快的原因应该是这一段吧：

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
不用一个个地遍历
建议换一个f(n),这个好像更快：
def f(n):
    s=str(n)
    l=len(s)
    sum=0
    p,q=10**l,10**(l-1)
    while p>1:
        n1,n2=n/p,n%p
        sum += n1*q
        if n2>=2*q: sum+=q
        elif n2>=q: sum+=n2%q+1
    p/=10
    q/=10
    return sum

BTW:
不过其实题目不是只要求净可能短吗：）
def f1():
    n,sum=1,1
    while 1:
        if n==sum:yield n
        n+=1
        sum+=str(n).count('1')
呵呵

还写了一个，仿照时钟的运行方法，每转到1的时候起变化
def Clock():
    l=(0,1,0,0,0, 0,0,0,0,0)
    c=None
    i,j=1,0
    while 1:
        yield l[i]+j
        i=(i+1)%10
        if not i:
            if not c:
                c=clock()
            j = c.next()
   
def f2():
    n,sum=0,0
    c=clock()
    while 1:
        if n==sum:yield n
        n+=1
        sum+=c.next() 

运行速度都比较慢，不过好理解



-----原始邮件-----
发件人:"魏忠" 
发送时间:2006-01-08 19:07:43
收件人:python-chinese at lists.python.cn
抄送:(无)
主题:Re: [python-chinese] Re: 再出一道给初学者的题


老兄的代码果真飞快!
俺的慢代码是这样的:

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/20060109/bfa1a071/attachment.htm