google的一道面试题。

当然，我知道，如果只是计算到199981的话，就没有意思了。

嗯，就是，就是，其实都有很大的关系（后一个位与前一位的关系,例如：0到999与0到99有很大的关系），可以以10的次方跳跃。所以能省N多的时间和处理。

如果要求从0到n每个数字的f(n)都算出来，不妨试试下面的
fs(n) = 数字n本身含有1的个数
f(0) = 0
f(n+1) = f(n) + fs(n+1)
单算某一个数n效率很低，但是从0算到n时间的话速度就快了，主要取决于fs(n)计算数字n本身含有1的个数的时间。再加上跳跃，还能更快。

这题的关键其实不是计算 f(n) ，这个是简单的。真正在降低计算时间上作用巨大的是剪枝，也就是说如果把那么多数字看作一棵搜索树上的节点的话，如何知道哪些分支子树是不用去检查判断的，否则无论怎么做也快不起来。

这是我后来想说的。讲得十分对。但在这里上面详细的计算方法，是起到很关键的作用的。

设g(k)是数ｋ中１的个数
f(n) = sum(0<=k<=n) g(k)
= sum(0<=k<n+1) g(k)

f(10n+9) = sum(0<=k<10(n+1)) g(k)
= sum(0<=k<n+1) (g(10k)+g(10k+1)+...+g(10k+9))
= sum(0<=k<n+1) (10g(k)+1)
= sum(0<=k<n+1) 10g(k) + sum(0<=k<n+1) 1
= 10 f(n) + n+1

package test.thinkinjava;

import java.util.Calendar;

/**
* @author NEUSOFT.wangyu
*/
public class TestGoogle{

int xx = 0;
int result = 1;

public static void main(String[] args){
TestGoogle instance = new TestGoogle();
instance.run2();
}

public void run2(){
Calendar c = Calendar.getInstance();
long aa = c.getTimeInMillis();
for(int i = 2;i<Integer.MAX_VALUE;i++){
int num = i;
while(num > 0){
xx = num;
num = num / 10 ;
if((xx - num*10) == 1){
result++;
}
}
//System.out.println("i= "+i+"result = "+result);
if(result == i){
System.out.println("result num ="+i);
break;
}
if(i == (Integer.MAX_VALUE -10)){
System.out.println("out of range !");
}
}

Calendar b = Calendar.getInstance();
long bb = b.getTimeInMillis();
System.out.println(bb-aa);

}

}

f(13)=6 那么下一个 f(n)=n 的最大的n是多少？
呵呵，有点拗口。
不过很同意大法师所说的，这个算法的关键是剪枝.

public static void main(String[] args) {
// TODO Auto-generated method stub
TestMain test=new TestMain();

Calendar startCalendar = Calendar.getInstance();
long start = startCalendar.getTimeInMillis();
// start count time
long nums=1;
for(long n=2;n<=400000000;n++) {
//int nums=0;
nums+=test.getNumbersOfOne(String.valueOf(n));

if(nums==n) {
System.out.println(nums);
break;
}

}
System.out.println("run end...");
Calendar endCalendar = Calendar.getInstance();
long end = endCalendar.getTimeInMillis();
System.out.println(end-start);

}

//
public long getNumbersOfOne(String strNum) {
int nums=0;
for(int i=0,len=strNum.length();i<len;i++) {
char a=strNum.charAt(i);
if(a=='1') nums++;
}
return nums;
}

}
计算到199981，用了63ms
其实我的getNumbersOfOne（）方法还可以在改进。。。。
我的思路很简单，当计算f(n)=f(n-1)+getNumbersOfOne(n)
其中getNumbersOfOne用来计算n中包含1的个数；
因为我不懂剪枝算法，我只能这种简单的思想了。。。。

我们将数x表示成 head*10(n)+tail;
如：x=1234 , 则表示为 1* 10(3) + 234;
f(1234) = 1 * f(99) + 235 + f(234);
不用我解释吧
234 = 2 * 10(2) + 34;
f(234) = 2 * f(99) + 100 + f(34);
从1到234，有两次 f(99) ,从 100 到 199 共有100个1， 从 200到234 的 1的总和  = f(34)

可以得出：
对于数x，
如果x<10
f(x) = x>=1 ? 1 : 0;
如果head = 1
f(x) = head * f(10(n) - 1) + f(tail) + tail+1
如果head > 1
f(x) = head * f(10(n) - 1) + f(tail) + 10(n);

根据这个公式我们可以迅速的求出f(x），而如果用getCountOfOne（long number)，只能得到某数中1的个数，对于从1到n的值，必须使用循环相加的方法，如果计算，123456789的值的话，就需要循环 123456789次，即便剪枝，也不能减少多少循环次数， 而用这个公式，写个递归方法，可以很快的算出答案。

但仍然有个问题：
如何证明满足f(n)=n的n是最大的n？