双蛋问题
昨天看了李永乐老师的视频,想着利用编程实现,想着想着就动起手来了。
问题描述
你有两个鸡蛋,楼层有一百层,这座楼有一个临界点,即从高于(含该楼层)高楼层往下扔鸡蛋,鸡蛋会碎,低于
该楼层,无论扔几次都不会碎(~~忽略物理因素),问你最少需要尝试几次,一定可以确定该临界楼层。
解法一
一层一层地尝试,最好的情况下只需仍一次,最坏的情况是100次,即答案是在[1,100],即最终答案是100次。
解法二
二分法,即第一个鸡蛋我不从第一层开始,我从第50(100的一半)层开始,要是鸡蛋碎了,临界楼层就在[1,50]之间,接着用解法一的方式去尝试;要是不碎,说明临界楼层就在[51,100]之间,继续从75层开始,然后又会出现两种情况,重复上述过程。即第一个鸡蛋是用于确定区间,第二个鸡蛋是用于确定临界楼层。在这种情况下最坏情况下需要1+49=50次,最好的情况是8次(依次扔的楼层是50,75,87,93,96,98,99,100),即答案是在[8,50],最终答案是50.
解法三
经过上面的尝试,我们发现,最坏情况下和最好情况下,需要的次数跨度太大了,我们可以不可以尝试着一种方案,使得最坏和最好的情况下使用次数相差最小呢?如何做到相差最小呢?那我只要两个鸡蛋所需扔的次数之和趋向于一个常数,就可以了。假设第一个鸡蛋第一次在第n层扔,假如鸡蛋碎了,第二个鸡蛋最坏情况需要扔n-1次,总次数是(1+n-1)次;假如没碎,第一个鸡蛋就可以再选择一个楼层来确定区间,那选哪一层呢?答案是第[n+(n-1)]层,假如碎了,第二个鸡蛋就从第n层开始往上寻找答案,最坏情况需要仍n-2次,即总次数是[2+(n-2)]次;假如没碎,第一个鸡蛋接着从第[n+(n-1)+(n-2)]层开始扔,重复上述过程,最坏情况下是:第一个鸡蛋扔的楼层是n,n-1,n-2,n-3,……,1,只需要[n+(n-1)+(n-2)+……+1]>=100,将求得的n向下求整即可,此时n=14。即最终答案是14,即14次尝试,一定可以确定该临界值。
普遍化
假如楼层数是m,鸡蛋数是n呢,对于某一个组合(m,n),怎样快速地得到答案呢?我们可以先画出一张表
下面是楼层数m,右边是鸡蛋数n | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
1 | 1 | 1 | 1 | 1 | 1 |
2 | 2 | ||||
3 | 3 | ||||
4 | 4 | ||||
5 | 5 | ||||
6 | 6 |
对于最左边和最上边,我们很容易可以填好,对于其他情况呢?设T(m,n)表示拥有n个蛋,需要确定m层楼的临界层的最小尝试次数。假设手上的第一个鸡蛋在第k层楼扔
- 假如碎了,相当于鸡蛋少了,临界楼层在第k层下面,需要的次数就是{T(k-1,n-1)+1}
- 假如不碎,相当于手上的鸡蛋数没变,而且需要确定的楼层数也减少了,答案就是{T(m-k,n)+1}
对于这两种情况,要么是使得鸡蛋数减少了,要么使得楼层数减少了,二者的取值有可能不一样,为了确保一定能确定出来,我们取最大值,我们记为Tk 。那k的取值又该如何选择呢?我们不难发现,k可以从1取到m,都会对应一个Tk ,我们只要选出最小的值即可。有同学可能会疑问,上面是选择最大值,这里为什么选择最小值呢?是因为这里的k是我们自己选择的,但是选好了k后,鸡蛋碎不碎我们无法预测,因此上面选择最大值,这里选择最小值。因此状态转移方程就是
T(m,n)= min(Tk ,k=1,2,3,……,m,Tk={max[T(m,n-1),T(m-k,n)]+1}
因此填表的方式就是以列为主序,从上往下,下面给出代码
/*
* @Description:
* @Author: Yale_Xin
* @Date: 2020-03-22 15:44:41
* @LastEditTime: 2020-03-22 15:56:36
* @LastEditors: Yale_Xin
*/
#include <stdio.h>
#define max(a, b) a > b ? a : b
int T[100][100], egg, floor;
int main() {
int m, n, k;
scanf("%d %d", &floor, &egg);
//两个循环用于初始化
for (m = 1; m <= floor; m++) {
T[m][1] = m;
}
for (n = 1; n <= egg; n++) {
T[1][n] = 1;
}
// 填表开始
for (n = 2; n <= egg; n++)
for (m = 2; m <= floor; m++) {
int minTk = 32767, Tk;
for (k = 1; k <= m; k++) {
// 蛋碎了,则还需尝试k-1次,不碎还需m-k次
Tk = max(T[k - 1][n - 1], T[m - k][n]);
Tk++;
minTk = minTk < Tk ? minTk : Tk;
}
T[m][n] = minTk;
}
return 0;
}
本文由「黄阿信」创作,创作不易,请多支持。
如果您觉得本文写得不错,那就点一下「赞赏」请我喝杯咖啡~
商业转载请联系作者获得授权,非商业转载请附上原文出处及本链接。
关注公众号,获取最新动态!