作者tkcn (小安)
看板Prob_Solve
标题Re: [讨论] 整数阵列限定总和与上下界,取乱数值
时间Fri Oct 21 00:30:24 2011
我认为你的解法没办法产生真的随机，
(也可能是我们对题目的定义不同))
下面是个例子:
N = 2, sum = 1
[0] [1]
low: 0 0
high: 2 10
也就是必须满足:
0 <= arr[0] < 2
0 <= arr[1] < 10
arr[0] + arr[1] = 1
能够满足上述条件的解有两组:
1. {0, 1}
2. {1, 0}
在我的观点看来，这两组解出现的机率必须是相同，才是正确的随机。
但我认为你提出的程式，出现 {0, 1} 这组解的机会较高。
※ 引述《tropical72 (蓝影)》之铭言：
: 我尝试的解法如下 (献丑了)
: 演算法大致如下所述
: process:
: assign low to arr
: slack = sum - (sum of low array)
: for i:= 1 to slack
: * cal column prob. of (range of up[j],arr[j]) (prob[j])
: * generate rnd = random(0,1)
: * find min j , st prob[j] >= rnd
: * increment arr[j]
: end for
: end process
: 可能没写那麽清楚，提供小弟 website 上详细说明
:
: http://edisonx.pixnet.net/blog/post/81995873
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.114.78.231