我觉得还是魏忠的好一点，起码代码清楚，重要的是符合题意

在06-1-8，python-chinese-request at lists.python.cn <
python-chinese-request at lists.python.cn> 写道：
>
> Send python-chinese mailing list submissions to
>        python-chinese at lists.python.cn
>
> To subscribe or unsubscribe via the World Wide Web, visit
>        http://python.cn/mailman/listinfo/python-chinese
> or, via email, send a message with subject or body 'help' to
>        python-chinese-request at lists.python.cn
>
> You can reach the person managing the list at
>        python-chinese-owner at lists.python.cn
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of python-chinese digest..."
>
>
> Today's Topics:
>
>   1. Re: ?????????? (yzhh)
>   2. Re: ?????????? (???)
>   3. Re: Re: ?????????? (??)
>   4. Re: Re: ?????????? (??)
>   5. Re: Re: ?????????? (???)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Sun, 08 Jan 2006 18:04:27 +0800
> From: yzhh <yezonghui at gmail.com>
> Subject: [python-chinese] Re: ??????????
> To: python-chinese at lists.python.cn
> Message-ID: 1 at sea.gmane.org>
> Content-Type: text/plain; charset=gb2312
>
> 魏忠 wrote:
>
> > 据说这道题来自google的面试：
> > 已知：
> > f(1)=1
> > f(10)=2
> > f(11)=4
> > f(n)表示从1到n的全部整数中1这个数字出现的次数
> > 写一个尽可能短的程序，计算出下一次f(n)=n时，n等于多少
> > 分析清楚之后，用python实现很容易。忙累了的高手也可以休息一下试试哦！
> >
> > 这里给出答案：199981
> > D:\py>python -m profile f11.py
> > 答案是:199981
> >          199985 function calls in 1.582 CPU seconds
> >
> > 开飞机的舒克
> > http://www.lvye.org/shuke
> > msn:weizhong at netease.com
>
> 这是我的代码，比较快，请指教
>
> def fac(n):
>    """Comput factorial of n"""
>    r = 1
>    i = 1
>    while (i<=n):
>        r *= i
>        i += 1
>    return r
>
> def C(n,m):
>    """Comput combinatory: select m from n"""
>    return fac(n)/(fac(m)*fac(n-m))
>
> def f(n):
>    if n == 0:
>        return 0
>
>    d = 0
>    m = 1
>    while m <= n :
>        m *= 10
>        d += 1
>    m /= 10
>    d -= 1  #now m == 10**d <= n < 10**(d+1)
>
>    count = 0
>    for i in range(1,d+1):
>        #count += No. of '1's where there is i occurrence of '1' in a
> number
>        count += i * C(d,i) * (9 **(d-i))
>    r = (n / m) * count
>    if (n / m ) == 1:
>        r += n - m + 1
>    else:
>        r += m
>    r += f(n%m)
>    return r
>
> #import pdb
> #pdb.set_trace()
>
> n2 = 2
> while n2 > f(n2):
>    n2 += n2 - f(n2)
> #    print "f(" + str(n2) + ") = " + str(f(n2))
> n1 = n2 / 2
> n = n2
> while (n != f(n)):
>    n = (n1 + n2) / 2
>    if n > f(n):
>        n1 = n
>    else:
>        n2 = n
> #    print "f(" + str(n) + ") = " + str(f(n))
>
> print n
> --
>   regards,
> yzhh
>
>
>
> ------------------------------
>
> Message: 2
> Date: Sun, 8 Jan 2006 11:05:02 +0000
> From: ??? <leexiaofeng at gmail.com>
> Subject: Re: [python-chinese] ??????????
> To: python-chinese at lists.python.cn
> Message-ID: <87af76540601080305o28798527i at mail.gmail.com>
> Content-Type: text/plain; charset=GB2312
>
> 在 06-1-7，魏忠<weizhong2004 at gmail.com> 写道：
> > 据说这道题来自google的面试：
> > 已知：
> > f(1)=1
> > f(10)=2
> > f(11)=4
> > f(n)表示从1到n的全部整数中1这个数字出现的次数
> > 写一个尽可能短的程序，计算出下一次f(n)=n时，n等于多少
> > 分析清楚之后，用python实现很容易。忙累了的高手也可以休息一下试试哦！
> >
> > 这里给出答案：199981
> > D:\py>python -m profile f11.py
> > 答案是:199981
> >          199985 function calls in 1.582 CPU seconds
> >
> 一个非常蹩脚的实现，验证了你的答案，请指教
> #!/usr/bin/env python
> def howmany1( n ):
>        count = 0
>        while(n != 0 ):
>                r = n % 10
>                n = n / 10
>                if( r != 1 ):
>                        continue
>                count += 1
>
>        return count
>
> def f11(n):
>        count = 0
>        while(n>0):
>                count += howmany1(n)
>                n -= 1
>        return count
>
> print f11(199981)
>
> ------------------------------
>
> Message: 3
> Date: Sun, 8 Jan 2006 19:07:43 +0800
> From: ?? <weizhong2004 at gmail.com>
> Subject: Re: [python-chinese] Re: ??????????
> To: python-chinese at lists.python.cn
> Message-ID: <acd2ebf20601080307h29b513c5p at mail.gmail.com>
> Content-Type: text/plain; charset="gb2312"
>
> 老兄的代码果真飞快!
> 俺的慢代码是这样的:
>
> result=[1]
> temp=1
> x=2
> while True:
>   jg=str(x).count('1')+temp
>   if jg==x:print x;break;
>   x+=1
>   temp=jg
>
>
> 在06-1-8，yzhh <yezonghui at gmail.com> 写道：
> >
> > 魏忠 wrote:
> >
> > > 据说这道题来自google的面试：
> > > 已知：
> > > f(1)=1
> > > f(10)=2
> > > f(11)=4
> > > f(n)表示从1到n的全部整数中1这个数字出现的次数
> > > 写一个尽可能短的程序，计算出下一次f(n)=n时，n等于多少
> > > 分析清楚之后，用python实现很容易。忙累了的高手也可以休息一下试试哦！
> > >
> > > 这里给出答案：199981
> > > D:\py>python -m profile f11.py
> > > 答案是:199981
> > >          199985 function calls in 1.582 CPU seconds
> > >
> > > 开飞机的舒克
> > > http://www.lvye.org/shuke
> > > msn:weizhong at netease.com
> >
> > 这是我的代码，比较快，请指教
> >
> > def fac(n):
> >     """Comput factorial of n"""
> >     r = 1
> >     i = 1
> >     while (i<=n):
> >         r *= i
> >         i += 1
> >     return r
> >
> > def C(n,m):
> >     """Comput combinatory: select m from n"""
> >     return fac(n)/(fac(m)*fac(n-m))
> >
> > def f(n):
> >     if n == 0:
> >         return 0
> >
> >     d = 0
> >     m = 1
> >     while m <= n :
> >         m *= 10
> >         d += 1
> >     m /= 10
> >     d -= 1  #now m == 10**d <= n < 10**(d+1)
> >
> >     count = 0
> >     for i in range(1,d+1):
> >         #count += No. of '1's where there is i occurrence of '1' in a
> > number
> >         count += i * C(d,i) * (9 **(d-i))
> >     r = (n / m) * count
> >     if (n / m ) == 1:
> >         r += n - m + 1
> >     else:
> >         r += m
> >     r += f(n%m)
> >     return r
> >
> > #import pdb
> > #pdb.set_trace()
> >
> > n2 = 2
> > while n2 > f(n2):
> >     n2 += n2 - f(n2)
> > #    print "f(" + str(n2) + ") = " + str(f(n2))
> > n1 = n2 / 2
> > n = n2
> > while (n != f(n)):
> >     n = (n1 + n2) / 2
> >     if n > f(n):
> >         n1 = n
> >     else:
> >         n2 = n
> > #    print "f(" + str(n) + ") = " + str(f(n))
> >
> > print n
> > --
> >    regards,
> > yzhh
> >
> > _______________________________________________
> > python-chinese
> > Post: send python-chinese at lists.python.cn
> > Subscribe: send subscribe to python-chinese-request at lists.python.cn
> > Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> > Detail Info: http://python.cn/mailman/listinfo/python-chinese
> >
>
>
>
> --
>
> 开飞机的舒克
> http://www.lvye.org/shuke
> msn:weizhong at netease.com
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL:
> http://lists.exoweb.net/pipermail/python-chinese/attachments/20060108/038989f6/attachment-0001.htm
>
> ------------------------------
>
> Message: 4
> Date: Sun, 8 Jan 2006 19:28:42 +0800
> From: ?? <weizhong2004 at gmail.com>
> Subject: Re: [python-chinese] Re: ??????????
> To: python-chinese at lists.python.cn
> Message-ID: <acd2ebf20601080328i70c8f6bfp at mail.gmail.com>
> Content-Type: text/plain; charset="gb2312"
>
> 老兄的代码速度很快,但俺没有看懂.能再加点注释么?
> 在俺的机器上,你的代码
> D:\py>python -m profile f112.py
> 199981
>         8557 function calls (7799 primitive calls) in 0.118 CPU seconds
> 当俺将你代码中的 range函数改为 xrange 之后,性能又提高了将近一倍
>
>
> 在06-1-8，yzhh <yezonghui at gmail.com> 写道：
> >
> > 魏忠 wrote:
> >
> > > 据说这道题来自google的面试：
> > > 已知：
> > > f(1)=1
> > > f(10)=2
> > > f(11)=4
> > > f(n)表示从1到n的全部整数中1这个数字出现的次数
> > > 写一个尽可能短的程序，计算出下一次f(n)=n时，n等于多少
> > > 分析清楚之后，用python实现很容易。忙累了的高手也可以休息一下试试哦！
> > >
> > > 这里给出答案：199981
> > > D:\py>python -m profile f11.py
> > > 答案是:199981
> > >          199985 function calls in 1.582 CPU seconds
> > >
> > > 开飞机的舒克
> > > http://www.lvye.org/shuke
> > > msn:weizhong at netease.com
> >
> > 这是我的代码，比较快，请指教
> >
> > def fac(n):
> >     """Comput factorial of n"""
> >     r = 1
> >     i = 1
> >     while (i<=n):
> >         r *= i
> >         i += 1
> >     return r
> >
> > def C(n,m):
> >     """Comput combinatory: select m from n"""
> >     return fac(n)/(fac(m)*fac(n-m))
> >
> > def f(n):
> >     if n == 0:
> >         return 0
> >
> >     d = 0
> >     m = 1
> >     while m <= n :
> >         m *= 10
> >         d += 1
> >     m /= 10
> >     d -= 1  #now m == 10**d <= n < 10**(d+1)
> >
> >     count = 0
> >     for i in range(1,d+1):
> >         #count += No. of '1's where there is i occurrence of '1' in a
> > number
> >         count += i * C(d,i) * (9 **(d-i))
> >     r = (n / m) * count
> >     if (n / m ) == 1:
> >         r += n - m + 1
> >     else:
> >         r += m
> >     r += f(n%m)
> >     return r
> >
> > #import pdb
> > #pdb.set_trace()
> >
> > n2 = 2
> > while n2 > f(n2):
> >     n2 += n2 - f(n2)
> > #    print "f(" + str(n2) + ") = " + str(f(n2))
> > n1 = n2 / 2
> > n = n2
> > while (n != f(n)):
> >     n = (n1 + n2) / 2
> >     if n > f(n):
> >         n1 = n
> >     else:
> >         n2 = n
> > #    print "f(" + str(n) + ") = " + str(f(n))
> >
> > print n
> > --
> >    regards,
> > yzhh
> >
> > _______________________________________________
> > python-chinese
> > Post: send python-chinese at lists.python.cn
> > Subscribe: send subscribe to python-chinese-request at lists.python.cn
> > Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> > Detail Info: http://python.cn/mailman/listinfo/python-chinese
> >
>
>
>
> --
>
> 开飞机的舒克
> http://www.lvye.org/shuke
> msn:weizhong at netease.com
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL:
> http://lists.exoweb.net/pipermail/python-chinese/attachments/20060108/507404fc/attachment-0001.html
>
> ------------------------------
>
> Message: 5
> Date: Sun, 8 Jan 2006 11:36:29 +0000
> From: ??? <leexiaofeng at gmail.com>
> Subject: Re: [python-chinese] Re: ??????????
> To: python-chinese at lists.python.cn
> Message-ID: <87af76540601080336t535eef15w at mail.gmail.com>
> Content-Type: text/plain; charset=GB2312
>
> 我想他的代码是不是直接算出比这个数小的数中所有1的个数，而不是一个一个加起来。
>
> 在 06-1-8，魏忠<weizhong2004 at gmail.com> 写道：
> > 老兄的代码速度很快,但俺没有看懂.能再加点注释么?
> > 在俺的机器上,你的代码
> > D:\py>python -m profile f112.py
> > 199981
> >          8557 function calls (7799 primitive calls) in 0.118 CPU seconds
> > 当俺将你代码中的 range函数改为 xrange 之后,性能又提高了将近一倍
> >
> >
> >  在06-1-8，yzhh <yezonghui at gmail.com> 写道：
> > > 魏忠 wrote:
> > >
> > > > 据说这道题来自google的面试：
> > > > 已知：
> > > > f(1)=1
> > > > f(10)=2
> > > > f(11)=4
> > > > f(n)表示从1到n的全部整数中1这个数字出现的次数
> > > > 写一个尽可能短的程序，计算出下一次f(n)=n时，n等于多少
> > > > 分析清楚之后，用python实现很容易。忙累了的高手也可以休息一下试试哦！
> > > >
> > > > 这里给出答案：199981
> > > > D:\py>python -m profile f11.py
> > > > 答案是:199981
> > > >          199985 function calls in 1.582 CPU seconds
> > > >
> > > > 开飞机的舒克
> > > > http://www.lvye.org/shuke
> > > > msn:weizhong at netease.com
> > >
> > > 这是我的代码，比较快，请指教
> > >
> > > def fac(n):
> > >     """Comput factorial of n"""
> > >     r = 1
> > >     i = 1
> > >     while (i<=n):
> > >         r *= i
> > >         i += 1
> > >     return r
> > >
> > > def C(n,m):
> > >     """Comput combinatory: select m from n"""
> > >     return fac(n)/(fac(m)*fac(n-m))
> > >
> > > def f(n):
> > >     if n == 0:
> > >         return 0
> > >
> > >     d = 0
> > >     m = 1
> > >     while m <= n :
> > >         m *= 10
> > >         d += 1
> > >     m /= 10
> > >     d -= 1  #now m == 10**d <= n < 10**(d+1)
> > >
> > >     count = 0
> > >     for i in range(1,d+1):
> > >         #count += No. of '1's where there is i occurrence of '1' in a
> > number
> > >         count += i * C(d,i) * (9 **(d-i))
> > >     r = (n / m) * count
> > >     if (n / m ) == 1:
> > >         r += n - m + 1
> > >     else:
> > >         r += m
> > >     r += f(n%m)
> > >     return r
> > >
> > > #import pdb
> > > #pdb.set_trace()
> > >
> > > n2 = 2
> > > while n2 > f(n2):
> > >     n2 += n2 - f(n2)
> > > #    print "f(" + str(n2) + ") = " + str(f(n2))
> > > n1 = n2 / 2
> > > n = n2
> > > while (n != f(n)):
> > >     n = (n1 + n2) / 2
> > >     if n > f(n):
> > >         n1 = n
> > >     else:
> > >         n2 = n
> > > #    print "f(" + str(n) + ") = " + str(f(n))
> > >
> > > print n
> > > --
> > >    regards,
> > > yzhh
> > >
> > > _______________________________________________
> > > python-chinese
> > > Post: send python-chinese at lists.python.cn
> > > Subscribe: send subscribe to
> > python-chinese-request at lists.python.cn
> > > Unsubscribe: send unsubscribe to
> > python-chinese-request at lists.python.cn
> > > Detail Info:
> > http://python.cn/mailman/listinfo/python-chinese
> > >
> >
> >
> >
> > --
> >
> >
> > 开飞机的舒克
> >  http://www.lvye.org/shuke
> > msn:weizhong at netease.com
> > _______________________________________________
> > python-chinese
> > Post: send python-chinese at lists.python.cn
> > Subscribe: send subscribe to
> > python-chinese-request at lists.python.cn
> > Unsubscribe: send unsubscribe to
> > python-chinese-request at lists.python.cn
> > Detail Info:
> > http://python.cn/mailman/listinfo/python-chinese
> >
> >
>
> ------------------------------
>
> _______________________________________________
> python-chinese mailing list
> python-chinese at lists.python.cn
> http://python.cn/mailman/listinfo/python-chinese
>
> End of python-chinese Digest, Vol 25, Issue 38
> **********************************************
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20060109/25abdc64/attachment-0001.html