关于“高楼扔鸡蛋”这个问题
今天上午，我们考了一张2022年的CSP-J入门级的初赛试卷，（结果我的成绩不怎么样（题外话））。下午分析卷子的时候，有人说第二大题阅读程序的第二小题是“高楼扔鸡蛋”问题，题目给的程序用了 2 种方法解了“高楼扔鸡蛋”问题。
于是，老师用了大半个下午和我们讨论了“高楼扔鸡蛋”这个问题。
题目意思很简单：
有 n 层楼，m 个鸡蛋，在某一个楼层及其以下的楼层往地面扔鸡蛋，鸡蛋不会碎；但在这个楼层以上的楼层往地面扔鸡蛋，鸡蛋就会碎。让你求至少需要耗费多少个鸡蛋才能找到这个楼层。（当然啦，鸡蛋没碎便可以再次使用（还有一点，使用的鸡蛋个数不能超出 m 哦！））
上面已经说过啦~ 题目给出了两种解法，一种是用递归做，另一种嘛，自然是非递归啦，
我们先来讲讲递归的做法（代码与分析如下所示）
-
首先是两个 if 语句；
（1）如果 m==1 ,返回 n ；因为只有一个鸡蛋，所以我们只能从一层往上试，最坏的情况就是试 n 次。
（2） 如果 n==0 ,便返回0；因为根本就没有楼层啊！
-
接着，把 ret 定义成无穷大，备用。
-
然后，我们扔出一个鸡蛋：
如果鸡蛋没有碎，那么对应的是 f(n - i, m)，也就是说我们可以去更高的楼层试一试鸡蛋会不会碎，m不减去一 是因为鸡蛋没有碎,所以可以拿回来继续用。
但鸡蛋若是碎了，那么对应的便是 f(i - 1, m - 1)，也就是说我们不仅要下降一层去试验，鸡蛋也要减少一个。
-
最后，用 max 求出鸡蛋碎与不碎中耗费鸡蛋数的最大值，再与， ret 求最少耗费的鸡蛋数，得出结论。（当然，若本次鸡蛋碎了，那也算耗费了一个鸡蛋，所以 max 后面要加 1 ）。
int f(int n, int m)
{
if (m == 1) return n;
if (n == 0) return 0;
int ret = numeric_limits<int>::max();
for (int i = 1; i <= n; i++)
ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
return ret;
}下面是第二种方法：
int g(int n, int m)
{
for (int i = 1; i <= n; i++)
h[i][1] = i;
for (int j = 1; j <= m; j++)
h[0][j] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 2; j <= m; j++)
{
h[i][j] = numeric_limits<int>::max();
for (int k = 1; k <= i; k++)
h[i][j] = min(h[i][j] , max(h[i - k][j], h[k - 1][j - 1]) + 1);
}
}
return h[n][m];
}代码我就不多介绍了，
思路和上面的差不多，只是把递归改成循环了而已（自己理解吧~）
好了，下面我把完整代码放剪贴板里了
有兴趣的可以自己去看看
完整代码
老师还和我们讨论了当输入为“7 3”时，
ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
一共运行了几次。
答案是448次。
原因我就不解释了，因为我马上要下课了，来不及解释了，拜拜~~
2023.8.20