【编程珠玑】第十二章：取样问题

一，概述
        问题描述：如何生成0~n-1内的m个随机整数（不重复）
               需求：按序输出，并且保证每个子集被选中的可能性相等。
        1）给出下面代码
[html]
#include "stdio.h"
#include "stdlib.h"
#include "time.h"

void getRandNumber(int m,int n)//在0 -- n-1 中挑选m个随机数
{
    srand(time(NULL));//这个很关键

    int i,j;
    for(i=0;i<n;++i)
    {
        if( rand()%(n-i) < m)
        {
            printf("%d ",i);
            m--;
        }
    }

}
int main()
{
    getRandNumber(5,10);
    return 0;
}

        其中for循环保证按序输出，rand()%(n-i) 保证输出概率符合要求。
     算法时间复杂度 O(n)
         2）非常规求法：
               将n个数写到大小相等的纸片上，摇匀。然后取出m个纸片，按序输出m个纸片

        3）解决算法时间复杂度问题，提出以下优化方案
              给定一个集合S，每次插入一个元素。插入之前检查S中个数是否达到m，且随机数在不在m中。
[html]
#include <iostream>
#include <set>
using namespace std;

void getSet(int m,int n)//在0 -- n-1 中挑选m个随机数
{
    srand(time(NULL));//这个很关键
    set<int> S;
    while(S.size()<m) //直到填满
        S.insert(rand()%n);
    set<int>::iterator i;
    for(i=S.begin();i!=S.end();++i)
        cout<<*i<<" ";
}
int main()
{
    getSet(5,10);
    return 0;
}

          C++模板插入操作在O(logm)时间内完成，而遍历集合需要O(m)时间。所以完整程序需要O(mlogm)时间

         4）生成随机数的另一种方式：把包含0 - n-1的数组顺序打乱，然后把前m个元素输出。
               更好的方式是，我们只需要打乱前m个元素，然后排序输出。
                或者生成大于n个1 - n范围的随机数，然后去掉重复的，输出前面的m个元素
[html]
#include <iostream>
#include <algorithm>
using namespace std;

void sort(int a[],int m)
{
    for(int i=1;i<m;i++)
        for(int j=i;j>0&&a[j-1]>a[j];j--)
                  swap(a[j-1],a[j]);
}

void getShuf(int m,int n)//在0 -- n-1 中挑选m个随机数
{
    srand(time(NULL));//这个很关键 www.zzzyk.com
    int i,j;
    int a[n];
    for(int i=0;i<n;++i)
        a[i]=i;
    for(int i=0;i<m;++i)
    {
        swap(a[i],a[rand()%(n-i)]);
    }
    sort(a,m);

    for(i=0;i<m;++i)
        cout<<a[i]<<" ";
}
int main()
{
    getShuf(5,10);
    return 0;
}

二，习题
       1）
[html]
int bigrand()
{
      return RAND_MAX*rand() + rand();
}
int region(int l, int u) //[l, u]
{
     ++u;
      return l + rand() % (u - l);

2）选择的m子集的概率相等，如何做？
在1 - n范围内随机选择一个数，然后其后的m-1 个数为所选择的子集（有可能到头，然后从0开始）

       3）
当m < n/2时，
总共试了k次，则前面k-1次找到的数都是在集合中，那么只有第k次不在里面，那么概率
p = (m/n)^(k-1) * (n-m)/n
那么期望是连加 k = 1至无穷大，根据二项式分布可知，期望等于
n/(n-m) < 2
从而可知得证
       4）参考算法导论中文版64页。
             搜集n张随机赠送的赠券，需要多少次？ nlogn次

       7）先输出再递归，改成先递归再输出
       9）给出一个算法，在最坏情况下只使用m个随机数。而不用丢弃已经生成的随机数
[html]
#include <iostream>
#include <set>
using namespace std;
void getSet(int m,int n)//在0 -- n-1 中挑选m个随机数
{
    srand(time(NULL));//这个很关键
    set<int> S;
    for(int i=n-m;i<n;++i)
    {
        int t=rand()%(i+1);
        if(S.find(t) == S.end())
                S.insert(t);
        else
                S.insert(i);
    }
    set<int>::iterator j;
    for(j=S.begin();
         j!=S.end();++j)
    cout<<*j<<" ";
}
int main()
{
    getSet(5,10);
    return 0;
}

10）问题：如何随机从n个对象中选择一个对象，这n个对象是按序排列的，但是在此之前你并不知道n的值？<

补充：软件开发 , 其他 ,