扔鸡蛋问题
问题
仅给出两个鸡蛋, 尝试在 100 层的建筑物中抛出鸡蛋,在最坏的情况下找出鸡蛋能承受的最大楼层。
解题
- 尝试从第一层开始测试,最坏 100 次;
- 尝试从中间层(50)开始测试,如果碎了,再拿出第二个鸡蛋从第一次层开始测试,合计 51 次;如果没碎,第一个鸡蛋捡起来, 从 75层开始测试,然后往复下去
思路大致如上,100 层很难算, 如果总层数只有 0,1,2,3,4... 层,最坏需要多少次基本上可以手算出来, 结果如下
层数 | 最坏测试数 |
---|---|
0 | 0 |
1 | 1 |
2 | 2 |
3 | 2 |
4 | 3 |
5 | 3 |
然后,要在 6 层楼房找出最大承受高度,
1. 第一枚鸡蛋可以从第一层抛出,如果碎了,最大承受楼层 0, 没碎,意味着我还有两个完整的鸡蛋可以在剩下 5 层中寻找结果,五层,见上表,最少需要 3 次,合计意味最坏 4 次
2. 第一枚鸡蛋从第二层抛出,如果碎了,另一枚鸡蛋从第一层开始扔,直到碎了为止,最坏 2 次, 没碎,意味着我还有两个完整的鸡蛋可以在剩下 4 层中寻找结果,四层,见上表,最少需要 3 次,合计最坏 4 次
3. 第一枚鸡蛋从第三层抛出...
4. 第一枚鸡蛋从第四层抛出...
5. 第一枚鸡蛋从第五层抛出...
6. 第一枚鸡蛋从第六层抛出...
7. 第一枚鸡蛋从第七层抛出...
8. 第一枚鸡蛋从第八层抛出, 合计最坏 8 次
其实结果已经出来了,6 层 楼中最少测试数即上述八种可能中最优的一个
f{n} = min{ (max{(1), f{n-1})), (max{(2), f{n-2})), (max((3), f{n-3})), ...}
cpp 代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> using namespace std; //int temp[1000] = {0, 1, 2, 2, 3, 3, 3, 4}; int temp[1000] = {0}; int towEges(int layer = 100) { for (int i=1;i<=layer;i++) { temp[i] = i; int a = 1; //cout<<i<<':'; while (a < i) { // 碎了,没碎 int tmp = (a) > (1+ temp[i-a]) ? (a):(1 + temp[i-a]); //cout<<tmp<<' '; if (tmp < temp[i]) { temp[i] = tmp; } a++; } //cout<<endl; } return 1; } int main() { towEges(100); for(int i=1;i<101;i++) { cout <<i<<':'<< temp[i] << endl; } return 0; } |