算法设计与分析 黄刘生 中国科学技术大学计算机系 国家高性能计算中心(合肥) 2008.819
1 算法设计与分析 黄刘生 中国科学技术大学计算机系 国家高性能计算中心（合肥） 2008.8.19
第一部分 概率算法
2 第一部分 概率算法
Ch1绪论 §11引言 1.故事:想象自己是神化故事的主人公,你 有一张不易懂的地图,上面描述了一处宝 藏的藏宝地点。经分析你能确定最有可能 的两个地点是藏宝地点,但二者相距甚远。 假设你如果已到达其中一处,就立即知道 该处是否为藏宝地点。你到达两处之一地 点,以及从其中一处到另一处的距离是5 天的行程。进一步假设有一条恶龙,每晚 光顾宝藏并从中拿走一部分财宝。假设你 取宝藏的方案有两种:
3 Ch.1 绪论 1. 故事：想象自己是神化故事的主人公，你 有一张不易懂的地图，上面描述了一处宝 藏的藏宝地点。经分析你能确定最有可能 的两个地点是藏宝地点，但二者相距甚远。 假设你如果已到达其中一处，就立即知道 该处是否为藏宝地点。你到达两处之一地 点，以及从其中一处到另一处的距离是5 天的行程。进一步假设有一条恶龙，每晚 光顾宝藏并从中拿走一部分财宝。假设你 取宝藏的方案有两种： §1.1 引言 地点 1 地点 2 你 5天 5天 5天
§11引言 方案1.花4天的时间计算出准确的藏宝地点,然 后出发寻宝,一旦出发不能重新计算 方案2.有一个小精灵告诉你地图的秘密,但你 必须付给他报酬,相当于龙3晚上拿走的财宝 Prob1.1.1若忽略可能的冒险和出发寻宝的代 价,你是否接受小精灵的帮助? 显然,应该接受小精灵的帮助,因为你只需 给出3晚上被盗窃的财宝量,否则你将失去4晚被 盗财宝量。 但是,若冒险,你可能做得更好!
4 方案1. 花4天的时间计算出准确的藏宝地点，然 后出发寻宝，一旦出发不能重新计算 方案2. 有一个小精灵告诉你地图的秘密，但你 必须付给他报酬，相当于龙3晚上拿走的财宝 Prob 1.1.1 若忽略可能的冒险和出发寻宝的代 价，你是否接受小精灵的帮助？ 显然，应该接受小精灵的帮助，因为你只需 给出3晚上被盗窃的财宝量，否则你将失去4晚被 盗财宝量。 但是，若冒险，你可能做得更好！ §1.1 引言
§11引言 设x是你决定之前当日的宝藏价值,设y是恶龙每 晚盗走的宝藏价值,并设x>9y 方案1:4天计算确定地址,行程5天,你得到的宝 藏价值为:x-9y 方案2:3y付给精灵,行程5天失去5y,你得到的 宝藏价值为:x-8y 方案3:投硬币决定先到一处,失败后到另一处冒 险方案) 一次成功所得:x5y,机会12 二次成功所得:x-10y,机会12期望赢利:x7,5
5 设x是你决定之前当日的宝藏价值，设y是恶龙每 晚盗走的宝藏价值，并设x>9y 方案1：4天计算确定地址，行程5天，你得到的宝 藏价值为：x-9y 方案2：3y付给精灵，行程5天失去5y，你得到的 宝藏价值为：x-8y 方案3：投硬币决定先到一处，失败后到另一处(冒 险方案) 一次成功所得：x-5y，机会1/2 二次成功所得：x-10y，机会1/2 §1.1 引言 }期望赢利：x-7.5y