《google笔试》由会员分享，可在线阅读，更多相关《google笔试（24页珍藏版）》请在金锄头文库上搜索。
1、google笔试资料仅供参考Google写出这样一个函数 ,输入一个 n, 输出从1到这个数字之间的出现的1的个数,比如f(13)等于6; f(9)等于1; 网上有很多这道题的解法，大多采用穷举法。这把这个算法题变成了程序设计，这道题，我认为是总结一个递推公式，然后用递推法实现，比较好。后来在网上考证了一下，这道题原来也是让总结一个数学函数即可，无需编程。既然写了，就贴出来，发表一下自己的解法。这道题还有另一半,当f(n)n是，最小的n是多少？本人还没有好的方法，因此就不贴了。下面的程序是上半部java实现的。/* 能够推出下列递推公式: * f(n)=(a1?s:n-s*a+1)+a*f(s
2、-1)+f(n-s*a)当n9时; * L是n的位数 * a是n的第一位数字 * s是10的L1次方 * n-s*a求的是a后面的数. * 公式说明： * 求 0-n 由多少个数字1，分三部分，一是所有数中第一位有多少个1，对应(a1?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 (n0?1:
3、0; int L=(int)(Math.log10(n)+1);/求n的位数l long s=(long)Math.pow(10, L-1);/求10的l1次方，方便求后面n的第一位数字，及其后面的数。 long a=(long)(n/s);/求n的第一位数字 return (a1?s:n-s*a+1)+a*f(s-1)+f(n-s*a); google笔试题：A+B=C在一个集合S中寻找最大的C使A+B=C且A,B,C均在集合当中解答(原创)1，将集合S中的数排序X1=X20;i-)for(j=0,k=i-1;kj;)if(Xj+XkXi) k-; cotinue;if(Xj+Xk 2)T(
4、0) = T(1) = 1, T(2) = 2.*/int tribonaci(int n)if (n uvSvu|w所识别的语言是：（）a、uvw*vu b、（uvwvu）* c、uv(uv)*wvu(vu)* d、(uv)*w(vu)*3、如下程序段输出是：（）char str10=Hello,Google;char *p=str0;countstrlen(p 10);a、0 b、5 c、6 d、104、cnt=0while(x!=1)cnt=cnt 1;if(x&1=0)x=x/2;elsex=3*x 1;countcntend1;当n=11时，输出：（）a、12 b、13 c、14 d
5、、155、写一段程序判定一个有向图G中节点w是否从节点v可达。（假如G中存在一条从v至w的路径就说节点w是从v可达的）。以下算法是用C 写成的，在bool Reachable函数中，你能够写出自己的算法。class Graphpublic:int NumberOfNodes();/返回节点的总数bool HasEdge(int u,int v);/u,v是节点个数，从零开始依次递增，当有一条从u到v的边时，返回true；bool Reachable(Graph&G, int v, int w)/请写入你的算法6、给定一棵所有边的长度均为整数的树，现要求延长其中某些边，使得从根到任意节点的路径长
6、度相等。问满足要求的树的边长度之和最小是多少?请写出你的算法，并分析时间复杂度。=Google笔试题1、 两个二进制数的异或结果% L. P2 C5 _2、 递归函数最终会结束，那么这个函数一定（不定项选择）：7 R8 c7 y( Q+ g/ a O1.使用了局部变量; s2 S8 9 M; w& . 3 d2. 有一个分支不调用自身 & J2 D7 Z+ $ a4 R A4 c3.使用了全局变量或者使用了一个或多个参数, O- l+ f3 i8 v* a$ m, S0 d, B, , * L3、以下函数的结果？2 * s; z/ O$ a$ z R+ 8 w4 F( A* h+ a& e !
7、 ) M7 s& int cal(int x) 1 r9 P4 L& ?3 k( M8 P+ f$ q & y1 n m9 R4 _5 g, vif(x=0) . s$ z0 IP! T1 O W! return 0;* z: T8 7 d+ R9 pelse; |1 P; : y* o6 c( I1 Yreturn x+cal(x-1);L6 k- X, g4 h+ K- ? _/ N9 m+ p7 C/ M9 ?, j) M8 GH( $ I( a: R- d3 ; # W4、 以下程序的结果？ 8 f7 N$ z/ g& c+ - V2 X* 8 evoid foo(int*a, int
8、* b) ( 4 . o# p, o7 c2 y9 M6 c0 S + ( t4 e5 W. Q+ 2 *a = *a+*b; & g4 _, o0 W; . h% p m3 f*b = *a-*b; $ _8 D b. e# M) m& Rd G*a = *a-*b;3 s/ J: i9 L0 Y: y 6 6 d/ # D3 f g2 v8 c) v L4 L: ; ) _# wvoid main()( Y: * + d( D0 U9 R# & t& * & i1 a! a5 Kint a=1, b=2, c=3;7 o- U- h1 o5 i, Efoo(&a,&b); * : r8 I
9、2 - f0 D, A0 ofoo(&b,&c); 0 k4 I& l1 h5 wfoo(&c,&a);( k# s7 X- | e) i6 P* b O# printf(%d, %d, %d, a,b,c);9 0 f9 5 w, jM9 N Y. 8 g; n* w; u2 p o5、下面哪项不是链表优于数组的特点？ % S1 U) _1 g5 T, d$ R# W- K7 L/ p1. 方便删除 2. 方便插入 3. 长度可变 4. 存储空间小4 K$ J$ l+ r# a2 W+ F8 ) Q6、T(n) = 25T(n/5)+n2的时间复杂度？9 yr& x: h8 d$ A, ?8 I4 M7、n个顶点，m条边的全连通
