网上一道google笔试题的答案

写出这样一个函数 ,输入一个 n, 输出从1到这个数字之间的出现的1的个数,比如f(13)等于6; f(9)等于1;
 网上有很多这道题的解法，大多采用穷举法。这把这个算法题变成了程序设计，这道题，我认为是总结一个递推公式，然后用递推法实现，比较好。后来在网上考证了一下，这道题本来也是让总结一个数学函数即可，无需编程。既然写了，就贴出来，发表一下自己的解法。这道题还有另一半,当f(n)＝n是，最小的n是多少？本人还没有好的方法，所以就不贴了。

下面的程序是上半部java实现的。

/* 可以推出下列递推公式:
  * f(n)=(a>1?s:n-s*a+1)+a*f(s-1)+f(n-s*a)当n>9时;
  * L是n的位数
  * a是n的第一位数字
  * s是10的L－1次方
  * n-s*a求的是a后面的数.
  * 公式说明：
  * 求 0-n 由多少个数字1，分三部分，一是所有数中第一位有多少个1，对应(a>1?s:n-s*a+1)
  * 当a大于1是,应该有a的L1次， a小于1是有n-s*a+1。
  * 如n是223 所有数中第一位有1是100;n是123所有数中第一位是1的有24
  * 二是 对应a*f(s-1） 如n是223应该有2*f(99)个1
  * 三是 对应f(n-s*a) 如n是223应该有f(23)个1。
  */

 long f(long n){
  if (n<9) return n>0?1:0;
  int L=(int)(Math.log10(n)+1);//求n的位数l
  long s=(long)Math.pow(10, L-1);//求10的l－1次方，方便求后面n的第一位数字，及其后面的数。
  long a=(long)(n/s);//求n的第一位数字  
  return (a>1?s:n-s*a+1)+a*f(s-1)+f(n-s*a);
 }