oj 1031 random permutation

Problem A: Random Permutations

Time Limit: 1 Sec Memory Limit: 128 MB Submit: 91 Solved: 54

Description

随机排列生成算法（运行a.exe输出数字的个数，运行a.exe test时输出为一次随机的排列）

Input

The input will be a list of integers

Output

The number of the integers

Sample Input

1 2 3 4 5 6 7 8 9 10

Sample Output

思路：产生元素数目为n的无重随机数列

—>产生随机数，确定不重复后才加入数组

—>确定不重复用循环？循环后如何有把握新的数也无重复？

—>两层？三层？不保险

—>递归？写一写，三个函数，赋值，比较，主函数

—>搞定

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<ctime>
 4 using namespace std;
 5 int seed=time(0);
 6 int b[50]={0};
 7 int test(int b[],int i,int temp)
 8 {
 9     for (int j=0;j<i;j++)
10     {
11         if (b[j]==temp) return -1;
12     }
13     return 0;
14 }
15 void give_test(int b[],int temp,int i,int n)
16 {
17     seed++;
18     srand(seed);
19     temp=rand()%n;
20     if (test(b,i,temp)==-1) 
21     {
22         seed++;
23         give_test(b,temp,i,n);
24     }
25     else b[i]=temp;
26 }
27 void random_permute(int a[],int n)
28 {
29     srand(seed);
30     b[0]=rand()%n;
31     int temp=0;
32     for (int i=1;i<n;i++)
33     {
34         give_test(b,temp,i,n);
35     }
36     for (int i=0;i<n;i++)
37     cout<<a[b[i]]<<" ";
38 }
39 int main(int argc,char *argv[])
40 {
41     int n;
42     cin>>n;
43     int a[50];
44     for (int i=0;i<n;i++)
45         cin>>a[i];
46     random_permute(a,n);
47     cout<<n<<endl;
48     return 0;
49 }

验证可行

—>修改符合oj设计（argc，argv……受不了了，先睡……改天再说）

—>逗了，原题未输入元素个数……改一改再说

—>拓展：http://www.cnblogs.com/eaglet/archive/2011/01/17/1937083.html 不经过如此多比较去重的较高效算法