有朋友写信问我有关这个程式的问题 我想说乾脆好好在这里帮大家说明一下 希望有帮助 有需要的话可以配合程式看 （相信我，解释程式不能当面说明真的很难说得清楚，我尽力啦） 假设我们现在要在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)