我想到的是:先把数组按照顺序初始化,然后随机从1~N-1取一个位置,把这个位置的值与放在N位置的值交换,然后再随机从1~N-2取一个,与放在N-1位置的值交换...直到只剩一个,放在那里不动。最终结果正好是倒序的每次取出的随机数,但有的数可能会被多次取到。
#include <stdio.h>
#define N 14
#define P {int i;for(i=1;i<=N;i++)printf("%d ",a[i]);printf("\n");}
int main()
{
int i=0;
int a[N+1];
int temp=0;
int j=0;
for(i=1;i<=N;i++) a[i]=i;
P
for(i=1;i<N;i++)
{
j=rand()%(N-i)+1;
temp=a[j];
a[j]=a[N-i+1];
a[N-i+1]=temp;
P
}
return 1;
}
比如:
初始化 1 2 3 4 5
1. 找到1~4的随机数3,序列变为1 2 [5] 4 [3]
2. 找到1~3的随机数2,序列变为1 [4] 5 [2] 3
3. 找到1~2的随机数2,序列变为1 [5] [4] 2 3
其中4这个数就多次被取到。
#include <stdio.h>
#define P {int i;for(i=1;i<=10;i++)printf("%d ",a[i]);printf("\n");}
int main()
{
int i=0;
int a[11];
int temp=0;
int j=0;
for(i=1;i<=10;i++) a[i]=i;
P
for(i=1;i<=10;i++)
{
j=rand()%9+1;
temp=a[j];
a[j]=a[10-i+1];
a[10-i+1]=temp;
P
}
return 1;
}
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 10 7 8 9 6
1 2 3 4 5 10 7 8 9 6
1 2 3 4 5 10 7 8 9 6
1 2 3 4 7 10 5 8 9 6
1 2 3 4 7 9 5 8 10 6
1 7 3 4 2 9 5 8 10 6
1 7 3 4 2 9 5 8 10 6
3 7 1 4 2 9 5 8 10 6
3 8 1 4 2 9 5 7 10 6
1 8 3 4 2 9 5 7 10 6
#include <stdio.h>
#define P {int i;for(i=1;i<=10;i++)printf("%d ",a[i]);printf("\n");}
int main()
{
int i=0;
int a[11];
int temp=0;
int j=0;
for(i=1;i<=10;i++) a[i]=i;
P
for(i=1;i<10;i++)
{
j=rand()%(11-i)+1;
temp=a[j];
a[j]=a[10-i+1];
a[10-i+1]=temp;
P
}
return 1;
}
1 2 3 4 5 6 7 8 9 10
1 10 3 4 5 6 7 8 9 2
1 10 3 4 5 6 7 8 9 2
1 10 3 4 5 6 8 7 9 2
1 10 3 4 5 8 6 7 9 2
1 10 3 4 5 8 6 7 9 2
1 10 3 4 5 8 6 7 9 2
1 10 4 3 5 8 6 7 9 2
4 10 1 3 5 8 6 7 9 2
10 4 1 3 5 8 6 7 9 2
D:\>tcc\tcc -run sj.c
1 2 3 4 5 6 7 8 9 10
1 10 3 4 5 6 7 8 9 2
1 10 3 4 5 6 7 8 9 2
1 10 3 4 5 6 8 7 9 2
1 10 3 4 5 8 6 7 9 2
1 10 3 4 5 8 6 7 9 2
1 10 3 4 5 8 6 7 9 2
1 10 4 3 5 8 6 7 9 2
4 10 1 3 5 8 6 7 9 2
10 4 1 3 5 8 6 7 9 2
#include <stdio.h>
#define N 14
#define P {int i;for(i=1;i<=N;i++)printf("%d ",a[i]);printf("\n");}
int main()
{
int i=0;
int a[N+1];
int temp=0;
int j=0;
for(i=1;i<=N;i++) a[i]=i;
P
for(i=1;i<N;i++)
{
j=rand()%(N-i)+1;
temp=a[j];
a[j]=a[N-i+1];
a[N-i+1]=temp;
P
}
return 1;
}
srand(time(NULL));
否则每次生成的伪随机数都是一样的。
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
随机产生一个 1~N! 范围的随机数,
比如生成的随机数是 4,
就输出上述第 4 个排列:2 3 1。
然后随机从1~N-1取一个位置
应改为:
然后随机从1~N取一个位置
以此类推。见:图灵社区:生成随机排列
http://www.ituring.com.cn/article/217419
#define N 100
#define P {int i;for(i=1;i<=N;i++)printf("%d ",a[i]);printf("\n");}
int fill(int a[])
{
for(int i=1;i<=N;i++) a[i]=i;
return 0;
}
int m1(int a[])
{
int i=0;
int temp=0;
int j=0;
for(i=1;i<N;i++)
{
j=rand()%(N+1-i)+1;
temp=a[j];
a[j]=a[N-i+1];
a[N-i+1]=temp;
}
return 0;
}
int m2(int a[])
{
int i=0;
int temp=0;
int j=0;
for(i=1;i<N;i+=2)
{
j=rand()%(N+1-i)+1;
temp=a[j];
a[j]=a[N-i+1];
a[N-i+1]=temp;
j=N+1-i-j; //仿照顺序查找的算法Q',在一次循环中处理2个位置
if(j>0)
{
temp=a[j];
a[j]=a[N-i+1-1];
a[N-i+1-1]=temp;
}
}
return 0;
}
int main()
{
int a[N+1];
for(int k=0;k<1000000;k++)
{
fill(a);
//测试第1种方法
//m1(a);
m2(a); //测试第2种方法
}
return 0;
}
//运行测试
方法1:
D:\lt>\timer tcc\tcc -run rp.c
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31
Kernel Time = 0.078 = 2%
User Time = 3.494 = 97%
Process Time = 3.572 = 99%
Global Time = 3.597 = 100%
方法2:
D:\lt>\timer tcc\tcc -run rp.c
Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31
Kernel Time = 0.078 = 3%
User Time = 2.449 = 95%
Process Time = 2.527 = 98%
Global Time = 2.554 = 100%