有朋友寫信問我有關這個程式的問題 我想說乾脆好好在這裡幫大家說明一下 希望有幫助 有需要的話可以配合程式看 （相信我，解釋程式不能當面說明真的很難說得清楚，我盡力啦） 假設我們現在要在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)