一种生成互不相同的随机数算法解决方案

一种生成互不相同的随机数算法
源代码如下
#include <iostream>
#include <time.h>
#include <windows.h>
using namespace std;
void rnd(int a[],int min,int max,int num)
{
int *_array=new int[max-min+1];
for (int i=0;i<max-min+1;i++)
_array[i]=min+i;
int t=max-min+1,r;
for (i=0;i<num;i++)
{
r=rand()%t;
a[i]=_array[r];
_array[r]=_array[--t];
}
delete []_array;
}
int main()
{
srand(time(0));
int a[10];
rnd(a,0,9,10);
for (int i=0;i<10;i++)
{
cout<<a[i]<<"\t";
}
return 0;
}
大致逻辑为
1.根据参数给定的最大数和最小数新建一个数组_array保存该范围内所有数
2.用一个变量t记录现在数组中有多少个不重复的数初始值为给定范围内的数的个数
3.从_array中随机抽取一个数放到给定的数组a,然后把该数和_array数组中的最后一个数交换
4.t-- 然后现在数组中前t个数是没有重复的然后重复步骤3

网上看到的两种大致分为三种
第一种是将产生的随机数与逐个与数组中前面的数作比较这种方法缺点是效率低当数组越大对速度的影响就越大
第二种是将抽过的数赋值为0 然后每次赋值前做一次判断如果再次抽到的数为0 就重新抽一次知道抽到不为0的数为止这种方法的缺点是命中率低
第三种是每次抽到随机数后从该数开始每个数组取该数下标+1的数的值该方法缺点是大量移动数据照成效率降低该方法还有一种变形可以克服该缺点就是用链表记录数据然后抽到过的数据从链表中删除不过使用链表也有些麻烦

欢迎大家补充指正

------解决方案--------------------
随机必然有重复。
所谓“不重复的随机”，其实是“洗牌”。
洗牌算法参考下面：

C/C++ code

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int d[6];
int i,n,a,b,t;
int c,j;
void main() {
    srand(time(NULL));
    printf("shuffle 0..n-1 demo\n");
    for (n=1;n<=5;n++) {/* 测试1～5个元素 */
        printf("_____n=%d_____\n",n);
        j=1;
        for (c=1;c<=n;c++) j=j*c;/* j为n! */
        j*=n*2;
        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */
            for (i=0;i<n;i++) d[i]=i;/* 填写0～n-1 */
            for (i=n;i>0;i--) {/* 打乱0～n-1 */
                a=i-1;b=rand()%i;
                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
            }
            printf("%04d:",c);
            for (i=0;i<n;i++) printf("%d",d[i]);
            printf("\n");
        }
    }
    printf("shuffle 1..n demo\n");
    for (n=1;n<=5;n++) {/* 测试1～5个元素 */
        printf("_____n=%d_____\n",n);
        j=1;
        for (c=1;c<=n;c++) j=j*c;/* j为n! */
        j*=n*2;
        for (c=1;c<=j;c++) {/* 测试n*2*n!次 */
            for (i=1;i<=n;i++) d[i]=i;/* 填写1～n */
            for (i=n;i>1;i--) {/* 打乱1～n */
                a=i;b=rand()%i+1;
                if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
            }
            printf("%04d:",c);
            for (i=1;i<=n;i++) printf("%d",d[i]);
            printf("\n");
        }
    }
}

------解决方案--------------------

C/C++ code


#include <iostream>
#include <ctime>
using namespace std;

void Print(int *a,int length)
{
    for(int i=0; i < length; ++i)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

///
void RandN(int min,int max,int *a)
{
    srand((unsigned)time(0));
    cout<<"开始产生随机数: \n";
    int count=0;
    int *arra=new int[max];
    int i=0;//作为了随机数据的下标

    while(count < 10)
    {
        /*添加代码*/
        int Sin=rand()%max;
        if(Sin == a[Sin])
        {
            continue;
        }
        else
        {
            a[Sin]=Sin;
            count++;
        }
        arra[i]=a[Sin];
        ++i;
    }

    Print(arra,max);
    delete []arra;

}
int _tmain(int argc, _TCHAR* argv[])
{
    int a[10];
    memset(a,-1,10);//初始化
    RandN(0,10,a);
    return 0;
}

一种生成互不相同的随机数算法解决方案

相关推荐