免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
Board logo

标题: [组合] 鸡蛋跳楼 [打印本页]

作者: realnumber    时间: 2019-8-29 15:07     标题: 鸡蛋跳楼

鸡蛋跳楼
(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    时间: 2019-8-29 15:13

本帖最后由 realnumber 于 2019-8-30 10:58 编辑

比如 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    时间: 2019-8-30 11:26

本帖最后由 realnumber 于 2019-8-30 13:47 编辑

和小朋友探讨后,发现选点不是固定的,而是一个等差数列
比如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    时间: 2019-8-30 13:46

回复 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. }
复制代码
包括之前这帖 http://kuing.orzweb.net/redirect ... =6515&pid=33479 也存在这个问题,是我把你的帖子编辑了。
作者: realnumber    时间: 2019-8-30 13:48

en




欢迎光临 悠闲数学娱乐论坛(第2版) (http://kuing.orzweb.net/) Powered by Discuz! 7.2