程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 一個C語言編寫的不重復隨機序列算法

一個C語言編寫的不重復隨機序列算法

編輯:關於C語言

最近一直搞數據庫,很久沒摸C語言,都快忘了。為了練手,前段時間一個沒有完成的產生不重復隨機序列的算法重寫一遍。

 

C語言沒有隨機種子值的概念,所以產生一個隨機、不重復序列還不太容易。最常歸的思路是:給定一個范圍,然後做rand() %MAX_VALUE運算,如果發現該值已經取過,則重新產生一個值。這個算法,你會發現隨著,當MAX_VALUE值大到一定程度時(我的測試值為20),就會陷入死循環。原因是,比如20個數,取了前面18個數,產生後面兩個數的幾率就會指數及減小,可能做上百萬次運算,也無法產生最後兩個數。於是自己重新想了一種算法。

算法原理:給出兩個數列,產生一個隨機數,將第二個數列該位置上的數,復制到第一個數列,然後對第二個數列進行壓縮,知道所有的值都使用完為止。如圖:

第一輪迭代

 \

將臨時數列進行壓縮,進行第二輪迭代:

 \

這樣,基本可以產生一個均勻不重復的隨機數列。但是,根據測試結果,同一個MAX_VALUE值,每次產生的隨機數列是一樣的,所以,若將此應用於生產,還需做其他處理。

源代碼如下:

 

#include"stdafx.h"

#include<stdlib.h>

#include<stdio.h>

#include<memory.h>

 

intrand_array(int* arr, int floor);

voidMergArr(int* pArr, int nSize);

 

#defineMAX_VALUE    10

 

int main(intargc, char** argv)

{

         int rand_list[MAX_VALUE];

         int ret = 0;

         int i = 0;

 

         ret = rand_array(rand_list, MAX_VALUE);

 

         for (i = 0; i < MAX_VALUE; i++)

         {

                   printf("rand_list[%d]:%d\r\n", i, rand_list[i]);

         }

 

         return 0;

}

 

intrand_array(int* pArrList, int nFloor)

{

         int i = 0;

         int* pArrTmp = NULL;                // 臨時數組

         int nRand = 0;

         int nTotal = 0;

         int nLastSize = 0;

         int nMemSize = nFloor * sizeof(int) +1;

 

         // 先為數組分配內存

         pArrTmp =  (int*)malloc(nMemSize);

 

         if (pArrList == NULL || pArrTmp ==NULL)

         {

                   return -1;

         }

 

         // 初始化數組

         for (i = 0; i < nFloor; i++)

         {

                   pArrList[i] = -1;

                   pArrTmp[i] = i;

         }

 

         nLastSize = nFloor;

 

         // 產生隨即數,並從pArrTmp表填至pArrList

         while (nTotal < nFloor)

         {

                   nRand = rand() % (nFloor -nTotal);

 

                   if (pArrTmp[nRand] != -1)

                   {

                            pArrList[nTotal] =pArrTmp[nRand];

                            pArrTmp[nRand] = -1;

                            nTotal++;

                   }

                   else

                   {

                            MergArr(pArrTmp,nLastSize);

                            nLastSize = nFloor -nTotal;

                   }

         }

 

         free(pArrTmp);

         pArrTmp = NULL;

 

         return 0;

}

 

voidMergArr(int* pArr, int nSize)

{

         int i = 0;

 

         int total = 0;

 

         for (i = 0; i < nSize; i++)

         {

                   if (pArr[i] != -1)

                   {

                            pArr[total] =pArr[i];

 

                            if (total != i)

                                     pArr[i] =-1;

 

                            total++;

                   }

 

         }

}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved