问题求解08问题求解.pptVIP

红帽和蓝帽 A B C A B C 结果 红 红 红 猜蓝，错 猜蓝，错 猜蓝，错 输 红 红 蓝 不答 不答 猜蓝，对 赢 红 蓝 红 不答 猜蓝，对 不答 赢 红 蓝 蓝 猜红，对 不答 不答 赢 蓝 红 红 猜蓝，对 不答 不答 赢 蓝 红 蓝 不答 猜红，对 不答 赢 蓝 蓝 红 不答 不答 猜红，对 赢 蓝 蓝 蓝 猜红，错 猜红，错 猜红，错 输 蒙提·霍尔问题 三门问题（Monty Hall problem）亦称为蒙提霍尔问题、蒙特霍问题或蒙提霍尔悖论，大致出自美国的电视游戏节目Lets Make a Deal。问题名字来自该节目的主持人蒙提·霍尔（Monty Hall）。 参赛者会看见三扇关闭了的门，其中一扇的后面有一辆汽车，选中后面有车的那扇门可赢得该汽车，另外两扇门后面则各藏有一只山羊。当参赛者选定了一扇门，但未去开启它的时候，节目主持人开启剩下两扇门的其中一扇，露出其中一只山羊。主持人其后会问参赛者要不要换另一扇仍然关上的门。 问题是：换另一扇门会否增加参赛者赢得汽车的机会率？ 蒙提·霍尔问题 最初选择的门 A A A B B B C C C 汽车的位置 A B C A B C A B C 蒙提可以打开的门 B,C C B C A,C A B A A,B 参赛者不转换选择 赢 输 输 输 赢 输 输 输 赢 参赛者转换选择 输 赢 赢 赢 输 赢 赢 赢 输 求数组的子数组之和的最大值 注意到 Sum[ i, …, j ]= Sum[i, …, j-1]+A[j]， 则可以将算法中的最后一个 for 循环省略，避免重复计算，从而使得算法得以改进，改进后的算法如下，这时复杂度 O(N2)。 int MaxSum( int*A , int n) { int maximum =-INF; int sum; for(int i=0; in; j++) { sum = 0 for (int j=i; jn; j++) { sum += A[j]; if (sum maximum) maximum = sum; } } return maximum; } 求数组的子数组之和的最大值 利用动态规划的方法求解 考虑数组中的一个元素 A[0]，以及和最大的一段数组 (A[i],…, A[j]) 和A[0] 之间的关系，有如下几种情况： (1) 当 0=i=j 时，元素 A[0] 本身构成和最大的一段； (2) 当 0=ij 时，和最大的一段以 A[0] 开始； (3) 当 0ij 时，元素 A[0] 跟和最大的一段没有关系。 因此，可以将一个大问题 (n个元素数组) 转化为一个较小的问题 (n-1个元素的数组)。 假设已经知道 (A[1],…, A[n-1]) 中和最大的一段之和为 All[1]，并且已经知道 (A[1], …, A[n-1]) 中包含 A[1] 的和最大的一段的和为 Start[1]。那么， (A[0],…, A[n-1]) 中问题的解 All[0] 为 max{A[0], A[0]+Start[1], All[1]} 求数组的子数组之和的最大值 int max (int x , int y) { return (xy) ? x : y; } int MaxSum( int*A , int n) { Start[n-1] = A[n-1]; All[n-1] = A[n-1]; for(i=n-2; i0; i--) { Start[i] = max(A[i], A[i]+Start[i+1]); All[i] = max(Start[i], All[i+1]); } return All[0]; } 正整数序列 给定正整数n，你的任务是用最少的操作次数把序列 1, 2, 3, …, n 中的所有数都变成 0。每次操作可从序列中选择一个或多个整数，同时减去一个相同的正整数。 比如，1, 2, 3 可以把 2 和 3 同时减小 2，得到 1, 0, 1。 int f(int n) { return n==1 ? 1: f(n/2) + 1; } 可口可乐瓶 便利店给出以下的优惠： 每 3 个空瓶可以换 1 瓶可口可乐。 现在，你准备从便利店买一些可口可乐(n瓶)，你想知道你最多可以从便利店拿到多少瓶可口可乐？ 以 8 瓶为例，可以获得多少？。 你也可以从朋友（或店主）那里借一个空瓶，这样可以获得多少？ 可口可乐瓶 设想买的可口可乐的瓶数为 n；借的空瓶数为 i； 总瓶数为 cnt，兑换前为 cnt=n+i； 实际喝到的可口可乐瓶数为 tot