C语言之random_n-续
之前写拉一个random_n的算法实现,虽然简单易懂,但是算法的效率相对来说不算很高,节省拉空间,只用到拉一个数组实现。
这个random_n的实现用到拉两个数组,子函数中的数组在函数栈销毁时释放空间。最好和最坏运行时间都是O(N )。主要时利用拉空间换时间。
具体的代码实现如下:
#include<stdio.h>
#include<stdlib.h>
#define MAX_NUM 10
void random_n(int a[],int n);
int main()
{
int a[MAX_NUM],i=0,j=0;
while(j<MAX_NUM)
{
a[j]=-1;
j++;
}
random_n(a,MAX_NUM);
while(i<MAX_NUM)
{
printf("%d\t",a[i]);
i++;
}
printf("\n");
return 0;
}
void random_n(int a[],int n)
{
int temp[n],k=0,count=0,x=0;
while(k<n)
{
temp[k]=k;
k++;
}
srand(time(0));
count=n;
k=0;
while(count)
{
x=rand()%count;
a[k]=temp[x];
printf("X= %d\t temp= %d \n",x,a[k]);
temp[x]=temp[count];
count=count-1;
k=k+1;
x=0;
}
}
调试和运行结果:
主要的思想:先产生0-N 之间的所有数,然后依次产生一个随机数,把产生的随机数当做下标,访问已经产生的有序数组,并取出下表所对应的值付给我们传进来的元数组。然后把这个数用最后一个数据覆盖掉。然后让产生随机数的模减1,这样下次访问的有效范围便是之前没有访问过的。这样依次循环进行知道数组填满。
思考过程如下:
----------------------------------------------------------------------------------------------
| 0 | 1 | 2 | .。。。 | 。。。 | N-1 | N |
-----------------------------------------------------------------------------------------------
假如产生的随机数为2,则:
----------------------------------------------------------------------------------------------
| 0 | 1 | N | .。。。 | 。。。 | N-1 | N |
-----------------------------------------------------------------------------------------------
下一次的寻址范围是:
----------------------------------------------------------------------------------------------
| 0 | 1 | 2 | .。。。 | 。。。 | N-1 | N |
-----------------------------------------------------------------------------------------------
依次覆盖。
摘自 明月天涯
补充:软件开发 , C语言 ,