據(jù)說是google的面試題，看誰的快

yzc2002

Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n.  

For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?  

翻譯過來大體是這樣：
有一個整數(shù)n,寫一個函數(shù)f(n),返回0到n之間出現(xiàn)的"1"的個數(shù)。比如f(13)=6,現(xiàn)在f(1)=1,問此后最大的f(n)=n的n是什么？

f(13)=6是 因為1,2,3,4,5,6,7,8,9,10,11,12,13.中'1'的個數(shù)，正好是6.

我寫了一個，用了不到一秒的時間
結(jié)果如下：

1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
200000
200001
1599981
1599982
1599983
1599984
1599985
1599986
1599987
1599988
1599989
1599990
2600000
2600001
13199998
35000000
35000001
35199981
35199982
35199983
35199984
35199985
35199986
35199987
35199988
35199989
35199990
35200000
35200001
117463825
500000000
500000001
500199981
500199982
500199983
500199984
500199985
500199986
500199987
500199988
500199989
500199990
500200000
500200001
501599981
501599982
501599983
501599984
501599985
501599986
501599987
501599988
501599989
501599990
502600000
502600001
513199998
535000000
535000001
535199981
535199982
535199983
535199984
535199985
535199986
535199987
535199988
535199989
535199990
535200000
535200001
1111111110

[ 本帖最后由 yzc2002 于 2006-3-29 17:09 編輯 ]

converse

關(guān)注ing...大哥把代碼拿出來showshow吧

cellar

俺地DD就是強，思考中...

bleem1998

寫了個偽的
大伙指正

1. 
   
2. //計算一個整數(shù)里還有多少個1，有幾個返回幾
   
3. int num_a_int(int papapa)
   
4. {
   
5.         //這個函數(shù)對誰來說都easy吧
   
6.         return 0;
   
7. }
   
8. 
   
9. //這個函數(shù)就是題目里要求的那個函數(shù)f了，利用num_a_int做遞歸
   
10. int f(int zzz)
    
11. {
    
12.         int ret = 0;
    
13. 
    
14.         if (zzz < 0)
    
15.                 return 0;
    
16. 
    
17.         ret += f(zzz - 1);
    
18. 
    
19.         return ret + num_a_int(zzz);
    
20. }
    

復(fù)制代碼

yzc2002

原帖由 converse 于 2006-3-29 11:51 發(fā)表
關(guān)注ing...大哥把代碼拿出來showshow吧

代碼倒是很簡單的，但解釋起來很費勁，不解釋又不可能看得懂
還是先想想吧~~

[ 本帖最后由 yzc2002 于 2006-3-29 12:40 編輯 ]

mingjwan

厲害,速度好快啊.

liubaochen

樓主可以貼下代碼嗎？ 好像不對啊

有一個整數(shù)n,寫一個函數(shù)f(n),返回0到n之間出現(xiàn)的"1"的個數(shù)。比如f(13)=6,現(xiàn)在f(1)=1,問下一個最大的f(n)=n的n是什么？

返回 f(a)=b 且當(dāng) a＝＝b的時， a＝？是嗎？

設(shè)n的位數(shù)為m  0~n之間1的個數(shù)為u
m和u的關(guān)系是  10^(n-1)*(9)^0+.....10^(n-n)*(9)^(n-1)
當(dāng)m是1時(是1位數(shù)) u=1 = 10^0*9^0
當(dāng)m是2時（兩位數(shù)）u=19 = 10^1 + 10^0*9^0
當(dāng)m是3時     u=271 = 10^2+10^1*9^1+10^0*9^2
.....
當(dāng)m〉10 （大于10位）時 u會趕上n


所以樓主的199981有問題啊

蘇蓉蓉

原帖由 liubaochen 于 2006-3-29 14:16 發(fā)表
樓主可以貼下代碼嗎？ 好像不對啊



返回 f(a)=b 且當(dāng) a＝＝b的時， a＝？是嗎？

設(shè)n的位數(shù)為m  0~n之間1的個數(shù)為u
m和u的關(guān)系是  10^(n-1)*(9)^0+.....10^(n-n)*(9)^(n-1)
當(dāng)m是1時(是1位數(shù)) u=1 = 10 ...

你 搞錯了吧？
f(19)=12
f(271)=158
有規(guī)律倒是真的，其實這個題目考的是一個算法，而不是編程技巧。

mingjwan

樓主的答案沒有問題的,我用最土的方法,結(jié)果跟樓主是一樣的,就是速度太慢了.

yzc2002

原帖由 liubaochen 于 2006-3-29 14:16 發(fā)表
設(shè)n的位數(shù)為m  0~n之間1的個數(shù)為u
m和u的關(guān)系是  10^(n-1)*(9)^0+.....10^(n-n)*(9)^(n-1)

這個關(guān)系你是怎么得出來的?應(yīng)該是不對的.
10^(n-1)*(9)^0+.....10^(n-n)*(9)^(n-1)=10^(n-1)(1+9/10+...+(9/10)^(n-1))=10^n-9^n
如f(99)=20而不是19