【益智遊戲】：真假金幣問題_綠翠園濁水溪畔的國中生專屬部落格forum.xmart.tw/formosa/

	§網綠翠園站§ 　濁水溪畔的國中生專屬部落格

【益智遊戲】：真假金幣問題

發表：濁水溪畔的國中生	2012-05-13 16:00:56	閱覽數：39184	(IP:　)	T 3493_R 0	引　用

在進入主題之前，容許我先說個小故事。

前微軟總裁Bill Gates在哈佛大學休學前，曾和老師Christos Papadimitriou發表過一篇很優的論文──【薄煎餅翻整問題】：給定一疊大小不一的薄煎餅，廚師如何用鏟子做最少次的翻轉，使得薄煎餅依序由小排到大。

這是個很難的問題，雖然Bill Gates只是一個大學生，但聰明的他給了一個很棒的解法。

後來，Christos Papadimitriou成了計算複雜理論（Computational complexity theory）的大師，據說有人曾向Papadimitriou提到：「Bill Gates一定很後悔沒繼續跟你做研究，不然，也一定能在計算理論領域佔有重要的一席之地。」

Papadimitriou回答說：「唉！該後悔的是我。當時如果我跟他一起去開公司，我老早就是全美十大富豪了！」

回應：濁水溪畔的國中生	2012-05-13 16:06:56	(IP:　)	T 3493_R 1	引　用

Christos Papadimitriou是何許人？

【轉貼wiki】：Christos Harilaos Papadimitriou (born August 16, 1949, Athens) is a Professor in the Computer Science Division at the University of California, Berkeley, United States. He studied at the National Technical University of Athens (BS in Electrical Engineering, 1972) and at Princeton University (MS in Electrical Engineering, 1974 and PhD in Electrical Engineering and Computer Science, 1976). He has also taught at Harvard, MIT, the National Technical University of Athens, Stanford, and UCSD.

Papadimitriou is the author of the textbook Computational Complexity, one of the most widely used textbooks in the field of computational complexity theory. He has also co-authored the textbook Algorithms (2006) with Sanjoy Dasgupta and Umesh Vazirani, and the graphic novel Logicomix (2009) with Apostolos Doxiadis.

He co-authored a paper with Bill Gates, co-founder of Microsoft, while Gates was studying at Harvard.

Christos Papadimitriou在複雜度理論等方面的傑出貢獻使他獲得【Donald E. Knuth Prize】，並成為美國國家科學院與美國國家工程學院院士。

【註】：Donald E. Knuth Prize是以史丹福大學的退休教授──Donald Ervin Knuth的名字命名，他是計算機方法分析及程式語言實作研究的開路先鋒，被公認是當代最偉大的資訊學家，曾經獲頒有資訊領域諾貝爾獎之稱的【杜林獎】。

回應：濁水溪畔的國中生	2012-05-13 16:08:33	(IP:　)	T 3493_R 2	引　用

眼尖的前輩先進可能會發現Christos Papadimitriou帽子上的人物圖片，似乎很眼熟？

沒錯！就是下面這張名為《英勇的游擊隊員》的照片，被譽為【世上最知名的照片】，是傳記、回憶錄、文章、紀錄片、歌曲及電影常出現的題材，主角是《時代》雜誌選為二十世紀百大影響力人物，生平毀譽參半的切格瓦拉（Che Guevara）。

【轉貼節錄wiki】：切格瓦拉（Che Guevara，1928年6月14日[1]－1967年10月9日），或簡稱切（El Che或Che），是阿根廷的馬克思主義革命家、醫師、作家、遊擊隊隊長、軍事理論家、國際政治家及古巴革命的核心人物。……

Che是文筆鋒利、創作豐富的作家與日記作者，著有影響深遠的游擊戰指南，及關於他橫越南美洲的青年摩托車旅行的暢銷自傳。同時，也是【驚爆13天】的始作俑者──他所訓練的民兵部隊在豬灣入侵擊退了美軍，並為古巴帶來了蘇聯核武彈道飛彈，隨後在1962年引發了古巴飛彈危機。Che於1965年離開古巴，前往剛果及玻利維亞進行革命。Che到了玻利維亞後，被當地由米國CIA協助的軍隊逮捕，並遭處決……。

Che Guevara死後，他的肖像成為反主流文化的普遍象徵、全球流行文化的標誌，同時也是第三世界共產革命運動中的英雄和世界左翼運動的象徵。

似乎有些矛盾？既然是標榜【反主流文化】，卻又形成【流行文化】的icon？

喔對了！Christos Papadimitriou是一個【另類】、【搞怪】的教授，2006年在加大柏克萊任教時，他和幾位教授、研究生組了一個名叫【Lady X and The Positive Eigenvalues】的搖滾樂團（連樂團名字都非常數理化……^__^），還擔任keyboard手！相對於傳統的古典樂而言，搖滾樂原本就有顛覆、叛逆的意味，所以身上有【反主流文化】的普遍象徵其實不足為奇，一如長髮、皮衣、馬靴、金屬扣環等配件，更能突顯搖滾的精神。

還好，酥肥鴨不是加大柏克萊的教官，不然若依其單面向的思維模式，大概又會因為Christos Papadimitriou頭戴Che肖像的帽子而推論他是共產思想，甚至貼標籤迫害吧？！

回應：濁水溪畔的國中生	2012-05-13 16:09:14	(IP:　)	T 3493_R 3	引　用

為保障我弟弟未來的權益，照例貼一些蠻複雜的東東來模糊焦點……^+++++++++^

【轉貼節錄wiki】：計算複雜性理論（Computational complexity theory）是計算理論的一部分，研究計算問題時所需的資源，比如時間（要通過多少步才能解決問題）和空間（在解決問題時需要多少記憶體），以及如何盡可能的節省這些資源。其他資源亦可考慮，例如在並行計算中，需要多少並行處理器才能解決問題。

【時間複雜度】──是指電腦完成一個演算法所需要的時間，是衡量一個演算法優劣的重要參數。時間複雜度越小，說明該演算法效率越高，則該演算法越有價值。

【空間複雜度】──是指電腦完成一個演算法所需要佔用的存儲空間，一般是輸入參數的函數，它是演算法優劣的重要度量指標。一般來說，空間複雜度越小，演算法越好。我們假設有一個圖靈機來解決某一類語言的某一問題，設有X個字（word）屬於這個問題，把X放入這個圖靈機的輸入端，這個圖靈機為解決此問題所需要的工作帶格子數總和稱為空間。

複雜度理論和可計算性理論不同，可計算性理論的重心在於問題能否解決，不管需要多少資源。而複雜性理論作為計算理論的分支，某種程度上被認為和演算法理論是一種【矛】與【盾】的關係，即演算法理論專註於設計有效的演算法，而複雜性理論專註於理解為什麼對於某類問題，不存在有效的演算法。

在20世紀50年代，Trahtenbrot和Rabin的論文被認為是該領域最早的文獻。一般說來，被公認奠定計算複雜性領域基礎的是Hartmanis和Stearns的1960年代的論文On the computational complexity of algorithms。在這篇論文中，作者引入了時間複雜性類TIME(f(n))的概念，並利用對角線法證明了時間層級定理（Time Hierarchy Theorem）。

此後，許多研究者對複雜性理論作出了貢獻。期間重要的發現包括：對隨機演算法的去隨機化（derandomization）的研究，對近似演算法的不可近似性（hardness of approximation）的研究，以及互動式證明系統（Interactive proof system）理論和零知識證明（Zero-knowledge proof）等。特別的複雜性理論對近代密碼學的影響非常顯著，近期，複雜性理論的研究者又進入了博弈論領域，並創立了【演算法博弈論】（algorithmic game theory）這一分支。

再次驗證正反前輩所說的【數學】不是簡單，而是超級【複雜】！^__^

（Multi-choice＋algorithm＋cloud，應該可以讓正反前輩【受迫性三太子附身】，比較沒空要偶們【喀擦】……^+++++++++^）

回應：濁水溪畔的國中生	2012-05-13 16:09:42	(IP:　)	T 3493_R 4	引　用

演算法需要好的分析與設計，才能找到好的解決方案，必要時也要腦筋急轉彎一下。

言歸正傳，為了讓Yuchin前輩所謂【男人變笨的預測模型】破功，提供以下幾個益智題目，讓各位前輩先進在閒暇之時好好鍛鍊鳥力…..啊不，是鍛鍊腦力！^++++++^

【＃1】：暖身問題──已知8個金幣中有1個假金幣，假的較輕。請問用天平最少秤幾次，就可以得知那一個是假金幣？

【＃2】：據悉是某大學某一年的資管所口試題目──已知128個金幣中有1個假金幣，假的較輕。請問用天平最少秤幾次，就可以得知那一個是假金幣？

【＃3】：把數字再搞大一些──已知19748個金幣中有1個騜金假幣（ma-gay B），假的較輕。請問用天平最少秤幾次，就可以得知那一個是假金幣？

＃1、＃2、＃3的數字看似愈來愈龐大複雜，其實都是同樣概念的問題，解決的道理是一樣的。透過這3題的操作，您會發現數量由8個變成19748個（增加2400多倍），但執行步驟卻只有增加幾次而已，而這也正是【數學】御繁為簡的奧義！（ㄟ……好像洩露解決的方式……^__*）

回應：濁水溪畔的國中生	2012-05-13 16:10:21	(IP:　)	T 3493_R 5	引　用

【＃4】：延伸問題──已知有10袋金幣，每袋數量不等（數十個至數百個），其中有1袋是假的，真的金幣每個10 g，假的金幣每個9 g。現在天平只能秤1次，請問該如何操作，就可以得知那一袋是假金幣？

【＃5】：變化問題──已知12個金幣中有1個假金幣，但不知道假的金幣比較輕或是比較重。請問用天平最少秤幾次，就可以得知那一個是假金幣？

讓頭腦稍為活動活動，祝各位前輩先進【益智遊戲】玩得愉快！

回應：濁水溪畔的國中生	2012-05-13 17:27:20	(IP:　)	T 3493_R 6	引　用

抱歉，補充一下。

以上問題中所謂【用天平最少秤幾次】是指──在您所提出的操作模式中，最糟的情況須秤幾次才能找到假金幣？

若是回答第1次、第2次就碰巧秤到假的金幣，這純屬巧合，不列為【合理】解答。

回應：正反修羅	2012-05-13 21:25:39	(IP:　)	T 3493_R 7	引　用

若是回答第1次、第2次就碰巧秤到假的金幣，這純屬巧合，不列為【合理】解答。
>>>

故意誤導！故意騙人^++++^

回應：正反修羅	2012-05-13 22:05:30	(IP:　)	T 3493_R 8	引　用

但執行步驟卻只有增加幾次而已，而這也正是【數學】御繁為簡的奧義！（ㄟ……好像洩露解決的方式……^__*）
>>>>
名詞
原木
航海日誌
木頭
^__^噓！！以X為底

回應：濁水溪畔的國中生	2012-05-13 22:30:23	(IP:　)	T 3493_R 9	引　用

R7>>故意誤導！故意騙人^++++^
==============================

正反前輩，暗安！吃飽未？

就好比踢一下精微儀讓測量儀器位置移動……ccc

除了【＃1】暖身問題，也不能說是騙人啦！

回應：濁水溪畔的國中生	2012-05-13 22:32:21	(IP:　)	T 3493_R 10	引　用

回應：正反修羅	2012-05-13 22:35:25	(IP:　)	T 3493_R 11	引　用

看外獨會的答案
笑到肚子痛！！！！！

>>>【＃4】：延伸問題──已知有10袋金幣，每袋數量不等（數十個至數百個），其中有1袋是假的，真的金幣每個10 g，假的金幣每個9 g。現在天平只能秤1次，請問該如何操作，就可以得知那一袋是假金幣？

>>>

存心耍人！腦筋急轉彎啊？？？

回應：濁水溪畔的國中生	2012-05-13 22:55:59	(IP:　)	T 3493_R 12	引　用

>>存心耍人！腦筋急轉彎啊？？？
==============================

正反前輩，天地良心，沒有存心耍人啦！^++++++^

回應：天涯台客	2012-05-14 04:59:09	(IP:　)	T 3493_R 13	引　用

整人的陷阱又來了？

>> 【＃4】：延伸問題──已知有10袋金幣，每袋數量不等（數十個至數百個），其中有1袋是假的，真的金幣每個10 g，假的金幣每個9 g。現在天平只能秤1次，請問該如何操作，就可以得知那一袋是假金幣？

●夭壽喔！弄得我的白髮掉滿地

回應：天涯台客	2012-05-14 05:18:40	(IP:　)	T 3493_R 14	引　用

回應：天涯台客	2012-05-14 05:19:58	(IP:　)	T 3493_R 15	引　用

前面搞個Christos Papadimitriou 和切格瓦拉（Che Guevara）？

這鍋叫做故佈疑陣，害偶一夜沒睡。

回應：正反修羅	2012-05-14 08:08:02	(IP:　)	T 3493_R 16	引　用

大揭曉：......... 個金幣，....【秤】上，.............袋。

你，猜對了嗎！？
>>>

抗議！抗議！！
高材生唬弄人！！

>>>【＃4】：...現在【天平】只能秤1次........，請問該如何操作，就可以得知那一袋是假金幣？>>>

高材生只給【天平】沒給【法碼】，只能比大小，不能知重量！^__*
台客用的是【秤】一【秤】就知重量

嘻嘻嘻！！

我居然以為濁水溪畔的高材生唬弄人，要我們：只用比大小的，就知道【＃4】的答案！！

真是思考的慣性！！！^++++++++++++++++++^

回應：濁水溪畔的國中生	2012-05-14 20:28:36	(IP:　)	T 3493_R 17	引　用

R13>>●夭壽喔！弄得我的白髮掉滿地
http://blog.xuite.net/magu/move4685/8158709
從每個袋子拿金幣出來，幾號袋就照號碼拿金幣來，......
原本應該是 550 克，看秤上的重量減去 550 克，
多出幾克就是有幾枚金幣是假的，
......
==============================

台客前輩，米國早安！

請注意喔！我的題目是──真的金幣每個10 g，假的金幣每個9 g，假的較輕。所以，這個參考解答應該要修正一下……^__^

--------------------------------------------------------------------------------
回應：天涯台客 2012-05-14 05:19:58 (IP: 　) T 3493_R 15 引　用
前面搞個Christos Papadimitriou 和切格瓦拉（Che Guevara）？
這鍋叫做故佈疑陣，害偶一夜沒睡。
==============================

嘿嘿嘿！麥假啦！臺灣時間【05:19:58】在SF當地是大白天啦……

回應：濁水溪畔的國中生	2012-05-14 20:41:10	(IP:　)	T 3493_R 18	引　用

R16>>抗議！抗議！！

正反前輩，暗安！

冤枉啊！偶沒有唬弄人，天平原本就是測量質量的度量衡儀器，完整的天平組是有包括砝碼的。

況且，偶題目本來就說──現在天平只能【秤】1次，又不是說【比】1次……

回應：濁水溪畔的國中生	2012-05-14 23:17:12	(IP:　)	T 3493_R 19	引　用

以下解答，僅供各位前輩先進參考。

首先，是【＃1】暖身問題──已知8個金幣中有1個假金幣，假的較輕。請問用天平最少秤幾次，就可以得知那一個是假金幣？

（1）最【人才】的做法：逐一比對。

1. 將8個金幣編號A1、A2、......A8。
2. 把（A1、A2）分放兩邊秤，若A1＞A2，則A2即為所求；若A1＝A2，則繼續下步驟。
3. 把（A1、A3）分放兩邊秤，若A1＞A3，則A3即為所求；若A1＝A3，則繼續下步驟。
4. 同上述作法，依序逐一相秤（A1、A4）、（A1、A5）……直到碰到比較輕的那個為止。

幸運的話，可能第一次就可以找到假金幣。萬一灰熊衰洨，假金幣正好是最後一個，那麼最糟的情況是──總共要秤7次！

（2）稍微不白爛的做法：兩兩對秤。

1. 每兩個金幣為一組，8個金幣分為（A1、A2）、（B1、B2）、（C1、C2）、（D1、D2）4組。
2. 把（A1、A2）分放兩邊秤，若A1＞A2，則A2即為所求；若A1＝A2，則繼續下步驟。
3. 把（B1、B2）分放兩邊秤，若B1＞B2，則B2即為所求；若B1＝B2，則繼續下步驟。
4. 同上述作法，依序逐一相秤（C1、C2）、（D1、D2）……直到秤到比較輕的那個為止。

幸運的話，可能第一次就找到假金幣。如果衰洨，假金幣正好在最後一組，那麼最糟的情況是──總共要秤4次！

（3）比較聰明的做法：二分法。

1. 將8個金幣平均分成兩組，分別為（A1、A2、A3、A4）及（B1、B2、B3、B4）。
2. 把A組、B組分放兩邊秤，若A組＞B組，則B組包含那個假金幣，繼續下步驟。
3. 同上述作法，再把B組平均分成兩組，分別為（B1、B2）及（B3、B4），並分放兩邊秤。若（B1、B2）＞（B3、B4），則（B3、B4）包含那個假金幣，繼續下步驟。
4. 把（B3、B4）分放兩邊秤，若B3＞B4，則B4即為所求。

持續將金幣【均分對秤】的步驟，只剩兩個金幣時，只要再秤一次即可。不過，若是採用這種做法，就沒有所謂【第一次就找到假金幣】的幸運事了。所以這樣總共要秤3次，也就是㏒2（8）＝3次。（以2為底，8的對數）

（4）更快的做法：

1. 將8個金幣平均分成3組，分別為（A1、A2、A3）、（B1、B2、B3）及（C1、C2）。
2. 把A組、B組分放兩邊秤，若A組＝B組，則C組包含那個假金幣，繼續步驟3；若A組＞B組，則B組包含那個假金幣，繼續步驟4。
3. 把（C1、C2）分放兩邊秤，若C1＞C2，則C2即為所求。
4. 把（B1、B2）分放兩邊秤，若B1＝B2，則B3即為所求；若B1＞B2，則B2即為所求。

每次都儘可能平分成3堆，且至少有兩堆金幣個數相同。先把相同個數的那兩堆拿來秤，如果有一堆比較輕，那一堆一定包含那個假金幣，否則金幣就在沒秤的那一堆；再把包含假金幣的那堆，依上述的相同做法（儘可能平分成三堆……）繼續操作。8個金幣分成3組，此時我們所要處理的數量已從8降到3或2，比上述二分法的策略只降到4有效多了。不過，若是採用這種做法，就沒有所謂【第一次就找到假金幣】的幸運事了。所以這樣總共要秤2次！也就是㏒3（8）＝1.8927892607……，→2次。（以3為底，8的對數）

回應：濁水溪畔的國中生	2012-05-14 23:57:12	(IP:　)	T 3493_R 20	引　用

以【＃1】暖身問題來說，上述4種解決方案的【最糟的情況】由7次→ 4次→ 3次→ 2次。乍看似乎次數差別不大，那麼，同理，依【＃1】的4種解決方案，則：

【＃2】：已知128個金幣中有1個假金幣……

（1）128－1＝127次
（2）128÷2＝64次
（3）㏒2（128）＝7次
（4）㏒3（128）＝4.416508275，→5次

【＃3】：已知19748個金幣中有1個騜金假幣（ma-gay B）……

（1）19748－1＝19747次
（2）19748÷2＝9874次
（3）㏒2（19748）＝14.2694189297，→15次
（4）㏒3（19748）＝9.0030009689，→10次

由【＃1】、【＃2】、【＃3】可知，隨著數字愈來愈龐大複雜，倘若仍堅持採用（1）或（2）土法煉鋼，除非踩到狗屎運，否則秤到起笑的機率非常大！縱然是數字比較少的【＃1】，採用（1）也只有1/7的機率能比採用（4）的做法還爽！（可不是天天都是過年喔……）

問題的解決方案，經常不是單一而是多重選擇。基本上，我個人認為只要能夠把問題解決就是王道，只不過，在考量資源有限及其他條件限制等因素，我們不得不被迫選擇【最佳或最符合某種利益的solution】。

歹勢，明天還要考試，【＃4】、【＃5】的解答明天再po上來，先下線！各位前輩先進，晚安！

回應：天涯台客	2012-05-15 02:35:07	(IP:　)	T 3493_R 21	引　用

回應：濁水溪畔的國中生	2012-05-15 07:09:32	(IP:　)	T 3493_R 22	引　用

撥洋蔥？

厚~~！偶今天若是考爛了就是台客前輩害滴！

來去讀冊，881

回應：正反修羅	2012-05-15 12:18:57	(IP:　)	T 3493_R 23	引　用

㏒>>>>Google翻譯

名詞
原木
航海日誌
木頭

--------------------------------------------------------------------------------

回應：正反修羅 2012-05-13 22:05:30 (IP: 　) T 3493_R 8 引　用

但執行步驟卻只有增加幾次而已，而這也正是【數學】御繁為簡的奧義！（ㄟ……好像洩露解決的方式……^__*）
>>>>
名詞
原木
航海日誌
木頭
^__^噓！！以X為底

回應：濁水溪畔的國中生	2012-05-15 18:56:32	(IP:　)	T 3493_R 24	引　用

【更正R22】：撥洋蔥 → 剝洋蔥？

R 23>>㏒>>>>Google翻譯
R 8>>^__^噓！！以X為底
==============================

正反前輩，暗安！

當您說【以X為底】時，就已經洩露天機了……^__^

回應：濁水溪畔的國中生	2012-05-15 21:27:26	(IP:　)	T 3493_R 25	引　用

誠如台客前輩所言【整人的陷阱又來了？】──在解決【＃1】~【＃3】同質性的系列問題之後，可能會形成思考慣性的盲點──由於一直在【比較】，所以暫時忘了天平原本就是測量質量的度量衡儀器，完整的天平組是有包括砝碼的。不過這可別怪我，題目本來就說──現在天平只能【秤】1次……，或許這在思索【＃4】延伸問題時容易相打電。

同時，我在題目加了【每袋數量不等（數十個至數百個）】的條件，以避免類似小烏龜前輩的【解決方案】……（很容易被【魯】……）
↓↓↓↓↓
**********************************************
回信發言人:娑訶, on May 14/2012 22:50:57 (IP code: X.X.253.150)
一次全放在地磅~ 知道總重量後
再一袋一袋拿起來遞減下去就知道每袋重量了
Record ID: 1336907360R051 From: 台灣
**********************************************

以下解答，僅供各位前輩先進參考。

【＃4】：延伸問題──已知有10袋金幣，每袋數量不等（數十個至數百個），其中有1袋是假的，真的金幣每個10 g，假的金幣每個9 g。現在天平只能秤1次，請問該如何操作，就可以得知那一袋是假金幣？

1. 將10袋金幣依序編號＃1、＃2、......＃10。
2. 自每個袋子取金幣，編號幾號就取幾個，2號就拿2個，8號就拿8個，一共55個金幣。
3. 秤55個金幣。如果全部都是真的金幣，則應該是550 g，而每個假的金幣比真的少1 g，所以我們可以根據少幾克來判斷那一袋是假金幣。

比如說，秤出來是543 g，表示有7枚金幣是假的，那麼由【編號幾號就取幾個】可知──第7袋就是。

回應：濁水溪畔的國中生	2012-05-15 21:28:00	(IP:　)	T 3493_R 26	引　用

【補充】：小烏龜前輩的【解答】緣由……

**********************************************
回信發言人:999-純銅, on May 14/2012 22:04:22 (IP code: X.X.197.241)
來點不太傷大腦的問題~
有4大袋重量不同體積都相同的銅幣~ 每袋有2百萬枚
只知道這四袋銅幣
一枚分別重 9克 8克 7克與 6克
4種不同重量但不知道分別是裝在哪一袋~
如何只用地磅磅一次~
就能知道這四大袋銅幣分別有多重?
Record ID: 1336907360R050 From: 台灣
**********************************************
回信發言人:娑訶, on May 14/2012 22:50:57 (IP code: X.X.253.150)
就把4大袋一次全放在地磅~ 知道總重量後
再一袋一袋拿起來遞減下去就知道每袋重量了
跟古代稱大象的原理一樣啦~ 大家晚安了 :)
Record ID: 1336907360R051 From: 台灣
**********************************************
回信發言人:新游泳池不能用, on May 14/2012 22:53:44 (IP code: X.X.160.144)
>>就把4大袋一次全放在地磅~ 知道總重量後
再一袋一袋拿起來遞減下去就知道每袋重量了
這應該不算秤1次
應該算秤4次
Record ID: 1336907360R052 From: 美國
**********************************************
回信發言人:濁水溪畔的國中生, on May 14/2012 23:01:32 (IP code: X.X.245.68)
我認為這題利用10進制結構即可求解。將袋編號＃1~＃4，分別取1000、100、10、1枚銅幣磅一次，由各位數的數字即知對應的袋子裝何種銅幣。
Record ID: 1336907360R054 From: 台灣
**********************************************
回信發言人:濁水溪畔的國中生, on May 14/2012 23:04:19 (IP code: X.X.245.68)
例如磅重顯示：6987，則＃1裝6克、＃2裝9克、＃3裝8克、＃4裝7克
Record ID: 1336907360R055 From: 台灣
**********************************************

回應：濁水溪畔的國中生	2012-05-15 21:29:11	(IP:　)	T 3493_R 27	引　用

最後，【＃5】：變化問題──已知12個金幣中有1個假金幣，但不知道假的金幣比較輕或是比較重。請問用天平最少秤幾次，就可以得知那一個是假金幣？

2008年國北教大資管所的計概也出了相同的題目，各位前輩先進可參考小周前輩所提供的解答。（請容我偷懶一下，留些腦力應付明天的考試）

↓↓↓↓↓
*****************************************
回信發言人:小周, on May 13/2012 22:47:56 (IP code: X.X.215.111)
十幾年前我開的話題..
http://darkroom.idv.tw/anikond800e/dir_show.asp?file=950&mana=0&page=1&area=8
Record ID: 1336907360R018 From: 台灣
*****************************************

經過這幾道題目的鳥力激盪，相信各位前輩先進的鳥力必定……【 Vxxxxx! 】^+++++++^

先下線K書，晚安！

回應：天涯台客	2012-05-16 01:11:00	(IP:　)	T 3493_R 28	引　用

　
　
　　● 資優高材生帥斃了！Funny、輕鬆一下。
　
　

回應：濁水溪畔的國中生	2012-05-16 07:04:33	(IP:　)	T 3493_R 29	引　用

台客前輩，米國早安！^__^

謝謝您的分享

回應：竹根	2012-05-17 11:18:35	(IP:　)	T 3493_R 30	引　用

【＃2】：已知128個金幣中有1個假金幣……

（1）128－1＝127次
（2）128÷2＝64次
（3）㏒2（128）＝7次
（4）㏒3（128）＝4.416508275，→5次

【＃3】：已知19748個金幣中有1個騜金假幣（ma-gay B）……

（1）19748－1＝19747次
（2）19748÷2＝9874次
（3）㏒2（19748）＝14.2694189297，→15次
（4）㏒3（19748）＝9.0030009689，→10次
*****************************************************************************

挖竹筍挖出的結果

（3）㏒2（19748）＝14.2694189297，→15次
（4）㏒3（19748）＝9.0030009689，→10次

三分法會有瞎貓的機會

（4）㏒3（19748）＝9.0030009689，→10次-1 次

回應：竹根	2012-05-17 11:35:57	(IP:　)	T 3493_R 31	引　用

>>（4）㏒3（128）＝4.416508275，→5次

128--> 44、 42=42

-->16、 14=14

-->6、5=/=5

-->1、2=2

1是死老鼠，４次成功。

歸納：三分法會有瞎貓的機會

（4）㏒3（19748）＝9.0030009689，→10次-1 次

回應：竹根	2012-05-17 11:38:09	(IP:　)	T 3493_R 32	引　用

挖竹筍還要趕所得稅申報，日月無光，累！

回應：正反修羅	2012-05-17 13:26:45	(IP:　)	T 3493_R 33	引　用

挖竹筍還要趕所得稅申報，日月無光，累！

>>>
5月31日還沒到

急著繳稅給馬狗政府？？？

回應：天涯台客	2012-05-17 15:39:18	(IP:　)	T 3493_R 34	引　用

討海大人

幾時回來？樂不思蜀啦？

正反修羅賢拜

老灰仔郎跟您請安。高材生那幾題竹根大ㄟ解的對不對？看攏嘸。

回應：天涯台客	2012-05-17 15:42:49	(IP:　)	T 3493_R 35	引　用

沒三小路用，偶貼錯欄了。（*﹏* ）

回應：濁水溪畔的國中生	2012-05-17 18:49:24	(IP:　)	T 3493_R 36	引　用

R31>>歸納：三分法會有瞎貓的機會
（4）㏒3（19748）＝9.0030009689，→10次-1 次
==============================

竹根前輩，暗安！

您說的沒錯。^__^

但是我在R6有先補充說明喔──以上問題中所謂【用天平最少秤幾次】是指──在您所提出的操作模式中，最糟的情況須秤幾次才能找到假金幣？

回應：gagaman	2012-05-17 20:55:14	(IP:　)	T 3493_R 37	引　用

程式中有非常多的機會，需要思考類似的題形。

舉例：

本站開欄標題超過１８字斷行符號的嵌入，程式就要在最少動作中找看有沒有（當然有現成函數），如何才能更快地找出來在那裡，是不是放對地方，而且要歸納出公式，減少cpu的負荷。

回應：濁水溪畔的國中生	2012-05-17 21:24:29	(IP:　)	T 3493_R 38	引　用

R37>>程式中有非常多的機會，需要思考類似的題形。
==============================

gagaman前輩，暗安！

我想這就是R3所提及的概念。不過我是有看沒有懂，R3是貼來模糊焦點，讓正反前輩【受迫性三太子附身】……^+++++++++^

回應：竹根	2012-05-18 11:22:31	(IP:　)	T 3493_R 39	引　用

>>那幾題竹根大ㄟ解的對不對？看攏嘸。

128--> 44、 42=42　（128個分3份，42個的兩份等重，知假幣在44那一堆

-->16、 14=14　　　（44個再分3份，14個的兩份相等，知假幣在16那一堆

-->6、5=/=5　　　（16個再分3份，5的兩份不等重，知假幣在輕的5個那一堆

-->1、2=2　　　　（輕的5個分3份，2個的兩份等重，瞎貓抓列沒稱的死老鼠是假幣　

1是死老鼠，４次成功。
***********************************************************************************************

台客老大！不好意思，鄉巴佬口齒不清，讓您看看攏嘸，因為這個程序並不必然在第一次被執行，是有時恰好被抓到，所以是瞎貓程序。

就算這個瞎貓沒抓到，只要再一次，假幣必無所盾形，５次必定達成任務。

如果-->1、2=2　　（輕的5個分3份，2個的兩份等重，瞎貓抓列沒稱的死老鼠是假幣

變成　1、2 =/= 2 　　則較輕的兩個要再稱一次，才能找到假幣。

４次是瞎貓效果，要時機湊巧才能做到。　

回應：濁水溪畔的國中生	2012-05-19 18:28:23	(IP:　)	T 3493_R 40	引　用

狗尾續貂：

1. 每次都儘可能平分成3堆，且至少有兩堆金幣個數相同。

2. 先把相同個數的那兩堆拿來秤，如果有一堆比較輕，那一堆一定包含那個假金幣，否則金幣就在沒秤的那一堆。

3. 再把包含假金幣的那堆，依上述的相同做法（儘可能平分成三堆……）繼續操作。

4. 最後若剩下5個，則繼續步驟5；若剩下7個，則繼續步驟6。

5. 將5個金幣成3組，分別為（A1、A2）、（B1、B2）及（C1）。

5-1. 把A組、B組分放兩邊秤，若A組＝B組，則（C1）就是那個假金幣。

5-2. 若A組＞B組，則B組包含那個假金幣，把（B1、B2）分放兩邊秤即可得知假金幣。

6. 將7個金幣平均分成3組，分別為（A1、A2、A3）、（B1、B2、B3）及（C1）

6-1. 把A組、B組分放兩邊秤，若A組＝B組，則（C1）就是那個假金幣。

6-2. 若A組＞B組，則B組包含那個假金幣，把（B1、B2）分放兩邊秤，若B1＝B2，則B3即為所求；若B1＞B2，則B2即為所求。

上述【5-1】或【6-1】就是竹根前輩所說的瞎貓機會，可以少掉【5-2】或【6-2】的步驟。