PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [討論] 整數陣列限定總和與上下界,取亂數值

看板Prob_Solve (計算數學 Problem Solving)作者tropical72 (藍影)時間13年前 (2011/10/21 02:16)推噓1(1推 0噓 2→)

留言3則, 2人參與討論串3/4 (看更多)

謝謝您的提醒，的確是我的誤失，若將演算法改如下請問如何？改善方法一 : 去掉累計機率概念，新增集合洗牌概念 N = 3 , sum = 4 [0] [1] [2] low 0 0 0 high 1 5 7 1. 初始化 arr = low = {0,0,0} 計算 slack = sum - (sum of arr) = 4 - 0 = 4 2. rng[i] = high[i] - arr[i] rng = {1,5,7}, rng 為非 0 元素之 index 加入集合 SET 中, 此例為 SET = {0,1,2} 3. 對 SET 做 shuffle , 取出第一個元素出來, 假設取出為 k 遞增 arr[k]。 4. 回到 step 2, 執行 slack 次改善方法二 : 改善累計機率概念，加入集合 N = 3 , sum = 4 [0] [1] [2] low 0 0 0 high 1 5 7 1. 初始化 arr = low = {0,0,0} 計算 slack = sum - (sum of arr) = 4 - 0 = 4 2. rng[i] = high[i] - arr[i] rng = {1,5,7}, rng 為非 0 元素之 index 加入集合 SET 中, 此例為 SET = {0,1,2}， 3. 再對 SET 做累計機率統計，因裡面有 3 個元素，均勻分配下， prob[0] = 0.3333 , prob[1] = 0.6666 , prob[2] = 1.0 4. 取一隨機亂數 rnd = (0,1] ， find min k st rnd <= prob[k] 假設 rnd = 0.05 , k = 1, 再遞增 arr[ SET[k] ] 5. 回到 step 2, 執行 slack 次請示請示乍看下，上二種法是否算是均勻？改善 1 用到多次之洗牌法效率從原本的 O(n) 又變到了 O(n^2)，改善 2 若無問題的話，暫時應以此方案做為解決，更好之解法乃待尋便是 (目前似乎沒什麼人在探討這問題 XD) 最後謝謝您不吝指正，非常感激 *^_^* ※ 引述《tkcn (小安)》之銘言： : 我認為你的解法沒辦法產生真的隨機， : (也可能是我們對題目的定義不同)) : 下面是個例子: : 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} 這組解的機會較高。 : : http://edisonx.pixnet.net/blog/post/81995873 -- No matter how gifted you are, alone, can not change the world. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.78.41 ※ 編輯: tropical72 來自: 180.177.78.41 (10/21 02:30)