[临时] 我的抛玻璃算法 [转]

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

暴力求解，输出 9 22 34 45 55 64 72 79 85 90 94 97 99 100，代码如下：
#include <iostream>
#include <utility>
#include <algorithm>

int main( void )
{
    std::pair<size_t,size_t> 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 <iostream>

size_t foo( size_t n )
{
    for( size_t i=1; i<n; ++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;
    }
}

转自 周星星BLOG