首页 > 代码库 > 数据结构与算法分析(C语言描述)习题2.7

数据结构与算法分析(C语言描述)习题2.7

问题描述:假设需要生成前N个自然数的一个随机置换。例如,{4,1,2,5,2}和{3,1,4,2,5}就是合法的置换,但{5,4,1,2,1}却不是,因为数1出现了两次而数3缺没有。这个程序常常用于模拟一些算法。我们假设存在一个随机数生成器randInt(i, j),它以相同的概率生成i和j之间的一个整数。下面是三个算法:

1.如下填入A[0]到A[N-1]的数组A;为了填入A[i],生成随机数直到它不同于已经生成的A[0],A[1], ... , A[i-1]时,再将其填入A[i]。

2.同算法1,但是要保存一个附加的数组,称之为Used(用过的)数组。当一个随机数Ran最初被放入数组A的时候,置Used[Ran]=1。这就是说,当用一个随机数填入A[i]时,可以用一步来测试是否该随机数已经被使用,而不是像第一个算法那样(可能)进行i部测试。

3.填写该数组使得A[i]=i+1。然后:

for(i = 1; i < N; i++)     swap(&A[i], &A[randInt(0, i)]);

分别写程序执行每个算法10次,得出一个好的平均值。对N=250,500,1 000,2 000运行程序1,对N=2500,5 000,10 000,20 000,40 000,80 000运行程序2;对N=1 0000,2 0000,4 0000,8 0000,160 000,320 000,640 000运行程序3。

实现:

 1 //返回一个[i, j)内的随机数 2 int randInt(int i, int j) 3 { 4     if (j - i == 0) 5         return i; 6     else if (j - i < 0) 7         return 0; 8     else 9         return rand() % (j - i) + i;10 }11 12 //算法113 int fillArray1(int A[], int n)14 {15     int count, ran, k;16 17     count = 0;18     while (count < n)19     {20         ran = randInt(0, n);21         for (k = 0; k < count; k++)22         {23             if (A[k] == ran)24                 break;25         }26         if (k == count)27         {28             A[count] = ran;29             count++;30         }31     }32     return 1;33 }34 35 //算法236 int fillArray2(int A[], int n)37 {38     int * used, count, ran;39 40     used = (int *)calloc(n, sizeof(int));41     if (used == NULL)42         return 0;43 44     count = 0;45     while (count < n)46     {47         ran = randInt(0, n);48         if (used[ran] == 0)49         {50             A[count] = ran;51             used[ran] = 1;52             count++;53         }54     }55     free(used);56     return 1;57 }58 59 static void swap(int * a, int * b)60 {61     int temp = *a;62     *a = *b;63     *b = temp;64 }65 66 //算法367 int fillArray3(int A[], int n)68 {69     int i;70     71     for (i = 0; i < n; i++)72         A[i] = i + 1;73     for (i = 0; i < n; i++)74         swap(&A[i], &A[randInt(0, i)]);75 }

以上算法主要有两个问题:

1). 动态数组问题:可用内存有限

算法2中要求用随机数做数组下标“Used[Ran]=1”,这就表示必须用有最大随机数个元素的变长数组Used数组。vs2013编译器不支持这种特性,我选择了动态内存分配malloc()实现Used数组。这受到了可用内存数量的限制。

2). C的随机数问题:随机数范围有限

C使用srand()和rand()产生伪随机数。我们知道,它们只能产生[0, RAND_MAX)之间的值。最多能产生(RAND_MAX+1)个不重复随机数。当N > RAND_MAX+1 时,算法不断尝试获取新的不重复随机数,陷入死循环。

如果您有更好的算法,欢迎交流。

数据结构与算法分析(C语言描述)习题2.7