--[[
组合概率
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
转载于:https://www.cnblogs.com/lotushy/p/4863756.html
相关资源：数据结构—成绩单生成器
