生成前n个自然数的一个随机置换的问题(随机数)
假设要生成前n个自然数的一个随机置换,如{4,3,1,5,2}和{3,1,4,2,5}就是一个合法置换;但{5,4,1,2,1}就不是,因为1出现2次而3没有。假设我们有一个随机数生成器RandInt(i,j),它以相同概率生成i到j之间的整数,下面是三个算法。
(1) 如下填入从A[0]到A[N-1]的数组A:为了填入A[i],生成不同于A[0],A[1],...,A[i-1]之间的随机数时,才将其填入A[i]
请问这个程序有什么问题?为什么随机数是5位数的?RandInt感觉写的是对的啊?等待大神赐教。。。
[code=C/C++][/code]// Sep5.cpp : //
#include "stdafx.h"
#include <stdio.h>
#include<time.h> //使用当前时钟做种子
#include <stdlib.h>
long RandInt(long X, long Y)
{
if(X==0)
{
return rand()%Y;
}
else
return rand()%(Y-X+1)+X; //判断随机数的产生区间
}
bool findNum(long rand,long *b,int index)
{
for(int i=0;i<=index;i++){
if(*b==rand)return true;
}
return false;
}
int _tmain(int argc, _TCHAR* argv[])
{
long a[100000];
long N;
long ran = 0;
double duration;
clock_t start;
clock_t finish;
start=clock();
printf("请输入自然数个数N:\n");
scanf("N=%ld",&N);
srand((unsigned)time(NULL)); //初始化随机数
ran = RandInt(0,N);
printf("%ld",ran);
a[0]=ran;
int i=1;
while(i<N){
ran = RandInt(0,N);
if(findNum(ran,a,i)==false){
a[i]=ran;
i++;
}
printf("%ld,",a);
}
finish=clock();
duration=(double)(finish-start)/CLOCKS_PER_SEC;
return 0;
}
[解决办法]
#include <stdio.h>
#include<time.h> //使用当前时钟做种子
#include <stdlib.h>
long RandInt(long X, long Y) {
if (X == 0) {
return rand() % Y;
} else
return rand() % (Y - X + 1) + X; //判断随机数的产生区间
}
bool findNum(long rand, long *b, int index) {
for (int i = 0; i < index; i++) { // ======================
if (b[i] == rand) // ======================
return true;
}
return false;
}
int main() {
long a[100000];
long N;
long ran = 0;
double duration;
clock_t start;
clock_t finish;
start = clock();
printf("请输入自然数个数N:\n");
scanf("%ld", &N); // ======================, 不要N=%ld,如果有,输入必须如:N=8
srand((unsigned) time(NULL)); //初始化随机数
ran = RandInt(0, N);
printf("%ld,", ran); // ======================
a[0] = ran;
int i = 1;
while (i < N) {
ran = RandInt(0, N);
if (findNum(ran, a, i) == false) {
a[i] = ran;
printf("%ld,", a[i]); // ======================
i++;
}
}
finish = clock();
duration = (double) (finish - start) / CLOCKS_PER_SEC;
return 0;
}
[解决办法]
感觉你自己定义一个链表效率能高一些。。。
[解决办法]
没看出什么问题,个人认为这样写比较好,每次循环用新的种子
while (i < N) {
srand((unsigned) time(NULL)); //初始化随机数
ran = RandInt(0, N);
if (findNum(ran, a, i) == false) {
a[i] = ran;
printf("%ld,", a[i]); // ======================
i++;
}
}