偶看新闻汕头金湖路:网上一道google笔试题的答案
来源：百度文库 编辑：偶看新闻 时间：2024/06/11 23:50:00
写出这样一个函数 ,输入一个 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);
}