Re: 答复: [cpp] 一道据说是Google的面试题

[Chen Shuo]

如果这真是一道面试题，需要用纸笔演算的话，倒很适合用递推公式，当然还要有相当的毅力，算到200 000这么大的数。比如：
1~9之间有1个1，那么f(x) = 1 if 1 <= x <= 9
10~19之间，个位有1个1，十位一直是1，那么f(19) = f(9) + 10 + 1 = 12
20~99之间，每10个数有一个1，那么f(99) = f(19) + 8 = 20
100~199之间，百位一直是1，后两位里有f(99)个1，所以f(199) = f(99) + 100 + f(99) = 140
200~999之间，每100个数里有f(99)个1，所以f(999) = f(199)+8*f(99)=300
1000~1999之间，千位一直是1，后三位里有f(999)个一，所以f(1999) = f(999) + 1000 + f(999) = 1600
这样一直算到f(99999) = 50000
那么f(199 999) = f(99 999) + 100 000 + f(99 999) = 200 000，已经接近目标了。
再往前退几个数，发现199 981是满足f(x)=x的第一个数（1除外）。

ps. 要是没有缩进，python程序还真不易看懂。

On 9/18/06, 孟岩 <myan at csdn.net> wrote:
> 我猜想这个题目不是让我们蛮力求解。我想到一个递推公式的解法。不过我喜欢陈硕的
> 这个算法，够Pythonic。
>
>
> -----邮件原件-----
> 发件人: cpp-bounces at codingnow.com [mailto:cpp-bounces at codingnow.com] 代表
> Chen Shuo
> 发送时间: 2006年9月18日 21:45
> 收件人: C++ Discuss Group
> 主题: Re: [cpp] 一道据说是Google的面试题
>
> cnt = 0
> for i in range(1, 200000):
>     str = '%d' % i
>     cnt += str.count('1')
>     if cnt == i and i > 1:
>         print i
>