还是回文整理一下好了 贴ar大的连结 洗牌法 正确来源是 良先生...啊是林先生... http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/AlgorithmGossip.htm From Gossip@caterpillar 说明 --------- 洗扑克牌的原理其实与乱数排列是相同的，都是将一组数字（例如1～N）打乱重新排列， 只不过洗扑克牌多了一个花色判断的动作而已。 解法 --------- 初学者通常会直接想到，随机产生1～N的乱数并将之存入阵列中，後来产生的乱数存入阵 列前必须先检查阵列中是否已有重复的数字，如果有这个数就不存入，再重新产生下一个 数，运气不好的话，重复的次数就会很多，程式的执行速度就很慢了，这不是一个好方法 。 以1～52的乱数排列为例好了，可以将阵列先依序由1到52填入，然後使用一个回圈走访阵 列，并随机产生1～52的乱数，将产生的乱数当作索引取出阵列值，并与目前阵列走访到 的值相交换，如此就不用担心乱数重复的问题了，阵列走访完毕後，所有的数字也就重新 排列了。 至於如何判断花色？这只是除法的问题而已，取商数判断花色，取余数判断数字，您可以 直接看程式比较清楚。 关键 程式码 ======== final int N = 52; int[] poker = new int[N + 1]; // 初始化阵列 for(int i = 1; i <= N; i++) poker[i] = i; // 洗牌 for(int i = 1; i <= N; i++) { int j = (int) (Math.random() * N); if(j == 0) j = 1; int tmp = poker[i]; poker[i] = poker[j]; poker[j] = tmp; } ======== 以上看出 如果原po想求是1~6随机排列，一般人来说会想用random取六次不重复 但是处理重复会浪费效率 故即用洗牌方式，也就是回圈来随机swap，大约是O(N) 算线性时间 若原po先前还多加不必要的sort，则最好用的quick sort也会变 O(n*lgn) 备注tsya大的程式 如果我没看错的话 光是判断重复就可能花 O(n*n) 而直到不重复停止 就像骰6颗骰子要出现一条龙那样难，需要赌神才有办法 ※ 引述《tsya (tsya)》之铭言： : 提供你 C 语言的 code 作参考 : 要写 JAVA 版的 只要找到 API 就行了 : #include<stdio.h> : #include<time.h> : int duplicate(int r[6]){ : int i,j; : for(i=0;i<6;i++) : for(j=i+1;j<6;j++) : if(r[i]==r[j]) : return 1; : return 0; : } : int main(){ : int r[6]={0},i; : srand(time(NULL)); : while(duplicate(r)==1) : for(i=0;i<6;i++) : r[i]=(rand()%6)+1; : for(i=0;i<6;i++) : printf("%d ",r[i]); : printf("\n"); : return 0; : } : import java.util.Random; : import java.util.Arrays; : public class shuffle{ : static boolean duplicate(int a[]){ : int i,j; : for(i=0;i<6;i++) : for(j=i+1;j<6;j++) : if(a[i]==a[j]) : return true; : return false; : } : public static void main(String[] args){ : int[] a=new int[6]; : Random r=new Random(); : while(shuffle.duplicate(a)==true) : for(int i=0;i<6;i++) : a[i]=r.nextInt(6)+1; : System.out.println(Arrays.toString(a)); : } : } --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.166.57.130 ※ 编辑: teman 来自: 218.166.57.130 (09/04 09:58)