IT名企面試：谷歌筆試題
谷歌是不少IT人都想去的企業(yè)，那么在進(jìn)入公司前，少不了面試筆試的測(cè)試。那么這里我們就總結(jié)了如下谷歌筆試題，并提供了一些參考答案。希望對(duì)您有用。
谷歌筆試題：判斷一個(gè)自然數(shù)是否是某個(gè)數(shù)的平方。當(dāng)然不能使用開方運(yùn)算。
假設(shè)待判斷的數(shù)字是 N。
方法1：
遍歷從1到N的數(shù)字，求取平方并和N進(jìn)行比較。
如果平方小于N，則繼續(xù)遍歷；如果等于N，則成功退出；如果大于N，則失敗退出。
復(fù)雜度為O(n^0.5)。
方法2：
使用二分查找法，對(duì)1到N之間的數(shù)字進(jìn)行判斷。
復(fù)雜度為O(log n)。
方法3：
由于
(n+1)^2
=n^2 + 2n + 1，
= ...
= 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)
注意到這些項(xiàng)構(gòu)成了等差數(shù)列（每項(xiàng)之間相差2）。
所以我們可以比較 N-1， N - 1 - 3， N - 1 - 3 - 5 ... 和0的關(guān)系。
如果大于0，則繼續(xù)減；如果等于0，則成功退出；如果小于 0，則失敗退出。
復(fù)雜度為O(n^0.5)。不過方法3中利用加減法替換掉了方法1中的乘法，所以速度會(huì)更快些。
谷歌筆試題：如何隨機(jī)選取1000個(gè)關(guān)鍵字
給定一個(gè)數(shù)據(jù)流，其中包含無窮盡的搜索關(guān)鍵字（比如，人們?cè)诠雀杷阉鲿r(shí)不斷輸入的關(guān)鍵字）。如何才能從這個(gè)無窮盡的流中隨機(jī)的選取1000個(gè)關(guān)鍵字？
定義長(zhǎng)度為1000的數(shù)組。
對(duì)于數(shù)據(jù)流中的前1000個(gè)關(guān)鍵字，顯然都要放到數(shù)組中。
對(duì)于數(shù)據(jù)流中的的第n（n>1000）個(gè)關(guān)鍵字，我們知道這個(gè)關(guān)鍵字被隨機(jī)選中的概率為 1000/n。所以我們以 1000/n 的概率用這個(gè)關(guān)鍵字去替換數(shù)組中的隨機(jī)一個(gè)。這樣就可以保證所有關(guān)鍵字都以 1000/n的概率被選中。
對(duì)于后面的關(guān)鍵字都進(jìn)行這樣的處理，這樣我們就可以保證數(shù)組中總是保存著1000個(gè)隨機(jī)關(guān)鍵字。
谷歌筆試題：將下列表達(dá)式按照復(fù)雜度排序
將下列表達(dá)式按照復(fù)雜度排序
2^n
n^Googol (其中 Googol = 10^100)
n!
n^n
按照復(fù)雜度從低到高為
n^Googol
2^n
n!
n^n
谷歌筆試題：在半徑為1的圓中隨機(jī)選取一點(diǎn)
假設(shè)圓心所在位置為坐標(biāo)元點(diǎn)(0, 0)。
方法1.
在x軸[-1, 1]，y軸[-1, 1]的正方形內(nèi)隨機(jī)選取一點(diǎn)。然后判斷此點(diǎn)是否在圓內(nèi)（通過計(jì)算此點(diǎn)到圓心的距離）。如果在圓內(nèi)，則此點(diǎn)即為所求；如果不在，則重新選取直到找到為止。
正方形的面積為4，圓的面積為pi，所以正方形內(nèi)的隨機(jī)點(diǎn)在圓內(nèi)的概率是 pi / 4。
方法2.
從[0, 2*pi)中隨機(jī)選一個(gè)角度，對(duì)應(yīng)于圓中的一條半徑，然后在此半徑上選一個(gè)點(diǎn)。但半徑上的點(diǎn)不能均勻選取，選取的概率應(yīng)該和距圓心的長(zhǎng)度成正比，這樣才能保證隨機(jī)點(diǎn)在圓內(nèi)是均勻分布的。
谷歌筆試題：給定一個(gè)未知長(zhǎng)度的整數(shù)流，如何隨機(jī)選取一個(gè)數(shù)
方法1.
將整個(gè)整數(shù)流保存到一個(gè)數(shù)組中，然后再隨機(jī)選取。
如果整數(shù)流很長(zhǎng)，無法保存下來，則此方法不能使用。
方法2.
如果整數(shù)流在***個(gè)數(shù)后結(jié)束，則我們必定會(huì)選***個(gè)數(shù)作為隨機(jī)數(shù)。
如果整數(shù)流在第二個(gè)數(shù)后結(jié)束，我們選第二個(gè)數(shù)的概率為1/2。我們以1/2的概率用第2個(gè)數(shù)替換前面選的隨機(jī)數(shù)，得到滿足條件的新隨機(jī)數(shù)。
....
如果整數(shù)流在第n個(gè)數(shù)后結(jié)束，我們選第n個(gè)數(shù)的概率為1/n。我們以1/n的概率用第n個(gè)數(shù)替換前面選的隨機(jī)數(shù)，得到滿足條件的新隨機(jī)數(shù)。
....
利用這種方法，我們只需保存一個(gè)隨機(jī)數(shù)，和迄今整數(shù)流的長(zhǎng)度即可。所以可以處理任意長(zhǎng)的整數(shù)流。#p#
谷歌筆試題：設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，其中包含兩個(gè)函數(shù)，1.插入一個(gè)數(shù)字，2.獲得中數(shù)。并估計(jì)時(shí)間復(fù)雜度。
1. 使用數(shù)組存儲(chǔ)。
插入數(shù)字時(shí)，在O(1)時(shí)間內(nèi)將該數(shù)字插入到數(shù)組***。
獲取中數(shù)時(shí)，在O(n)時(shí)間內(nèi)找到中數(shù)。（選數(shù)組的***個(gè)數(shù)和其它數(shù)比較，并根據(jù)比較結(jié)果的大小分成兩組，那么我們可以確定中數(shù)在哪組中。然后對(duì)那一組按照同樣的方法進(jìn)一步細(xì)分，直到找到中數(shù)。）
2. 使用排序數(shù)組存儲(chǔ)。
插入數(shù)字時(shí)，在O(logn)時(shí)間內(nèi)找到要插入的位置，在O(n)時(shí)間里移動(dòng)元素并將新數(shù)字插入到合適的位置。
獲得中數(shù)時(shí)，在O(1)復(fù)雜度內(nèi)找到中數(shù)。
3. 使用大根堆和小根堆存儲(chǔ)。
使用大根堆存儲(chǔ)較小的一半數(shù)字，使用小根堆存儲(chǔ)較大的一半數(shù)字。
插入數(shù)字時(shí)，在O(logn)時(shí)間內(nèi)將該數(shù)字插入到對(duì)應(yīng)的堆當(dāng)中，并適當(dāng)移動(dòng)根節(jié)點(diǎn)以保持兩個(gè)堆數(shù)字相等（或相差1）。
獲取中數(shù)時(shí)，在O(1)時(shí)間內(nèi)找到中數(shù)。
給定一個(gè)固定長(zhǎng)度的數(shù)組，將遞增整數(shù)序列寫入這個(gè)數(shù)組。當(dāng)寫到數(shù)組尾部時(shí)，返回?cái)?shù)組開始重新寫，并覆蓋先前寫過的數(shù)。
請(qǐng)?jiān)谶@個(gè)特殊數(shù)組中找出給定的整數(shù)。
假設(shè)數(shù)組為a[0, 1, ..., N-1]。
我們可以采用類似二分查找的策略。
首先比較a[0]和a[N/2]，如果a[0] < a[N/2]，則說明a[0,1,...,N/2]為遞增子序列，否則另一部分是遞增子序列。
然后判斷要找的整數(shù)是否在遞增子序列范圍內(nèi)。如果在，則使用普通的二分查找方法繼續(xù)查找；如果不在，則重復(fù)上面的查找過程，直到找到或者失敗為止。
給定兩個(gè)已排序序列，找出共同的元素。
不妨假設(shè)序列是從小到大排序的。定義兩個(gè)指針分別指向序列的開始。
如果指向的兩個(gè)元素相等，則找到一個(gè)相同的元素；如果不等，則將指向較小元素的指針向前移動(dòng)。
重復(fù)執(zhí)行上面的步驟，直到有一個(gè)指針指向序列尾端。
谷歌筆試題：找到鏈表的倒數(shù)第m個(gè)節(jié)點(diǎn)。
方法1：
首先遍歷鏈表，統(tǒng)計(jì)鏈表的長(zhǎng)度N。
然后再次遍歷鏈表，找到第N-m個(gè)節(jié)點(diǎn)，即為倒數(shù)第m個(gè)節(jié)點(diǎn)。
方法2：
使用兩個(gè)指針，并使它們指向的節(jié)點(diǎn)相距m-1個(gè)。
然后同時(shí)向前移動(dòng)兩個(gè)指針，當(dāng)一個(gè)指針指***一個(gè)節(jié)點(diǎn)時(shí)，第二個(gè)指針指向倒數(shù)第m個(gè)節(jié)點(diǎn)。
兩個(gè)方法的復(fù)雜度都是O(n)。
但是當(dāng)N較大而m較小時(shí)，方法2可能會(huì)更快一些。因?yàn)榉椒?能更好利用CPU的緩存。
更多閱讀：
http://baike.baidu.com/view/2089.htm CPU -> 緩存
谷歌筆試題：給定一個(gè)排序數(shù)組，如何構(gòu)造一個(gè)二叉排序樹？
采用遞歸算法。
選取數(shù)組中間的一個(gè)元素作為根節(jié)點(diǎn)，左邊的元素構(gòu)造左子樹，右邊的節(jié)點(diǎn)構(gòu)造有子樹。
谷歌筆試題：數(shù)組中是否有兩個(gè)數(shù)的和為10
1.比較任意兩個(gè)數(shù)的和是否為10。如
for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { .... }}
復(fù)雜度為O(n*n)。
2.將數(shù)組排序后，對(duì)每個(gè)數(shù)m，使用二分查找在數(shù)組中尋找10-m。
復(fù)雜度為O(nlogn)。
3.將數(shù)組存儲(chǔ)到hash_set中去，對(duì)每個(gè)數(shù)m，在hash_set中尋找10-m。
復(fù)雜度為O(n)。
4.如果數(shù)組很大，超過內(nèi)存的容量，可以按照hash(max(m, 10-m))%g，將數(shù)據(jù)分到g個(gè)小的group中。然后對(duì)每個(gè)小的group進(jìn)行單獨(dú)處理。
復(fù)雜度為O(n)。
谷歌筆試題：找到兩個(gè)字符串的公共字符，并按照其中一個(gè)的排序
寫一函數(shù)f(a,b)，它帶有兩個(gè)字符串參數(shù)并返回一串字符，該字符串只包含在兩個(gè)串中都有的并按照在a中的順序。寫一個(gè)版本算法復(fù)雜度O(N^2)和一個(gè)O(N)
O(N^2)：
對(duì)于a中的每個(gè)字符，遍歷b中的每個(gè)字符，如果相同，則拷貝到新字符串中。
O(N)：
首先使用b中的字符建立一個(gè)hash_map，對(duì)于a中的每個(gè)字符，檢測(cè)hash_map中是否存在，如果存在則拷貝到新字符串中。
給定一個(gè)整數(shù)序列，其中有些是負(fù)數(shù)，有些是正數(shù)，從該序列中找出***和的子序列。比如：-5，20，-4，10，-18，子序列[20，-4，10]具有***和26。
- ` int GetMaxSubArraySum(int* array, int array_len) {
- ` int current_sum = 0;
- ` int max_sum = 0;
- ` for (int i = 0; i < array_len; ++i) {
- ` current_sum += array[i];
- ` if (current_sum > max_sum) {
- ` max_sum = current_sum;
- ` } else if (current_sum < 0) {
- ` current_sum = 0;
- ` }
- ` }
- ` return max_sum;
- ` }
- 或者
- int maxsum(int n,int[] list)
- {
- int ret,sum=0;
- int i;
- for (ret=list[i=0];i<n;i++)
- sum=(sum>0?sum:0)+list[i],ret=(sum>ret?sum:ret);
- return ret;
- }
#p#谷歌筆試題：將無向無環(huán)連通圖轉(zhuǎn)換成深度最小的樹
已知一個(gè)無向無環(huán)連通圖T的所有頂點(diǎn)和邊的信息，現(xiàn)需要將其轉(zhuǎn)換為一棵樹，要求樹的深度最小，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法找到所有滿足要求的樹的根結(jié)點(diǎn)，并分析時(shí)空復(fù)雜度。
最簡(jiǎn)單直接的方法就是把每個(gè)節(jié)點(diǎn)都試一遍：
假設(shè)某個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)，計(jì)算樹的深度。當(dāng)遍歷完所有節(jié)點(diǎn)后，也就找到了使樹的深度最小的根節(jié)點(diǎn)。
但這個(gè)方法的復(fù)雜度很高。如果有n個(gè)節(jié)點(diǎn)，則時(shí)間復(fù)雜度為O(n^2)。
樹的深度取決于根節(jié)點(diǎn)到最深葉節(jié)點(diǎn)的距離，所以我們可以從葉節(jié)點(diǎn)入手。
葉節(jié)點(diǎn)會(huì)且只會(huì)和某一個(gè)節(jié)點(diǎn)連通（反之不成立，因?yàn)楦?jié)點(diǎn)也可能只和一個(gè)節(jié)點(diǎn)連通），所以我們很容易找到所有可能的葉節(jié)點(diǎn)。
題目可以等價(jià)于找到了兩個(gè)葉節(jié)點(diǎn)，使得兩個(gè)葉節(jié)點(diǎn)之間的距離最遠(yuǎn)。根節(jié)點(diǎn)就是這兩個(gè)葉節(jié)點(diǎn)路徑的中間點(diǎn)（或者中間兩個(gè)點(diǎn)的任意一個(gè)）。
我們可以每次都將連接度為1的節(jié)點(diǎn)刪掉，直到***只剩下1個(gè)或2個(gè)節(jié)點(diǎn)，則這一個(gè)節(jié)點(diǎn)，或者兩個(gè)節(jié)點(diǎn)中的任意一個(gè)，就是我們要找的根節(jié)點(diǎn)。
谷歌筆試題：將字符串中的小寫字母排在大寫字母的前面
有一個(gè)由大小寫組成的字符串，現(xiàn)在需要對(duì)它進(jìn)行修改，將其中的所有小寫字母排在大寫字母的前面（大寫或小寫字母之間不要求保持原來次序）。
初始化兩個(gè)int變量A和B，代表字符串中的兩個(gè)位置。開始時(shí)A指向字符串的***個(gè)字符，B指向字符串的***一個(gè)字符。
逐漸增加A的值使其指向一個(gè)大寫字母，逐漸減小B使其指向一個(gè)小寫字母，交換A，B所指向的字符，然后繼續(xù)增加A，減小B....。
當(dāng)A>=B時(shí)，就完成了重新排序。
i指向***一個(gè)小寫字符，j尋找小寫字符。
- void swapString(char* str, int len)
- {
- int i=-1;
- int j=0;
- for(j=0; j<len; j++)
- {
- if(str[j]<='z' && str[j]>='a')
- {
- i++;
- swap(str[i], str[j]);
- }
- }
- }
谷歌筆試題：在重男輕女的國(guó)家里，男女的比例是多少？
在一個(gè)重男輕女的國(guó)家里，每個(gè)家庭都想生男孩，如果他們生的孩子是女孩，就再生一個(gè)，直到生下的是男孩為止。這樣的國(guó)家，男女比例會(huì)是多少？
還是1：1。
在所有出生的***個(gè)小孩中，男女比例是1：1；在所有出生的第二個(gè)小孩中，男女比例是1：1；.... 在所有出生的第n個(gè)小孩中，男女比例還是1：1。
所以總的男女比例是1：1。
谷歌筆試題：如何拷貝特殊鏈表
有一個(gè)特殊的鏈表，其中每個(gè)節(jié)點(diǎn)不但有指向下一個(gè)節(jié)點(diǎn)的指針pNext，還有一個(gè)指向鏈表中任意節(jié)點(diǎn)的指針pRand，如何拷貝這個(gè)特殊鏈表？
拷貝pNext指針非常容易，所以題目的難點(diǎn)是如何拷貝pRand指針。
假設(shè)原來鏈表為A1 -> A2 ->... -> An，新拷貝鏈表是B1 -> B2 ->...-> Bn。
為了能夠快速的找到pRand指向的節(jié)點(diǎn)，并把對(duì)應(yīng)的關(guān)系拷貝到B中。我們可以將兩個(gè)鏈表合并成
A1 -> B1 -> A2 -> B2 -> ... -> An -> Bn。
從A1節(jié)點(diǎn)出發(fā)，很容易找到A1的pRand指向的節(jié)點(diǎn)Ax,然后也就找到了Bx，將B1的pRand指向Bx也就完成了B1節(jié)點(diǎn)pRand的拷貝。依次類推。
當(dāng)所有節(jié)點(diǎn)的pRand都拷貝完成后，再將合并鏈表分成兩個(gè)鏈表就可以了。
- class ListNode
- {
- int value;
- ListNode* p_next;
- ListNOde* p_rand;
- public ListNode(int v, ListNode* next, ListNode* rand): value(v), p_next(next), p_rand(rand)
- {
- }
- };
- ListNode*copyList(ListNode*p)
- {
- if(p!=null)
- {
- /*構(gòu)建交叉數(shù)組 p0->q0->p1->q1->p2->q2...*/
- ListNOde*ppre=p;
- ListNode*post=->next;
- while(pre!=null)
- {
- pre->next=newListNode(pre->value,post,pre->p_rand->p_next);
- pre=last;
- lastlast=last->p_next;
- }
- /*拆分成被拷貝數(shù)組和拷貝數(shù)組 p0->p1->p2....;q0->q1->q2....*/
- ppre=p;
- ListNode*res=p->p_next;
- while(res->p_next!=null)
- {
- p->p_next=res->p_next;
- res->p_next=res->p_next->p_next;
- }
- returnres;
- }else
- {
- returnp;
- }
- }
如果在高速公路上30分鐘內(nèi)看到一輛車開過的幾率是0.95，那么在10分鐘內(nèi)看到一輛車開過的幾率是多少？(假設(shè)為常概率條件下)
假設(shè)10分鐘內(nèi)看到一輛車開過的概率是x，那么沒有看到車開過的概率就是1-x，30分鐘沒有看到車開過的概率是(1-x)^3，也就是0.05。所以得到方程(1-x)^3 = 0.05
解方程得到x大約是0.63。
谷歌筆試題：從25匹馬中找出最快的3匹
最少需要7次。
首先將馬分成a,b,c,d,e 5個(gè)組，每組5匹，每組單獨(dú)比賽。然后將每組的***名放在一起比賽。假設(shè)結(jié)果如下
a0,a1,a2,a3,a4
b0,b1,b2,b3,b4
c0,c1,c2,c3,c4
d0,d1,d2,d3,d4
e0,e1,e2,e3,e4
其中a, b,c,d,e小組都是按照名次排列（速度a0>a1>a2>a3>a4, b0>b1....)。并第6次比賽的結(jié)果為a0>b0>c0>d0>e0。
那么第6次比賽結(jié)束后，我們知道最快的一匹為a0。
我們知道第2名的馬一定是a1或者b0，所以在接下來的比賽中要包含這兩匹馬。如果a1快，那么第3名是a2或者b0，如果b0快，那么第3名是a1，b1或者c0。也就是說第2名和第3名一定在a1，a2，b0，b1和c0當(dāng)中，所以在第7場(chǎng)比賽中包括這5匹馬就可以得到第2名和第3名。
所以7次比賽就可以獲得前3名的馬。#p#
谷歌筆試題：海盜分金問題
有5個(gè)海盜，按照等級(jí)從5到1排列。***的海盜有權(quán)提議他們?nèi)绾畏窒?00枚金幣。但其他人要對(duì)此表決，如果多數(shù)（所有人中的多數(shù)）反對(duì)，那他就會(huì)被殺死。他應(yīng)該提出怎樣的方案，既讓自己拿到盡可能多的金幣又不會(huì)被殺死？
分配方案是98，0，1，0，1。
5級(jí)海盜會(huì)不會(huì)被殺死，取決于5級(jí)海盜死后其他海盜是否會(huì)獲得更多的利益。如果可以獲得更多的利益，則肯定會(huì)反對(duì)，如果會(huì)獲得更少的利益，則肯定會(huì)支持，如果利益沒有變化，則反對(duì)或支持都可以。
如果5級(jí)海盜死了，則有4級(jí)海盜分配，4級(jí)海盜面臨同樣的問題，需要看自己死后的利益分配變化。然后是3級(jí)海盜，2級(jí)海盜。
2級(jí)海盜無論提出什么方案，都不會(huì)有多數(shù)人反對(duì)（自己支持，另一個(gè)人反對(duì)不能構(gòu)成多數(shù)反對(duì)）。所以2級(jí)海盜肯定會(huì)提出100，0的分配方案，自己獨(dú)享所有金幣。
猜到2級(jí)海盜的分配方案后，3級(jí)海盜會(huì)提出99，0，1的分配方案。這樣1級(jí)海盜因獲得了比2級(jí)海盜方案中更多的金幣，所以會(huì)支持3級(jí)海盜的方案。
猜到3級(jí)海盜的分配方案后，4級(jí)海盜會(huì)提出99，0，1，0的分配方案。這樣2級(jí)海盜獲得了比3級(jí)海盜方案中更多的金幣，所以會(huì)支持4級(jí)海盜的方案。
猜到4級(jí)海盜的分配方案后，5級(jí)海盜會(huì)提出98，0，1，0，1的分配方案。這樣1級(jí)海盜和3級(jí)海盜獲得了比4級(jí)海盜方案中更多的金幣，所以會(huì)支持5級(jí)海盜的方案。
谷歌筆試題：4人過橋問題
4 個(gè)人晚上要穿過一座索橋回到他們的營(yíng)地?？上麄兪稚现挥幸恢е荒茉賵?jiān)持17分鐘的手電筒。通過索橋必須要拿著手電，而且索橋每次只能撐得起兩個(gè)人的份量。這四個(gè)人過索橋的速度都不一樣，***個(gè)走過索橋需要1分鐘，第二個(gè)2分鐘，第三個(gè)5分鐘，最慢的那個(gè)要10分鐘。他們?cè)鯓硬拍茉?7分鐘內(nèi)全部走過索橋？
1）***個(gè)和第二個(gè)一起過去，用掉2分鐘；
2）***個(gè)回來，用掉1分鐘；
3）第三個(gè)和第四個(gè)一起過去，用掉10分鐘；
4）第二個(gè)回來，用掉2分鐘；
5）***個(gè)和第二個(gè)一起過去，用掉2分鐘。
總共用掉17分鐘。
谷歌筆試題：如何從8只球中找出比較重的一個(gè)
你有8個(gè)一樣大小的球，其中7個(gè)的重量是一樣的，另一個(gè)比較重。怎樣能夠用天平僅稱兩次將那個(gè)重一些的球找出來。
解答：
先取6個(gè)，天平上一邊3個(gè)，同重則稱剩余2個(gè)即可；不同重，則取重的3個(gè)中的2個(gè)來稱。
分析：
此題可以通過倒推法來解決。
如果我們知道重球在某兩個(gè)球中，則可以通過天平兩邊各放一個(gè)，比較重量發(fā)現(xiàn)重球。
如果我們知道重球在某三個(gè)球中，則可以通過天平兩邊各放一個(gè)，如果一樣重，則第三個(gè)球是重球，否則天平上較重的即是重球。
如果我們知道重球在大于等于四個(gè)球中，則不能通過一次稱重發(fā)現(xiàn)重球。
所以通過***次稱重，我們必須將重球限定在某兩個(gè)或三個(gè)球當(dāng)中。另外，天平兩端放的球數(shù)應(yīng)該相等，否則結(jié)果基本沒有意義。
滿足兩端球相等的所有可能的比較方法
左，右
1， 1
2， 2
3， 3
4， 4
再考慮到必須將重球限定在2或3個(gè)球中，***次只能采取3，3的比較方法。
此題還可以擴(kuò)展一下：在m只大小相同的球中，m-1只重量相同，另外一只比較重。問需要用天平稱多少次才能將重球找出來？
從上面的分析中可以知道，稱一次最多可以
- 將重球從3個(gè)球中找出來。
- 將重球從9個(gè)球中限定在3個(gè)球中。
- 將重球從27個(gè)球中限定在9個(gè)球中。
.....
所以，稱n次最多可以將重球從3^n中找出來。倒推回去也就可以獲得m個(gè)球需要稱多少次。
或者
我們用i+表示第i個(gè)球比較重。
共有8種可能性：1+; 2+; 3+; 4+; 5+; 6+; 7+; 8+;
將1 2 3 與4 5 6 放在天秤上稱，如果左邊中，則可以將重球確定在1 2 3中，
即可能性為：1+ 2+ 3+ 然后將1和2放在天秤兩邊稱，如果左邊重則重球?yàn)?，如果右邊重，重球?yàn)?，如果平衡重球?yàn)?。
如果平衡：7+ 8+ 將7和8放在天秤兩邊稱，可以判斷重球?yàn)?還是8
如果右邊重：4+ 5+ 6+ 同球1 2 3的情況。
【編輯推薦】
