洗牌演算法(交換法)

洗牌演算法就是可以產生不重複的亂數的一種演算法,舉例來講如果要產生十個亂數,並且這十個亂數必須是「不重複」的,那很多人的直覺是用rand函式取得一個亂數值以後,存入陣列,並且跟陣列內以有的數字做比對,這種方法簡單是簡單,但是效能很差,而這裡要介紹的洗牌演算法效能跟剛剛講的方法可說是天差地遠,洗牌演算法的原理其實很簡單,就是先在陣列裡存入數字,然後將數字打散

講解:

例如現在要產生10個不重複的亂數

則我們建立一個陣列,並在裡面存入1~10

int x[10]={0};

for(int i=0;i<=9;i++){
	x[i]=i;		//將x陣列的1~10元素依序填入資料,例如x[1]=1,x[2]=2
}

也就是說x[0]=0,x[1]=1,x[2]=2.....

再來我們將陣列的資料打散,利用交換法

time_t xx;
    srand((unsigned)time(NULL));			//用時間重設亂數表

    for(int ii=0;ii<=1000;ii++){
        int n1=rand()%10;		//產生0~9的亂數
        int n2=rand()%10;
        //將陣列資料進行交換(打散)
		int temp=x[n1];
        x[n1]=x[n2];
        x[n2]=temp;

    }

產生0~9的亂數,指定為n1、n2,並且將x[n1]與x[n2]的資料互換

趙這個動作持續一定次數之後(此處假設為1000次),陣列x裡面的資料就完全混亂了

也就是說x[0]裡面存的不再是0,x[1]裡面存的也未必是1

到這裡就算是完成囉~

輸出陣列裡的資料,然後他其實就是亂數XD,而且內容還不會重複

詳細原始碼:

/*
	洗牌演算法
	產生不重複亂數
	可用於排座位
*/

#include 
#include		//亂數函式要用的
#include

using namespace std;

int main()
{
    int x[10]={0};

    for(int i=0;i<=9;i++){
        x[i]=i;		//將x陣列的1~10元素依序填入資料,例如x[1]=1,x[2]=2
    }

    time_t xx;
    srand((unsigned)time(NULL));			//用時間重設亂數表

    for(int ii=0;ii<=1000;ii++){
        int n1=rand()%10;		//產生0~9的亂數
        int n2=rand()%10;
        //將陣列資料進行交換(打散)
		int temp=x[n1];
        x[n1]=x[n2];
        x[n2]=temp;

    }

    for(int i=0;i<=9;i++){
        cout<

專案檔下載:Box.net4SharedGoogleDropbox

洗牌演算法原理:

他的原理其實不難懂,因為你一開始x陣列的內容是有順序的1~10,但是經過打散以後,x陣列的內容仍然是1~10的數字,但是原有的順序性就不再存在了,這時候如果再用x[0]~x[9]的順序來輸出,所輸出的資料就是亂數

後記:

大概什麼時候會用到洗牌演算法呢?像最常見可能就是選座位的時候吧,先把每個座位都設定好一個編號,然後陣列的維度就是代表同學的學號,透過洗牌演算法,就可以讓每個同學都分到「隨機」的座位,並且座位絕對不會重複

在〈洗牌演算法(交換法)〉中有 10 則留言

  1. 要再O(n)完成洗牌
    只要這樣就好了, 而且每個人都會至少被換到一次
    for(int i = 0; i < n; i++)
    {
    int n1=rand()%10;
    //將陣列資料進行交換(打散)
    int temp=x[n1];
    x[n1]=x[i];
    x[i]=temp;
    }

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步了解 Akismet 如何處理網站訪客的留言資料