据说是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?  

翻译过来大体是这样：
有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问此后最大的f(n)=n的n是什么？

f(13)=6是 因为1,2,3,4,5,6,7,8,9,10,11,12,13.中'1'的个数，正好是6.

我写了一个，用了不到一秒的时间
结果如下：

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

关注ing...大哥把代码拿出来showshow吧

cellar

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

bleem1998

写了个伪的
大伙指正

1. 
   
2. //计算一个整数里还有多少个1，有几个返回几
   
3. int num_a_int(int papapa)
   
4. {
   
5.         //这个函数对谁来说都easy吧
   
6.         return 0;
   
7. }
   
8. 
   
9. //这个函数就是题目里要求的那个函数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. }
    

复制代码

yzc2002

原帖由 converse 于 2006-3-29 11:51 发表
关注ing...大哥把代码拿出来showshow吧

代码倒是很简单的，但解释起来很费劲，不解释又不可能看得懂
还是先想想吧~~

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

mingjwan

厉害,速度好快啊.

liubaochen

楼主可以贴下代码吗？ 好像不对啊

有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么？

返回 f(a)=b 且当 a＝＝b的时， a＝？是吗？

设n的位数为m  0~n之间1的个数为u
m和u的关系是  10^(n-1)*(9)^0+.....10^(n-n)*(9)^(n-1)
当m是1时(是1位数) u=1 = 10^0*9^0
当m是2时（两位数）u=19 = 10^1 + 10^0*9^0
当m是3时     u=271 = 10^2+10^1*9^1+10^0*9^2
.....
当m〉10 （大于10位）时 u会赶上n


所以楼主的199981有问题啊

苏蓉蓉

原帖由 liubaochen 于 2006-3-29 14:16 发表
楼主可以贴下代码吗？ 好像不对啊



返回 f(a)=b 且当 a＝＝b的时， a＝？是吗？

设n的位数为m  0~n之间1的个数为u
m和u的关系是  10^(n-1)*(9)^0+.....10^(n-n)*(9)^(n-1)
当m是1时(是1位数) u=1 = 10 ...

你 搞错了吧？
f(19)=12
f(271)=158
有规律倒是真的，其实这个题目考的是一个算法，而不是编程技巧。

mingjwan

楼主的答案没有问题的,我用最土的方法,结果跟楼主是一样的,就是速度太慢了.

yzc2002

原帖由 liubaochen 于 2006-3-29 14:16 发表
设n的位数为m  0~n之间1的个数为u
m和u的关系是  10^(n-1)*(9)^0+.....10^(n-n)*(9)^(n-1)

这个关系你是怎么得出来的?应该是不对的.
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