有关google题目的陷阱

在有关google的一道题目上已有不少人在讨论

其实，大家都被这道题目开了一道玩笑。。

原题：

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.

题目是有极限的，而最大的数一般是溢出整型数的范围的。。

不过，google的题目目的就在开发考生的思维，所以答案开阔有很多思想。。

单单就f(n)的计算方法就很多，我想以此引出讨论，先看看有没有更一般的算法。。。

结果我会慢慢公布。。哈哈。。。有兴趣的多讨论。。。

评论

4 楼 baibai326 2007-04-18  

不错，经楼主指点，恍然大悟，谢谢分享

3 楼 mjy304122 2007-04-18  

后半部分还没给出。。。
后面的更精彩。。。
哈哈。。。

2 楼 solospider 2007-04-17  

顶，被迷惑了，关注点放到前半部分，其实这个问题完全不需要那么复杂的。
不过找出规律还是蛮难得，赞一个。

1 楼 mjy304122 2007-04-17  

我就不再卖关子了。。。。。。。
既然，很多人都还停留在追求所谓速度上。。。。
对于2进制
f(1)=1,f(10)=10 就再没有符合了
3进制
f(1)=1,f(11)=11,f(12)=12,f(110)=110
4进制
符合的有
1，121，122，123，130，200，201，1110
。。。。。。。
。。。。。。。
十进制最后的就是f(1111111110)=1111111110

还有以下是求f(n)的方法count(n)是直接算的。。。
对任何进制可用，2进制的话q=q*2，当然除也是除十。。。
绝对比以上的求f(n)的方法快，当然还可以再加工一下
还有最主要的如何提高遍历的速度，就是楼主说的剪枝（我人为我的方法也不能称为剪枝）
我用了很简单的思想以后再说。。。。。
当然，为什么1111111110是最大，这是函数变化率的问题，大家朝这个方向想想就明白了。

time=0;
q=1;
public int count(int n){
clear();
num=n;
tem1=n;
temp(n);
while(tem1!=0){
q=q*10;
temp(tem1);
}


//System.out.print(time);
//System.out.println();
//System.out.println();
return time;
}
private void temp(int n){
int a=n/10;
int b=n%10;
tem1=a;

time=time+a*q;
if(b>1)
time=time+q;
else if(b==1)
time=time+num%q+b;

}