| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3682 人关注过本帖
标题:鸡蛋问题
只看楼主 加入收藏
wangfengLLD
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2007-11-6
收藏
得分:0 

1、要保证鸡蛋的硬度能被正确测量出来,则当只有一个鸡蛋是,只能从第一楼开始一层一层的测。
2、当有两个鸡蛋时,则用二分法原则先测一下第50层,若鸡蛋破了,则只剩下一个鸡蛋,又要从第一楼开始慢慢测。
若鸡蛋在第50层没破,则再测一下第75层,若破了,则用另一个鸡蛋从第51层开始慢慢的测。
若鸡蛋在75层没破,则继续下去......
3、当有三个鸡蛋时......


nothing is impossible
2007-11-21 10:50
chmlqw
Rank: 1
等 级:新手上路
帖 子:180
专家分:0
注 册:2007-10-11
收藏
得分:0 
以下是引用wangfengLLD在2007-11-21 10:50:26的发言:

1、要保证鸡蛋的硬度能被正确测量出来,则当只有一个鸡蛋是,只能从第一楼开始一层一层的测。
2、当有两个鸡蛋时,则用二分法原则先测一下第50层,若鸡蛋破了,则只剩下一个鸡蛋,又要从第一楼开始慢慢测。
若鸡蛋在第50层没破,则再测一下第75层,若破了,则用另一个鸡蛋从第51层开始慢慢的测。
若鸡蛋在75层没破,则继续下去......
3、当有三个鸡蛋时......

按照这个说法,对于第一个例子:100,2
最坏情况就是 先用2分法测第一层,然后鸡蛋破了。所以第二个只能从第一层开始,那最坏情况就是49 了?
答案怎么是14,哪个高手解释一下

2007-11-21 11:18
心剑菩提
Rank: 1
等 级:新手上路
帖 子:249
专家分:0
注 册:2007-5-17
收藏
得分:0 
希望大家指点
希望大家指点

前世五百次的回眸 才换来今生的擦肩而过
2007-11-29 08:25
cmydd
Rank: 1
等 级:新手上路
帖 子:20
专家分:0
注 册:2007-11-28
收藏
得分:0 
呵呵 我来答
还好哈 我学了点数学   我来说说 你们看说的对不哈  先说1个鸡蛋  10层吧   要是10次吧  要是第一层就破了    和你说的那2个鸡蛋和100层的2分法50层就破了不是一个性质么  所以 你们这样想是错的  第一个50层破了 另外还有一个就从1开始一个一个试  算一次   然后第二次还是有2个鸡蛋  是吧   从25开始 第2次  在13开始就是第3次 然后7开始4次 4开始5次  然后2开始 6次   然后1是最后一次 也就是说7次 他只是说在最坏的情况下  也就是说考虑破的时候   以50为界 50下为7次  50上也是7次  一起14次   你们所说的49是不对的  一10为例子吧     他只是一破来说的    一起测10次  也就是说  从10层破   一次  9层破 2次  8层破3次                            最后到1层破 10次  中间你们并没考虑他要是不破的情况吧  
我就是这样想的 说的不对  还希望谅解    新手
2007-11-29 14:19
leeco
Rank: 4
等 级:贵宾
威 望:10
帖 子:1029
专家分:177
注 册:2007-5-10
收藏
得分:0 
题目的描述有一些问题,比如,如果第一层掉下来就破裂了,硬度是否算为0?楼层是从0开始算起还是从1层开始算起?如果一个10层楼,在第10层掉下来仍然没有破裂那么硬度就无法测量出来,这种情况怎么算?
2007-11-29 18:19
心剑菩提
Rank: 1
等 级:新手上路
帖 子:249
专家分:0
注 册:2007-5-17
收藏
得分:0 
输入3 96
输出9

前世五百次的回眸 才换来今生的擦肩而过
2007-11-30 18:25
leeco
Rank: 4
等 级:贵宾
威 望:10
帖 子:1029
专家分:177
注 册:2007-5-10
收藏
得分:0 
连输入数据的范围都没给嘛?
那我怎么判断是预处理还是用滚动数组处理每个case
2007-11-30 19:04
wjcloudy
Rank: 1
来 自:辽宁大连
等 级:新手上路
帖 子:44
专家分:0
注 册:2007-11-6
收藏
得分:0 
回复 8# 的帖子
回去好好考虑考虑
2007-11-30 19:14
leeco
Rank: 4
等 级:贵宾
威 望:10
帖 子:1029
专家分:177
注 册:2007-5-10
收藏
得分:0 
程序代码:
/*
f[0][h]=INF ;f[0][0]=0;
f[n][h]=min{ max{f[n-1][h1-1],f[n][h-h1]}+1 ,h1=1,2,...,h }
*/
#include <stdio.h>

#define INF 1000000
#define max(x,y) ((x)>(y)?(x):(y))

int _f[2][100001];
struct {
    int* operator [] (int i){
        return _f[i&1];
    }    
}f;    

int main()
{
    int N,H;
    while(scanf("%d%d",&N,&H)!=EOF){
        int res=-1;
        for(int h=0;h<=H;h++){
            f[0][h]=INF;
        }
        f[0][0]=0;
        for(int n=1;n<=N;n++){
            f[n][0]=0;
            for(int h=1;h<=H;h++){
                f[n][h]=INF;
                for(int h1=1;h1<=h;h1++){
                    f[n][h]<?=max(f[n-1][h1-1],f[n][h-h1])+1;
                }
            }    
            if(n>=f[n][H]){
                res=f[n][H];
                break;
            }    
        }
        printf("%d\n",(res!=-1?res:f[N][H]));
    }    
}
2007-11-30 19:30
心剑菩提
Rank: 1
等 级:新手上路
帖 子:249
专家分:0
注 册:2007-5-17
收藏
得分:0 
这些是什么意思?
struct {
    int* operator [] (int i){
        return _f[i&1];
    }   
}f;   


f[n][h]<?=max(f[n-1][h1-1],f[n][h-h1])+1;

printf("%d\n",(res!=-1?res:f[N][H]));
你能不能改的易懂一些

前世五百次的回眸 才换来今生的擦肩而过
2007-12-06 15:06
快速回复:鸡蛋问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.041125 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved