Re: [討論] 整數陣列限定總和與上下界,取亂數值
看板Prob_Solve (計算數學 Problem Solving)作者tkcn (小安)時間13年前 (2011/10/21 00:30)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/4 (看更多)
我認為你的解法沒辦法產生真的隨機，
(也可能是我們對題目的定義不同))
下面是個例子:
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
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12