要么改变世界,要么适应世界

双蛋问题

2020-03-22 16:09:00
208
目录

昨天看了李永乐老师的视频,想着利用编程实现,想着想着就动起手来了。

问题描述

你有两个鸡蛋,楼层有一百层,这座楼有一个临界点,即从高于(含该楼层)高楼层往下扔鸡蛋,鸡蛋会碎,低于

该楼层,无论扔几次都不会碎(~~忽略物理因素),问你最少需要尝试几次,一定可以确定该临界楼层。

解法一

一层一层地尝试,最好的情况下只需仍一次,最坏的情况是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;
}
历史评论
开始评论