google笔试题整理

《google笔试题整理 》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、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

2、-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。*/longf(longn){if(n<9)returnn>0?1:0;intL=(

3、int)(Math.log10(n)+1);//求n的位数llongs=(long)Math.po[in]nTheninT(n).param[out]midValueofT(n-2).param[out]rightValueofT(n-3).returnValueofT(n-1).*/intfind_trib(intn,intmid,intright){if(3==n){mid=1;right=1;return2;}else{inttemp;mid=find_trib(n-1,right,temp);returnmidrighttemp;}}/**FindvalueofT(n).pa

4、ram[in]TheninT(n).returnValueofT(n).noteT(n)=T(n-1)T(n-2)T(n-3)(n>2)T(0)=T(1)=1,T(2)=2.*/inttribonaci(intn){if(n<0){//Undefinedfeature.return0;}if(0==n

5、

6、1==n){return1;}if(2==n){return2;}intmid,right;intleft=find_trib(n,mid,right);returnleftmidright;}　　啊啊，对了，答卷的时候我可没心情写