假设需要生成前n个自然数的一个随机置换。例如,{4,3,1,5,2}和{3,1,4,2,5}就是合法的置换,但{5,4,1,2,1}却不是,因为数1出现两次而数3却没有。这个程序常常用于模拟一些算法。我们假设存在一个随机数生成器randint(i,j),它以相同的概率生成i和j之间的一个整数。
int randint(int i, int j) //srand()放在主函数中了 { if(i==0) return rand()%(j+1); else return rand()%(j-i+1) + i; }
填入从a[0]到a[n-1]的数组a,为了填入a[i],生成随机数直到它不同于已经生成的a[0],a[1],...,a[i-1]时,再将其填入a[i].
void fun1(int a[], int n) { int tmp; for (int i = 0; i < n; i++) { tmp=randint(1, n); for (int j = 0; j < i; j++) { if(tmp==a[j]) { tmp=randint(1, n); j=-1; } } a[i] = tmp; } }
同算法一,但要保存一个附加的数组,称之为used(用过的)数组。当一个随机数ran最初被放入数组a的时候,置used[ran]=1。
void fun2(int a[], int n) { int tmp; for (int i = 0; i < n; i++) { tmp=randint(1, n); while(used[tmp]!=0) tmp=randint(1, n); a[i]=tmp; used[tmp]=1; } }
填写该数组使得a[i]=i+1.然后:
for(i=1; i<n; i++) swap(&a[i], a[randint(0,i)]);
void swap(int &a, int &b) { int tmp=a; a=b; b=tmp; } void fun3(int a[], int n) { for (int i = 0; i < n; i++) { a[i]=i+1; } for (int i = 1; i < n; i++) { swap(a[i], a[ randint(0, i) ]); } }
如对本文有疑问, 点击进行留言回复!!
208核、6TB内存!阿里云发布全球最强云服务器:挑战摩尔定律极限
Pycharm环境下调用Qt desinger 常见问题以及解决方法
pyqt5讲解1:窗口,QLabel,QLineEdit,QTextEdit
已知后序遍历和中序遍历求层序遍历(L2-006 树的遍历 (25分))
网友评论