Chinaunix首页 | 论坛 | 博客
  • 博客访问: 913997
  • 博文数量: 158
  • 博客积分: 4380
  • 博客等级: 上校
  • 技术积分: 2367
  • 用 户 组: 普通用户
  • 注册时间: 2006-09-21 10:45
文章分类

全部博文(158)

文章存档

2012年(158)

我的朋友

分类: C/C++

2012-11-23 15:05:00

问题:
有一幢100层高的大楼,给你两个完全相同的玻璃棋子。
假设从某一层开始,丢下玻璃棋子就会破碎。那么怎么利用手中的两颗棋子,
用一种什么样的最优策略,知道这个临界的层高呢?

暴力求解,输出 9 22 34 45 55 64 72 79 85 90 94 97 99 100,代码如下:
#include
#include
#include

int main( void )
{
    std::pair x[101] = { std::make_pair(0,0) };

    for( size_t i=1; i<=100; ++i )
    {
        size_t min_depth = 100;
        size_t m = 0;
        for( size_t j=1; j<=i; ++j )
        {
            size_t cur_depth = std::max(j-1,x[i-j].second);
            if( cur_depth < min_depth )
            {
                min_depth = cur_depth;
                m = j;
            }
        }
        x[i] = std::make_pair(m,min_depth+1);
    }

    size_t base = 0;
    for( size_t m=100; m>0; )
    {
        std::cout << base+x[m].first << ' ';
        base += x[m].first;
        m -= x[m].first;
    }

    return 0;
}

根据上述代码中的x值的规律编写代码,输出 9 22 34 45 55 64 72 79 85 90 94 97 99 100,代码如下:
#include

size_t foo( size_t n )
{
    for( size_t i=1; i    {
        n -= i;
    }
    return n;
}
int main( void )
{
    size_t base = 0;
    for( size_t n=100; n>0; )
    {
        size_t m = foo(n);
        std::cout << base+m << ' ';
        base += m;
        n -= m;
    }
}

阅读(1795) | 评论(11) | 转发(0) |
给主人留下些什么吧!~~

网友评论2012-11-23 15:06:52

start2046
以前没看明白,今天从其他地方看了这个问题,才晓得为什么选择1 2 3 4 5 6 7 8 9 10 11 12 13。因为1累加到14是105,刚好大于100。
感觉星星有些过于注重编程技巧了,如果在之前对算法进行适当的分析会更好的。

网友评论2012-11-23 15:06:44

一个咸蛋的唠叨
就前两个数而言,我感觉11、22比9、22更为合理啊

网友评论2012-11-23 15:06:36

周星星
因为题目要求是“用一种什么样的最优策略,知道这个临界的层高呢?”
而不是“随便用一种策略,知道这个临界的层高呢?”

用我算出来的方法,平均只要十几次,最差情况下也只要十几次,而你的方法平均要50次,最差情况下要100次。

网友评论2012-11-23 15:06:29

poptang
那为什么不从一开始就从一楼抛呢,非得算出来个9?

网友评论2012-11-23 15:06:22

conry
呵呵,看来我是钻牛角尖了,就想着九层碎了在八层试,没想着下到一楼再从第一层到第八层依次抛下去试