[lua]笔试-组合概率

--[[

组合概率

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description:

某生产零件的工厂为方便管理场内生产的零件种类，现将他们生产的零件从低等到高等零件排序，序号分别为1,2..n，已知该厂的任意几个低等的零件可以组合成更高等的零件，零件的序号代表了零件的等级，比如5号零件可以由1号和4号零件组合而成，也可以有2号和3号零件组合而成。

现有一个序号为 x 的零件，它是由n个序号在[a,b]区间内的零件组合而成，求n个序号在[a,b]区间内的零件组合为 x 零件的概率

一行输入四个整数依次为n，a，b，x，用空格分隔。数据规模和约定

对于50%的数据，n≤5.

对于100%的数据，n≤100,b≤100

输出一行为组合为 x 零件的概率，小数点后保留四位小数

--]]

local M = 101

local N = 101

local a = 0

local b = 0

local function init()

	local F = {}

	for i=1,M do

		F[i-1] = {}

		for j=1,N do

			F[i-1][j-1] = 0

		end

	end

	return F

end

function P(F, n, X)

	if F[n][X] == nil then

		return 0

	end

	if n == 0 and X == 0 then

		F[0][0] = 1

		return 1

	end

	if n == 0 and X ~= 0 then

		F[0][X] = 0

		return 0

	end

	for k=a,b do

		if X>=a then

			F[n][X] = F[n][X] + P(F, n-1, X - k)

		end

	end

	F[n][X] = F[n][X] / (b-a+1)

	return F[n][X]

end

function run(n,x,ta,tb)

	local F = init()

	a = ta

	b = tb

	local v = P(F, n, x)

	local l = string.format("%.4f", v)

	print(l)

end

run(1, 4, 1,5) -- expected: 1/5 = 0.2000

run(2, 10, 1, 9) -- expected: 4/36 = 1/9 = 0.1111

run(4, 23, 1, 20) -- expected: 0.0106
巴特西

[lua]笔试-组合概率

最新文章

热门文章
