算法导论练习题（第五章第二小节）

算法导论5.2习题解析

• 5.2-1 在HIRE-ASSISTANT模型中，若求职者按照随机顺序依次出现，恰好进行一次聘用操作的可能性有多大？恰好进行n次聘用操作的概率又是多少？
  • 5.2-2 在HIRE-ASSISTANT模型中，若求职者按照随机顺序依次出现，恰好进行两次聘用操作的概率是多少？
  • 5.2-3 运用指示器随机变量的方法，计算掷出n个骰子后所得点数总和的数学期望。
  • 5.2-4 运用指示器随机变量的方法，解决如下帽子核对问题（hat-check problem）：假设有n位顾客，每位顾客将一顶帽子交给餐厅的服务员。服务员在不区分的情况下将帽子以随机顺序归还给顾客。请问顾客中恰好拿到自己帽子的人数的期望值是多少？
  • 5.2-5 设A[1..n]是一个由n个不同数值组成的序列。若存在i<j且A[i]>A[j]的情况，则称(i,j)为序列A的一个逆序对（inversion）。（更多关于逆序对的示例可参考思考题2-4的内容。）假设序列A中的元素是<1,2,...,n>的一个均匀随机排列，请运用指示器随机变量的方法计算该序列中逆序对数量的期望值。

5.应聘者随机顺序下的雇佣概率计算

答：由于应聘者的出现顺序为随机排列，因此每个应聘者在任意位置出现的可能性均为1/n。
由此可知，恰好进行一次雇佣操作的概率为$(1/n)^