算法导论第五章5.1雇佣问题课后答案研究

。

因为调用RANDOM(0,1)表示(a,b)之间的数，则肯定是用n位二进制数表示(a,b)之间的数。n位二进制数的每一位都有2种可能的选择(0,1)，所以对于n位二进制数就有2^n种选择方式，其中每一个n位二进制数都有1/2^n个几率被选中，(a,b)之间有b-a+1个数，我们约定用RANDOM(0,1)生成随机二进制数的实验过程是相互独立的，每次实验成功时的几率都是p=(b-a+1)/(2^n)(成功选中(a,b)之间的数的概率)选中失败的几率是q=1-p,根据伯努利的几何分布知E(x)=1/p 知道E(x)=(2^n)/(b-a+1) 这就表示了在用RANDOM(0,1)成功随机到(a,b)之间的数之前需要平均进行(2^n)/(b-a+1)次随机，因为每次进行RANDOM(0,1)随机生成数时间固定为常数Tc，所以期望时间T=((2^n)/(b-a+1))Tc

#include <iostream>

#include <time.h>

using namespace std;

int power(int x,int n)

{

    int s=1;

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

    {

       s*=x;

    }

    return s;

}

int Rand(int a[],int m)

{

    int n=0;

    srand((unsigned)time(NULL));

    for (int i=0;i<m;i++)

    {

        a[i]=rand()%2;

        n+=a[i]*power(2,i);

    }

    return n;

}

int Rand2(int a,int b,int n)

{

    int flag=0;

    for (int i=a;i<b;i++)

    {

        if (n==i)

        {

            flag=1;

            break;

        }

    }

    return flag;

}

void main()

{

  int j=1,m=8,a[8]={0},b[10000]={0};

  b[j]=Rand(a,m);

  if (Rand2(1,5,b[j]))

  {

      cout<<b[j]<<"符合题意！"<<endl;

  }

  while(1)

  {

      cout<<"b["<<j-1<<"]"<<b[j]<<endl;

      if (Rand2(1,5,b[j]))

      {

          cout<<b[j]<<"符合题意！"<<endl;

          break;

      }

      else 

      {

          ++j;

          b[j]=Rand(a,m);

          while (b[j-1]==b[j])//这个循环式为了重置那些随机到相同的数

          {

              b[j]=Rand(a,m);

          }

      }

  }

}