5.1概率计数。没太看明白题意。。
5.2（查找一个无序数组）本题将分析三个算法，他们在一个包含n个元素的无序数组A中查找一个值x.
考虑如下的随机策略：随机挑选A中的一个下标i,如果A[i]=x,则终止，否则，继续挑选A一个新的随机下标，重复随机挑选下标，直到找到一个下标j，使A[j]=x,或者直到我们已经检查过A中的每一个元素，注意，我们每次都是从全部下标的集合中挑选，于是可能不止一次地检查某个元素。
a)请写出过程RANDOM-SEARCH的伪代码来实现上述策略，确保党A中所有下标都被挑选过时，你的算法应该停止。
#include <iostream>
#include <time.h>
using namespace std;
void main()
{
int a[10]={9,5,2,7,4,6,8,1,3,0},x=100,i,b[10]={1},flag=1;
cin>>x;
srand((unsigned)time(NULL));
while (flag)
{
i=rand()%10;
if (a[i]==x)
{
cout<<"已经找到"<<endl;
break;
}
else
{
b[i]=0;
}
for (int j=0;j<10;j++)
{
if(b[j])
{
break;
}
}
if (j==10)
{
flag=0;
cout<<"数组中无此值！"<<endl;
break;
}
}
}
b)假定恰好有一个下标i使得A[i]=x.在我们找到x和RANDOM-SEARCH结束之前，必须挑选A下标的数目期望是多少？
经过k次，找到x,成功检查到的概率p=1/n ，没有找到的概率q=(1-1/n) 利用伯努利的几何分布E=1/p=n
c)假设又κ≥ 1个下标i使得A[i]=x，推广你对b部分的解答，在我们找到x和RANDOM-SEARCH结束之前，必须挑选A下标的数目期望是多少？你的答案应该是n和k的函数。
由b可知成功检查到的概率p=k/n E=1/p=n/k
d)假设没有下标i使得A[i]=x。在检查完A的所有元素和RANDOM-SEARCH结束之前，我们必须挑选A的下标的数目期望是多少？
设i个元素未被检查，n-i个元素已被检查，成功检查到新元素的Pi=i/n,重复检查到旧元素的Pi=(n-i)/n算失败。所以这个可以看做伯努利的几何分布。
还剩下i个元素未被检查时候需要经过平均经过E=1/Pi=n/i.次检测到1个新元素。
所以可以看出还剩下n个元素时，仅平均需要n/n=1次既可检查到新元素。
还剩下n-1个元素时，平均需要n/(n-1)次检测到新元素
。。。。
还剩下1个元素时，平均需要n/1次检测到新元素
所以总的次数是E=∑n/i=n(1+1/2+1/3+...1/n)=nlnn=O(nlgn)
现在考虑一个确定性的线性查找算法，我们称之为DETERMINISTIC-SEARCH.具体的说，这个算法在A中顺序查找x,考虑A[1],A[2],A[3]...A[n]，直到找到A[i]=x，或者到达数组的某位。假设输入数组的所有排列都是等可能的。
e.）假设恰好有一个下标i使得A[i]=x。DETERMINISTIC-SEARCH平均运行时间是多少？DETERMINISTIC-SEARCH最坏情况运行时间是多少？
平均时间E=∑k/n=(1+2+..+n)/n=(n+1)/2.最坏情况是这个待查找的元素正好是最后一个元素，所以需要查找次数为n.
f.)假设又κ≥ 1个下标i使得A[i]=x，推广你对e部分的解答，DETERMINISTIC-SEARCH平均情形的运行时间是多少？最坏运行时间又是多少？ 用n与k的函数表达。
成功找到元素的概率p=k/n，查找失败的概率q=1-p,平均查找次数符合伯努利的几何分布,E=∑kp(1-p)^(k-1)=1/p=n/k.
g.)假设没有下标i使得A[i]=x。DETERMINISTIC-SEARCH平均运行时间是多少？DETERMINISTIC-SEARCH最坏情况运行时间是多少？
不管是平均还是最坏查找次数都是n.
最后，考虑一个随机算法SCRAMBLE-SEARCH，它先将输入数组随机变换数列，然后再排列变换后的数组上，运行上面的确定性查找算法。
h.)设k是满足A[i]=x的下标的数目。，请给出在k=0和k=1情况下，算法SCRAMBLE-SEARCH最坏情形的运行时间和运行时间期望。推广你的解答以处理
k>=1的情况。
这个无非是将第一种随机算法加上了一层随机性。对于生成的随机数列再次随机，那么依然是随机数列。所以k=0,1>=1的情况和上面的随机算法一致。
i.)你将会使用3种查找算法中的哪一个？解释你的答案。
当然是确定性线性查找算法了。。这个算法比随机算法花费更少的运行时间。