oj 1031 random permutation

2022-10-17 14:51:05

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的无重随机数列

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

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

—>两层？三层？不保险

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

—>搞定

 #include<iostream>

 #include<cstdlib>

 #include<ctime>

 using namespace std;

 int seed=time();

 int b[]={};

 int test(int b[],int i,int temp)

 {

     for (int j=;j<i;j++)

     {

         if (b[j]==temp) return -;

     }

     return ;

 }

 void give_test(int b[],int temp,int i,int n)

 {

     seed++;

     srand(seed);

     temp=rand()%n;

     if (test(b,i,temp)==-)

     {

         seed++;

         give_test(b,temp,i,n);

     }

     else b[i]=temp;

 }

 void random_permute(int a[],int n)

 {

     srand(seed);

     b[]=rand()%n;

     int temp=;

     for (int i=;i<n;i++)

     {

         give_test(b,temp,i,n);

     }

     for (int i=;i<n;i++)

     cout<<a[b[i]]<<" ";

 }

 int main(int argc,char *argv[])

 {

     int n;

     cin>>n;

     int a[];

     for (int i=;i<n;i++)

         cin>>a[i];

     random_permute(a,n);

     cout<<n<<endl;

     return ;

 }

验证可行

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

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

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

码农公寓