请教一个python函数的写法

aluoyeshi

想写一个python函数，实现:
有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6 ; f(11)=4

请教一下该怎么写呢？谢谢

chunchengfh

1. #!/usr/bin/python
   
2. 
   
3. def f(i):
   
4.         cnt = 0;
   
5.         for x in range(0, i+1):
   
6.                 cnt += str(x).count('1')
   
7.         return cnt;
   
8. 
   
9. test = [13, 11, 101]
   
10. for x in test:
    
11.         print "f(%d) = %d" %(x, f(x))
    

复制代码

luffy.deng

回复 2# chunchengfh
不用range()

1. def f(i):
   
2.     cnt = 0
   
3.     while i>0:
   
4.         cnt += str(i).count('1')
   
5.         i-=1
   
6.     return cnt
   
7. 
   
8. print f(13)

复制代码

aluoyeshi

多谢，写的都比较简洁，不过如果数字串比较长的话，效率不是很高

luffy.deng

一个个数  N很大的时候肯定慢，得找个好的算法。

洋葱爆鸡

《编程之美》里面专门讨论过这个问题，是有专门的算法的，通过分析n就可以直接得到f(n)的结果，翻译成python：

1. def f(n):
   
2.         iCount=0
   
3.         iFactor=1
   
4.         iLowerNum=0
   
5.         iCurrNum=0
   
6.         iHigherNum=0
   
7.         while(n/iFactor!=0):
   
8.                 iLowerNum=n-(n/iFactor)*iFactor
   
9.                 iCurrNum=(n/iFactor)%10
   
10.                 iHigherNum=n/(iFactor*10)
    
11. 
    
12.                 if iCurrNum==0:
    
13.                         iCount+=iHigherNum*iFactor
    
14.                 elif iCurrNum==1:
    
15.                         iCount+=iHigherNum*iFactor+iLowerNum+1
    
16.                 else:
    
17.                         iCount+=(iHigherNum+1) * iFactor
    
18. 
    
19.                 iFactor*=10
    
20. 
    
21.         return iCount
    
22. 
    
23. print f(11)
    
24. print f(13)
    

复制代码