還是回文整理一下好了 貼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)