鸡蛋跳楼

realnumber

鸡蛋跳楼
(egg.pas/cpp/c)
【题目描述】
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N  共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
【输入格式】
        共一行，两个正数K和N
【输出格式】
        最坏情况下确定F需要移动的次数
【样例输入1】
1 2
【样例输出1】
2
【样例输入2】
2 6
【样例输出2】
3
【数据范围】
1<=K<=100,
1<=N<=10000。
【样例1说明】
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。如果它没碎，那么我们肯定知道 F = 2 。因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

realnumber

比如 k=1,n=10,那么从1楼开始实验，最坏情况下需要10次.
又鸡蛋数量足够，k>=[$log_2n$]+1，似乎是二分法;
不够的话，k=1只能从底层逐层检验，k>=2 ,怎么设置规则？            
比如k=2,n=61

2个鸡蛋，61层楼
方案一：选第31层，破的话，需要从第一层逐层检验，最坏是在第30层，需要31次才能够检验出来.
方案二：选取第3层掉落，未破，继续选第6层，再未破，继续选第9层，...这样，最坏情况是在第60层，需要22次才能够检验出来.
方案三：选取第8层掉落，依次16，24，....最坏情况是在第56层，需要7+7=14次才能检验出来.
方案四：选取第7层掉落，依次14，21，..最坏情况是在第56层，需要8+6=14次
方案五：选第10层...需要6+9=15次
...这样看起来14次才是最优的.

2个鸡蛋，1000层楼
方案一：依次8层，最坏需要125+7=132次
方案二：依次50层，最坏需要20+49=69次
方案三：依次32层，最坏需要31+31=62次.

猜测：2个鸡蛋，n层  最优策略，依次选取$\sqrt{n}$层，最坏需要约$2\sqrt{n}$

3个鸡蛋？
3个蛋1000层
方案一：依次100层，最坏10+20-1=29次
方案二：依次81层，最坏12+18-1=29次
方案三：依次400层，最坏2+40-1=41次
方案四：依次t层，最坏$\frac{n}{t}+2\sqrt{t}$,在$t=n^{\frac{2}{3}}$时取最小，但前提是假设选点有固定位置.

realnumber

和小朋友探讨后，发现选点不是固定的，而是一个等差数列
比如2个鸡蛋，66楼
方案：第一次选11楼，第二次21楼，第三次30楼，依次38，45，51，56，
60，63，65，66
最坏是11次

应该是这个了，小朋友编的
#include<stdio.h>
#include<algorithm>
using namespace std;
  
int f[105],ans;
  
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    while(f[k]<n){
        for( int i=k;i>0;i-- ) f=f+f[i-1]+1; \\为什么代码会变掉？
        ans++;
    }
    printf("%d",ans);
    return 0;
}

kuing

回复 3# realnumber

\\为什么代码会变掉？

因为［i］是论坛内的斜体标记。
要想避免这种情况的发生，在贴代码时要点击界面上的代码按钮再粘贴，生成像下面这样东西：

1. #include<stdio.h>
2. #include<algorithm>
3. using namespace std;
4.   
5. int f[105],ans;
6.   
7. int main(){
8.     int n,k;
9.     scanf("%d%d",&n,&k);
10.     while(f[k]<n){
11.         for( int i=k;i>0;i-- ) f[i]=f[i]+f[i-1]+1; \\为什么代码会变掉？
12.         ans++;
13.     }
14.     printf("%d",ans);
15.     return 0;
16. }

复制代码

包括之前这帖 kuing.cjhb.site/forum.php?mod=redirect&goto=findpost&ptid=6515&pid=33479 也存在这个问题，是我把你的帖子编辑了。

realnumber

en

hbghlyj

charlesliuyx.github.io/2018/10/11/【直观算法】Egg Puzzle 鸡蛋难题/