Google笔试题整理.doc

Google笔试题整理 .docGoogle笔试题整理
写出这样一个函数,输入一个 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)((n)+1);//求n的位数l
long s=(long)[in] n The n in T(n).
param[out] mid Value of T(n - 2).
param[out] right Value of T(n - 3).
return Value of T(n - 1).
*/
int find_trib(int n, int mid, int right)
{
if (3 == n)
{
mid = 1;
right = 1;
return 2;
}
else
{
int temp;
mid = find_trib(n - 1, right, temp);
return