扔鸡蛋问题
问题
仅给出两个鸡蛋， 尝试在 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; } |
