据说这道题来自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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20060107/0f8b83ed/attachment.html

魏忠 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

在 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)

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

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.htm

老兄的代码速度很快,但俺没有看懂.能再加点注释么?
在俺的机器上,你的代码
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.html

我想他的代码是不是直接算出比这个数小的数中所有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
>
>

用google groups回的帖成了乱码，只好再来过

我的思路：
1. f(n)可以直接计算，用一些排列组合计数，
计算复杂度O(log(n)**3)次乘法
2. 主程序选择一些n来尝试，看什么时候f(n)开始大于或等于n，
我的尝试是跳着来的－如果n>f(n)，下一个就尝试n+(n-f(n))
3. 如果跳过头了，用二分查找收缩到那一点

把我代码里面的print注释去掉，可以看到跳跃过程；
实际上第三步没有用上

BTW，这是我的第一个python程序，写得不精简，见笑了
那个xrange()能不能简单介绍一下，谢谢

-- 
   regards,
yzhh

老兄的数据结构学得相当扎实,佩服佩服
第一个python程序就写这么好,再次佩服
range函数生成一个list,每次调用range都要动态分配内存.
xrange生成一个迭代器,就是只有用那个数时才临时通过计算提供值.这样节省内存(看上去效率没有list高,但当数比较大时,反而节省cpu时间)
我没有正经学过数据结构,但是在python in a nutshell 一书中提到
range(a,b,c) is O((b-a)/c). xrange(a,b,c) is O(1), but looping on xrange's
result is O((b-a)/c).
btw,老兄平常用什么im工具?

在06-1-8，yzhh <yezonghui at gmail.com> 写道：
>
> 用google groups回的帖成了乱码，只好再来过
>
> 我的思路：
> 1. f(n)可以直接计算，用一些排列组合计数，
> 计算复杂度O(log(n)**3)次乘法
> 2. 主程序选择一些n来尝试，看什么时候f(n)开始大于或等于n，
> 我的尝试是跳着来的－如果n>f(n)，下一个就尝试n+(n-f(n))
> 3. 如果跳过头了，用二分查找收缩到那一点
>
> 把我代码里面的print注释去掉，可以看到跳跃过程；
> 实际上第三步没有用上
>
> BTW，这是我的第一个python程序，写得不精简，见笑了
> 那个xrange()能不能简单介绍一下，谢谢
>
> --
>    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/825da26a/attachment.htm

让你说的我都不好意思了，呵呵
你怎么认定我的年纪比你大呢，兄才:)
QQ(LumaQQ)和MSN(KOpete)我都用，QQ用的多一些

-- 
   regards,
yzhh

>     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))

这部分代码也许可以改成：
count = d * ( 10 ** (d-1) )

我的算法。

计算从1..n里面，有多少个数个位数为1，有多少个数10位数为1，...
然后加起来

由于频繁使用了对象，因此效率惨不忍睹，但是算法还是很清楚的

def ToWeiShuList(n):
	lst = []
	power = 1
	while n / power != 0 :
		lst.append(WeiShu(n, power))
		power *= 10
	return lst

class WeiShu(object) :
	def __init__(self, n, power ) :
		self.before = n / (power * 10)
		self.digit  = n / power % 10
		self.after  = n % power
		self.power  = power
	def value(self) :
		base = self.before * self.power
		if self.digit >= 2:
			return base + self.power
       		if self.digit == 0 :
			return base
		if self.digit == 1 :
       			return base + self.after + 1

def ones(n) :
	l = ToWeiShuList(n)
	return sum(i.value() for i in l)

if __name__ == "__main__" :
    i = 2
    while ones(i) != i :
        i += 1
    print i




On 1/8/06, 李晓锋 <leexiaofeng at gmail.com> wrote:
> >     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))
>
> 这部分代码也许可以改成：
> count = d * ( 10 ** (d-1) )
>
> _______________________________________________
> 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
>
>

On 1/7/06, 魏忠 <weizhong2004 at gmail.com> wrote:
> 据说这道题来自google的面试：
> 已知：
> f(1)=1
> f(10)=2
> f(11)=4
> f(n)表示从1到n的全部整数中1这个数字出现的次数
> 写一个尽可能短的程序，计算出下一次f(n)=n时，n等于多少
> 分析清楚之后，用python实现很容易。忙累了的高手也可以休息一下试试哦！

原来还有这样的题，尽量短吗？可以这样
>>> for n in xrange(2,10000000):
...   if n == reduce(lambda x,y:x+y, [len([d for d in str(i) if
d=='1']) for i in xrange(1,n+1)]): print n; break

这段代码短倒是短了，可执行效率嘛……不知道要让人等多长时间。心急的可以直接这样：
>>> for n in xrange(199980,10000000):
...   if n == reduce(lambda x,y:x+y, [len([d for d in str(i) if
d=='1']) for i in xrange(1,n+1)]):print n;break

对我的算法作了一下修改，放弃对象，直接用函数，速度提高了一个数量级

我的算法的复杂度是logN

def f(n, power) :
    before = n / (power * 10)
    digit  = n / power % 10
    after  = n % power
    base = before * power
    if digit >= 2 :
        return base + power
    if digit == 0 :
        return base
    if digit == 1 :
        return base + after + 1
	
def ones(n) :
    power = 1
    result = 0
    while n / power != 0 :
        result += f(n, power)
        power *= 10
    return result

if __name__ == "__main__" :
    import time
    start = time.time()
    i = 2
    while ones(i) != i :
        i += 1
    print i
    print time.time() - start



On 1/9/06, Xie Yanbo <xieyanbo at gmail.com> wrote:
> On 1/7/06, 魏忠 <weizhong2004 at gmail.com> wrote:
> > 据说这道题来自google的面试：
> > 已知：
> > f(1)=1
> > f(10)=2
> > f(11)=4
> > f(n)表示从1到n的全部整数中1这个数字出现的次数
> > 写一个尽可能短的程序，计算出下一次f(n)=n时，n等于多少
> > 分析清楚之后，用python实现很容易。忙累了的高手也可以休息一下试试哦！
>
> 原来还有这样的题，尽量短吗？可以这样
> >>> for n in xrange(2,10000000):
> ...   if n == reduce(lambda x,y:x+y, [len([d for d in str(i) if
> d=='1']) for i in xrange(1,n+1)]): print n; break
>
> 这段代码短倒是短了，可执行效率嘛……不知道要让人等多长时间。心急的可以直接这样：
> >>> for n in xrange(199980,10000000):
> ...   if n == reduce(lambda x,y:x+y, [len([d for d in str(i) if
> d=='1']) for i in xrange(1,n+1)]):print n;break
>
> _______________________________________________
> 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
>
>

shhgs <shhgs.efhilt at gmail.com> writes:

> 对我的算法作了一下修改，放弃对象，直接用函数，速度提高了一个数量级
>
> 我的算法的复杂度是logN
>

你这个log(N)指的是计算f(n)的复杂度吧。算上main里面的循环，总体求解的复
杂度是N*log(N)。

可能乘除法用得比较多，好象总体耗时也比较多。

我这里提供另一个思路。显然f(n)可以通过是递推求得

f(n) = f(n-1) + g(n) 其中g(n)为n中1的个数。

g(n)可以用log10(N)的算法求

def count_digit(n): # count the digit '1' in n
    count = 0
    while n > 0:
        if n % 10 == 1:
            count += 1
        n /= 10
    return count

那么用递推定义，总体求解也只需要 N*log10(N)

def solve():
    total = 1 # f(2) = 1
    n = 2
    while total != n:
        n += 1
        total += count_digit(n)
    print "f(%d) = %d" % (n, total)

另外，g(n)也可以递推计算

n末位是0的时候，g(n+1) = g(n)+1
n末位是1的时候，g(n+1) = g(n)-1
n末位是2-8的时候，g(n+1) = g(n)

n末位是9的时候，由于n+1会进位，1的数目变化比较复杂，直接用count_digit计
算比较方便。

那么solve()可以改写，减少90%的count_digit()的调用次数。这样，在速度和代
码简洁性上，效果都不错。


> def f(n, power) :
>     before = n / (power * 10)
>     digit  = n / power % 10
>     after  = n % power
>     base = before * power
>     if digit >= 2 :
>         return base + power
>     if digit == 0 :
>         return base
>     if digit == 1 :
>         return base + after + 1
> 	
> def ones(n) :
>     power = 1
>     result = 0
>     while n / power != 0 :
>         result += f(n, power)
>         power *= 10
>     return result
>
> if __name__ == "__main__" :
>     import time
>     start = time.time()
>     i = 2
>     while ones(i) != i :
>         i += 1
>     print i
>     print time.time() - start
>
>
>
> On 1/9/06, Xie Yanbo <xieyanbo at gmail.com> wrote:
>> On 1/7/06, 魏忠 <weizhong2004 at gmail.com> wrote:
>> > 据说这道题来自google的面试：
>> > 已知：
>> > f(1)=1
>> > f(10)=2
>> > f(11)=4
>> > f(n)表示从1到n的全部整数中1这个数字出现的次数
>> > 写一个尽可能短的程序，计算出下一次f(n)=n时，n等于多少
>> > 分析清楚之后，用python实现很容易。忙累了的高手也可以休息一下试试哦！
>>
>> 原来还有这样的题，尽量短吗？可以这样
>> >>> for n in xrange(2,10000000):
>> ...   if n == reduce(lambda x,y:x+y, [len([d for d in str(i) if
>> d=='1']) for i in xrange(1,n+1)]): print n; break
>>
>> 这段代码短倒是短了，可执行效率嘛……不知道要让人等多长时间。心急的可以直接这样：
>> >>> for n in xrange(199980,10000000):
>> ...   if n == reduce(lambda x,y:x+y, [len([d for d in str(i) if
>> d=='1']) for i in xrange(1,n+1)]):print n;break
>>


-- 
Regards,
Feng Ye

难道Google要的是这个解法？

def f(n) :
    return str(n).count('1')

if __name__ == "__main__" :
    all = 1
    i = 2
    while all != i :
        i += 1
        all += f(i)
    print i

多简单


On 1/9/06, Feng Ye <yef at 163.com> wrote:
> shhgs <shhgs.efhilt at gmail.com> writes:
>
> > 对我的算法作了一下修改，放弃对象，直接用函数，速度提高了一个数量级
> >
> > 我的算法的复杂度是logN
> >
>
> 你这个log(N)指的是计算f(n)的复杂度吧。算上main里面的循环，总体求解的复
> 杂度是N*log(N)。
>
> 可能乘除法用得比较多，好象总体耗时也比较多。
>
> 我这里提供另一个思路。显然f(n)可以通过是递推求得
>
> f(n) = f(n-1) + g(n) 其中g(n)为n中1的个数。
>
> g(n)可以用log10(N)的算法求
>
> def count_digit(n): # count the digit '1' in n
>     count = 0
>     while n > 0:
>         if n % 10 == 1:
>             count += 1
>         n /= 10
>     return count
>
> 那么用递推定义，总体求解也只需要 N*log10(N)
>
> def solve():
>     total = 1 # f(2) = 1
>     n = 2
>     while total != n:
>         n += 1
>         total += count_digit(n)
>     print "f(%d) = %d" % (n, total)
>
> 另外，g(n)也可以递推计算
>
> n末位是0的时候，g(n+1) = g(n)+1
> n末位是1的时候，g(n+1) = g(n)-1
> n末位是2-8的时候，g(n+1) = g(n)
>
> n末位是9的时候，由于n+1会进位，1的数目变化比较复杂，直接用count_digit计
> 算比较方便。
>
> 那么solve()可以改写，减少90%的count_digit()的调用次数。这样，在速度和代
> 码简洁性上，效果都不错。
>
>
> > def f(n, power) :
> >     before = n / (power * 10)
> >     digit  = n / power % 10
> >     after  = n % power
> >     base = before * power
> >     if digit >= 2 :
> >         return base + power
> >     if digit == 0 :
> >         return base
> >     if digit == 1 :
> >         return base + after + 1
> >
> > def ones(n) :
> >     power = 1
> >     result = 0
> >     while n / power != 0 :
> >         result += f(n, power)
> >         power *= 10
> >     return result
> >
> > if __name__ == "__main__" :
> >     import time
> >     start = time.time()
> >     i = 2
> >     while ones(i) != i :
> >         i += 1
> >     print i
> >     print time.time() - start
> >
> >
> >
> > On 1/9/06, Xie Yanbo <xieyanbo at gmail.com> wrote:
> >> On 1/7/06, 魏忠 <weizhong2004 at gmail.com> wrote:
> >> > 据说这道题来自google的面试：
> >> > 已知：
> >> > f(1)=1
> >> > f(10)=2
> >> > f(11)=4
> >> > f(n)表示从1到n的全部整数中1这个数字出现的次数
> >> > 写一个尽可能短的程序，计算出下一次f(n)=n时，n等于多少
> >> > 分析清楚之后，用python实现很容易。忙累了的高手也可以休息一下试试哦！
> >>
> >> 原来还有这样的题，尽量短吗？可以这样
> >> >>> for n in xrange(2,10000000):
> >> ...   if n == reduce(lambda x,y:x+y, [len([d for d in str(i) if
> >> d=='1']) for i in xrange(1,n+1)]): print n; break
> >>
> >> 这段代码短倒是短了，可执行效率嘛……不知道要让人等多长时间。心急的可以直接这样：
> >> >>> for n in xrange(199980,10000000):
> >> ...   if n == reduce(lambda x,y:x+y, [len([d for d in str(i) if
> >> d=='1']) for i in xrange(1,n+1)]):print n;break
> >>
>
>
> --
> Regards,
> Feng Ye
>
> _______________________________________________
> 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
>

我怀疑yzhh的逼近算法是不是严密

第一，是不是存在两个i == f(i)的区间，会不会一下子跳到后面一个区间
第二，就我的验证199981,199982, ....199989都符合i == f(i),如果n2乘的时候一下子跑到比方说199984，它能不能校正


On 1/9/06, shhgs <shhgs.efhilt at gmail.com> wrote:
> 难道Google要的是这个解法？
>
> def f(n) :
>     return str(n).count('1')
>
> if __name__ == "__main__" :
>     all = 1
>     i = 2
>     while all != i :
>         i += 1
>         all += f(i)
>     print i
>
> 多简单
>
>
> On 1/9/06, Feng Ye <yef at 163.com> wrote:
> > shhgs <shhgs.efhilt at gmail.com> writes:
> >
> > > 对我的算法作了一下修改，放弃对象，直接用函数，速度提高了一个数量级
> > >
> > > 我的算法的复杂度是logN
> > >
> >
> > 你这个log(N)指的是计算f(n)的复杂度吧。算上main里面的循环，总体求解的复
> > 杂度是N*log(N)。
> >
> > 可能乘除法用得比较多，好象总体耗时也比较多。
> >
> > 我这里提供另一个思路。显然f(n)可以通过是递推求得
> >
> > f(n) = f(n-1) + g(n) 其中g(n)为n中1的个数。
> >
> > g(n)可以用log10(N)的算法求
> >
> > def count_digit(n): # count the digit '1' in n
> >     count = 0
> >     while n > 0:
> >         if n % 10 == 1:
> >             count += 1
> >         n /= 10
> >     return count
> >
> > 那么用递推定义，总体求解也只需要 N*log10(N)
> >
> > def solve():
> >     total = 1 # f(2) = 1
> >     n = 2
> >     while total != n:
> >         n += 1
> >         total += count_digit(n)
> >     print "f(%d) = %d" % (n, total)
> >
> > 另外，g(n)也可以递推计算
> >
> > n末位是0的时候，g(n+1) = g(n)+1
> > n末位是1的时候，g(n+1) = g(n)-1
> > n末位是2-8的时候，g(n+1) = g(n)
> >
> > n末位是9的时候，由于n+1会进位，1的数目变化比较复杂，直接用count_digit计
> > 算比较方便。
> >
> > 那么solve()可以改写，减少90%的count_digit()的调用次数。这样，在速度和代
> > 码简洁性上，效果都不错。
> >
> >
> > > def f(n, power) :
> > >     before = n / (power * 10)
> > >     digit  = n / power % 10
> > >     after  = n % power
> > >     base = before * power
> > >     if digit >= 2 :
> > >         return base + power
> > >     if digit == 0 :
> > >         return base
> > >     if digit == 1 :
> > >         return base + after + 1
> > >
> > > def ones(n) :
> > >     power = 1
> > >     result = 0
> > >     while n / power != 0 :
> > >         result += f(n, power)
> > >         power *= 10
> > >     return result
> > >
> > > if __name__ == "__main__" :
> > >     import time
> > >     start = time.time()
> > >     i = 2
> > >     while ones(i) != i :
> > >         i += 1
> > >     print i
> > >     print time.time() - start
> > >
> > >
> > >
> > > On 1/9/06, Xie Yanbo <xieyanbo at gmail.com> wrote:
> > >> On 1/7/06, 魏忠 <weizhong2004 at gmail.com> wrote:
> > >> > 据说这道题来自google的面试：
> > >> > 已知：
> > >> > f(1)=1
> > >> > f(10)=2
> > >> > f(11)=4
> > >> > f(n)表示从1到n的全部整数中1这个数字出现的次数
> > >> > 写一个尽可能短的程序，计算出下一次f(n)=n时，n等于多少
> > >> > 分析清楚之后，用python实现很容易。忙累了的高手也可以休息一下试试哦！
> > >>
> > >> 原来还有这样的题，尽量短吗？可以这样
> > >> >>> for n in xrange(2,10000000):
> > >> ...   if n == reduce(lambda x,y:x+y, [len([d for d in str(i) if
> > >> d=='1']) for i in xrange(1,n+1)]): print n; break
> > >>
> > >> 这段代码短倒是短了，可执行效率嘛……不知道要让人等多长时间。心急的可以直接这样：
> > >> >>> for n in xrange(199980,10000000):
> > >> ...   if n == reduce(lambda x,y:x+y, [len([d for d in str(i) if
> > >> d=='1']) for i in xrange(1,n+1)]):print n;break
> > >>
> >
> >
> > --
> > Regards,
> > Feng Ye
> >
> > _______________________________________________
> > 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
> >
>

shhgs <shhgs.efhilt at gmail.com> writes:

> 难道Google要的是这个解法？

呵呵，显然重要的不是解法，是解决问题的思路，算法优化的能力。

我觉得这个题目还是不错的，有很多种思路。既可以从数学方面下手，寻找通式
，也可以对不太满意的算法进行各种优化。

>
> def f(n) :
>     return str(n).count('1')
>
> if __name__ == "__main__" :
>     all = 1
>     i = 2
>     while all != i :
>         i += 1
>         all += f(i)
>     print i
>
> 多简单
>
>

-- 
Regards,
Feng Ye

兼职赚钱网站，看看：http://www.myetone.com
Best & Regards

Adam Tang
Myetone info.tech. Co.,Ltd.
Tel: (021)53852321-801
Fax:(021)53852320
Mail: tangyuejun at myetone.com
Msn:online4u8 at hotmail.com
Skype:tangyuejun
Address: 403 Room,18 Xizang Road(M) 
Ganglu Plaza Shanghai,China
Post Code: 200001

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20060110/4479ee17/attachment.htm

shhgs的问题问的好，二分查找不能应付n1,n2之间有多个解的情况（只能找到某一个）
我正在寻找其他搜索方法
另外昨晚穷举的办法尝试了2到10**12之间的所有数，找到好多解：
199981~199990, 200000, 200001, 1599981~1599990, 2600000, 2600001,
13199998
35000000, 35000001, 35199981~35199981, 35200000, ...
117463825
500000000, 500000001, 500199981, ...
1111111110
没列举完，没有耐心等到结束了

我希望能找到一个快的算法，能从小到大列举全部的解
（可以证明解的个数是有限的，当n的数量级是10**m且m>100时，
f(n) > m*(10**(m-1)) > 100*(10**(m-1)) == 10**(m+1) > n.
m*(10*(m-1))是1到10**m-1(m个9那个数)中间出现的'1'的个数）

shhgs wrote:

> 我怀疑yzhh的逼近算法是不是严密
> 
> 第一，是不是存在两个i == f(i)的区间，会不会一下子跳到后面一个区间
> 第二，就我的验证199981,199982, ....199989都符合i ==
> f(i),如果n2乘的时候一下子跑到比方说199984，它能不能校正
> 

李晓锋 wrote:

>>     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))
> 
> 这部分代码也许可以改成：
> count = d * ( 10 ** (d-1) )

wonderful!
-- 
   regards,
yzhh

递推g(n)的时候个位是9不用单独算，这个算法实际就是从个位开始找到一个不是9的数字，是0就加1，是1就减1
while True:
    r = n % 10
    if r == 9:
        n = n / 10
        continue
    elif r == 0: g = g + 1
    elif r == 1: g = g - 1
    break



另外，g(n)也可以递推计算

n末位是0的时候，g(n+1) = g(n)+1
n末位是1的时候，g(n+1) = g(n)-1
n末位是2-8的时候，g(n+1) = g(n)

n末位是9的时候，由于n+1会进位，1的数目变化比较复杂，直接用count_digit计
算比较方便。



2006/1/10, Feng Ye <yef at 163.com>:
>
> shhgs <shhgs.efhilt at gmail.com> writes:
>
> > 对我的算法作了一下修改，放弃对象，直接用函数，速度提高了一个数量级
> >
> > 我的算法的复杂度是logN
> >
>
> 你这个log(N)指的是计算f(n)的复杂度吧。算上main里面的循环，总体求解的复
> 杂度是N*log(N)。
>
> 可能乘除法用得比较多，好象总体耗时也比较多。
>
> 我这里提供另一个思路。显然f(n)可以通过是递推求得
>
> f(n) = f(n-1) + g(n) 其中g(n)为n中1的个数。
>
> g(n)可以用log10(N)的算法求
>
> def count_digit(n): # count the digit '1' in n
>    count = 0
>    while n > 0:
>        if n % 10 == 1:
>            count += 1
>        n /= 10
>    return count
>
> 那么用递推定义，总体求解也只需要 N*log10(N)
>
> def solve():
>    total = 1 # f(2) = 1
>    n = 2
>    while total != n:
>        n += 1
>        total += count_digit(n)
>    print "f(%d) = %d" % (n, total)
>
> 另外，g(n)也可以递推计算
>
> n末位是0的时候，g(n+1) = g(n)+1
> n末位是1的时候，g(n+1) = g(n)-1
> n末位是2-8的时候，g(n+1) = g(n)
>
> n末位是9的时候，由于n+1会进位，1的数目变化比较复杂，直接用count_digit计
> 算比较方便。
>
> 那么solve()可以改写，减少90%的count_digit()的调用次数。这样，在速度和代
> 码简洁性上，效果都不错。
>
>
> > def f(n, power) :
> >     before = n / (power * 10)
> >     digit  = n / power % 10
> >     after  = n % power
> >     base = before * power
> >     if digit >= 2 :
> >         return base + power
> >     if digit == 0 :
> >         return base
> >     if digit == 1 :
> >         return base + after + 1
> >
> > def ones(n) :
> >     power = 1
> >     result = 0
> >     while n / power != 0 :
> >         result += f(n, power)
> >         power *= 10
> >     return result
> >
> > if __name__ == "__main__" :
> >     import time
> >     start = time.time()
> >     i = 2
> >     while ones(i) != i :
> >         i += 1
> >     print i
> >     print time.time() - start
> >
> >
> >
> > On 1/9/06, Xie Yanbo <xieyanbo at gmail.com> wrote:
> >> On 1/7/06, 魏忠 <weizhong2004 at gmail.com> wrote:
> >> > 据说这道题来自google的面试：
> >> > 已知：
> >> > f(1)=1
> >> > f(10)=2
> >> > f(11)=4
> >> > f(n)表示从1到n的全部整数中1这个数字出现的次数
> >> > 写一个尽可能短的程序，计算出下一次f(n)=n时，n等于多少
> >> > 分析清楚之后，用python实现很容易。忙累了的高手也可以休息一下试试哦！
> >>
> >> 原来还有这样的题，尽量短吗？可以这样
> >> >>> for n in xrange(2,10000000):
> >> ...   if n == reduce(lambda x,y:x+y, [len([d for d in str(i) if
> >> d=='1']) for i in xrange(1,n+1)]): print n; break
> >>
> >> 这段代码短倒是短了，可执行效率嘛……不知道要让人等多长时间。心急的可以直接这样：
> >> >>> for n in xrange(199980,10000000):
> >> ...   if n == reduce(lambda x,y:x+y, [len([d for d in str(i) if
> >> d=='1']) for i in xrange(1,n+1)]):print n;break
> >>
>
>
> --
> Regards,
> Feng Ye
>
> _______________________________________________
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.exoweb.net/pipermail/python-chinese/attachments/20060110/f7791db0/attachment-0001.html