Re: [問題] 樂透不能重複問題
有朋友寫信問我有關這個程式的問題
我想說乾脆好好在這裡幫大家說明一下
希望有幫助
有需要的話可以配合程式看
（相信我，解釋程式不能當面說明真的很難說得清楚，我盡力啦）
假設我們現在要在1~10之中取出二個不重複的亂數
程式執行過程如下
第一回合執行前
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] //陣列索引
1 2 3 4 5 6 7 8 9 10 //陣列內容
假設第一回合從[0]~[9]之中取到[5]這個位置好了
接著便把[0]和[5]的“內容“交換 (打*處)
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] //陣列索引
6 2 3 4 5 1 7 8 9 10 //陣列內容
* *
完畢後你可以想成[0]是用來放答案的地方
所以下次取亂數的時候不再考慮[0]這個位置，也就是說6這個數字已經取過不再考慮
這也是為甚麼第二回合我們只取[1]~[9]（不去碰答案區）
第二回合執行前
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] //陣列索引
6 2 3 4 5 1 7 8 9 10 //陣列內容
接著第二回我們便從[1]~[9]之中來取
假設又取到[5]這個位置好了（巧合嘛^^，你也可以自行換別的數字）
接著便把[1]和[5]的“內容“交換 (記得我剛說[0]是答案區，我們不去動它的)
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] //陣列索引
6 1 3 4 5 2 7 8 9 10 //陣列內容
* *
這時候你可以想成[0]和[1]是用來放答案的地方
所以下次取亂數的時候不再考慮[0]和[1]這二個位置
也就是說6和1這二個數字已經取過不再考慮
這也是為甚麼第三回合(如果有的話)我們只取[2]~[9]
所以這個例子裡最後取出來的亂數是6, 1
好，接著來思考一下機率問題
首先第一回合取亂數時是不是1~10每一個數字被取到的機率是一樣的?
...答案是肯定的（機率為1/10），所以第一回合OK
那第二回合呢？
記得我們的問題是...取“不重複“的亂數
所以第一回合取到的6當然就不考慮啦
也就是說在第二回我們要從1,2,3,4,5,7,8,9,10這“九“個數字中取出一個亂數(不包含6)
因為[0]已經是答案區啦
而我第二回合只取[1]~[9]
現在你觀察一下第二回開始前[1]~[9]的內容
是不是剛好就是1,2,3,4,5,7,8,9,10這九個數字 (要想一下喔，這可不是巧合^^)
所以第二回合中這九的數字被選到的機率也是一樣的（機率為1/9）
請注意
雖然1/10和1/9好像機率不同，但別忘了這已經是第二回合囉，只剩下九個數字嘛
（而且要第一回合槓龜的人才有這榮幸出現在第二回合阿）
結論是每一個數字在這二回合的過程中被取到的機率是
(1/10)+(9/10*1/9) = 1/5
回想一下我們要解的問題你會發現
10個數字裡面任挑二個不重複的數字
每一個數字被挑到的機率本來就就是1/5囉（請參考機率課本）
希望這樣的說明真的有清楚了
最後我想說
我知道一般這個問題的解法都是
“把陣列打亂，然後取亂數“
但有沒有想過
到底要打多少次才夠亂？
我提供的程式基本上從機率的角度出發
利用一些小技巧避免“把陣列打亂“這個動作
讓程式跑起來比較有效率一些
作為大家參考吧
※ 引述《ninteen (小美)》之銘言：
: ※ 引述《ninteen (小美)》之銘言：
: : janyfor的方法是比較好的
: : 運算複雜度比較低
: : 不過所謂打亂陣列的地方可能要修改一下
: : 以下我提供程式碼
: : int Max = 46; //亂數的最大值
: : int[] numbers = new int[Max];
: : for (int i=0 ; i<Max ; i++) numbers[i]=i;//陣列初始化
: : int n = 6; //你需要的亂數個數
: : int pick, temp;
: : for(int i=0 ; i<n ; i++){
: : pick = (int)(Math.random()*(Max-i) + i);//重點在這裡
: : //Swapping
: : temp = numbers[pick];
: : numbers[pick] = numbers[i];
: : numbers[i] = temp;
: : }
: : //Show出亂數
: : for(int i=0 ; i<n ; i++) System.out.println(numbers[i]);
: 這個程式確實會出現0
: 如果不想出現0
: 把for (int i=0 ; i<Max ; i++) number[i]=i;
: 改成for (int i=0 ; i<Max ; i++) number[i]=i+1; 即可
: 至於Max-i這個地方是重點，不是我寫錯
: 基本精神是，取過的亂數不再取
: 也就是說
: 第一次取0~45，然後取出的亂數放到陣列的[0]的位置，一但放過去之後就不再動它
: 第二次取1~45，然後取出的亂數放到陣列的[1]的位置，一但放過去之後就不再動它
: 第三次取2~45，然後取出的亂數放到陣列的[2]的位置，一但放過去之後就不再動它
: 依此類推
: 希望這樣說明有清楚
: 原諒我不能畫圖很難說明
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 24.17.240.114
※ 編輯: ninteen 來自: 24.17.240.114 (12/11 17:17)
※ 編輯: ninteen 來自: 24.17.240.114 (12/11 17:18)
推
12/11 19:38, , 1F
12/11 19:38, 1F
推
12/12 21:20, , 2F
12/12 21:20, 2F
討論串 (同標題文章)