3.3  歸納法

　　當我們要解決一個問題的時候，可以先分析這個問題的幾種簡單的、特殊的情況，從中發(fā)現(xiàn)并歸納出一般規(guī)律或作出某種猜想，從而找到解決問題的途徑。這種從特殊到一般的思維方法稱為歸納法。

例10 將100以內(nèi)的質(zhì)數(shù)從小到大排成一個數(shù)字串，依次完成以下5項工作叫做一次操作：

　　（1）將左邊第一個數(shù)碼移到數(shù)字串的最右邊；

　�。�2）從左到右兩位一節(jié)組成若干個兩位數(shù)；

　�。�3）劃去這些兩位數(shù)中的合數(shù)；

　�。�4）所剩的兩位質(zhì)數(shù)中有相同者，保留左邊的一個，其余劃去；

　　（5）所余的兩位質(zhì)數(shù)保持數(shù)碼次序又組成一個新的數(shù)字串。

　　問：經(jīng)過1999次操作，所得的數(shù)字串是什么？

解：第1次操作得數(shù)字串711131131737；

　　第2次操作得數(shù)字串11133173；

　　第3次操作得數(shù)字串111731；

　　第4次操作得數(shù)字串1173；

　　第5次操作得數(shù)字串1731；

　　第6次操作得數(shù)字串7311；

　　第7次操作得數(shù)字串3117；

　　第8次操作得數(shù)字串1173。

　　不難看出，后面以4次為周期循環(huán)，1999=4×499+3，所以第1999次操作所得數(shù)字串與第7次相同，是3117。

例11 有100張的一摞卡片，玲玲拿著它們，從最上面的一張開始按如下的順序進行操作：把最上面的第一張卡片舍去，把下一張卡片放在這一摞卡片的最下面。再把原來的第三張卡片舍去，把下一張卡片放在最下面。反復(fù)這樣做，直到手中只剩下一張卡片，那么剩下的這張卡片是原來那一摞卡片的第幾張？

分析與解：可以從簡單的不失題目性質(zhì)的問題入手，尋找規(guī)律。列表如下：

　　設(shè)這一摞卡片的張數(shù)為N，觀察上表可知：

　�。�1）當N=2a（a=0，1，2，3，…）時，剩下的這張卡片是原來那一摞卡片的最后一張，即第2a張；

　�。�2）當N=2a+m（m＜2a）時，剩下的這張卡片是原來那一摞卡片的第2m張。

　　取N=100，因為100=26+36，2×36=72，所以剩下這張卡片是原來那一摞卡片的第72張。

　　說明：此題實質(zhì)上是著名的約瑟夫斯問題：

　　傳說古代有一批人被蠻族俘虜了，敵人命令他們排成圓圈，編上號碼1，2，3，…然后把1號殺了，把3號殺了，總之每隔一個人殺一個人，最后剩下一個人，這個人就是約瑟夫斯。如果這批俘虜有111人，那么約瑟夫斯的號碼是多少？

　　例12 要用天平稱出1克、2克、3克……40克這些不同的整數(shù)克重量，至少要用多少個砝碼？這些砝碼的重量分別是多少？

分析與解：一般天平兩邊都可放砝碼，我們從最簡單的情形開始研究。

　�。�1）稱重1克，只能用一個1克的砝碼，故1克的一個砝碼是必須的。

　�。�2）稱重2克，有3種方案：

　　①增加一個1克的砝碼；

　　②用一個2克的砝碼；

　　③用一個3克的砝碼，稱重時，把一個1克的砝碼放在稱重盤內(nèi)，把3克的砝碼放在砝碼盤內(nèi)。從數(shù)學(xué)角度看，就是利用3-1=2。

　�。�3）稱重3克，用上面的②③兩個方案，不用再增加砝碼，因此方案①淘汰。

　�。�4）稱重4克，用上面的方案③，不用再增加砝碼，因此方案②也被淘汰�？傊�，用1克、3克兩個砝碼就可以稱出（3+1）克以內(nèi)的任意整數(shù)克重。

　�。�5）接著思索可以進行一次飛躍，稱重5克時可以利用

　　9-（3+1）=5，

　　即用一個9克重的砝碼放在砝碼盤內(nèi)，1克、3克兩個砝碼放在稱重盤內(nèi)。這樣，可以依次稱到1+3+9=13（克）以內(nèi)的任意整數(shù)克重。

　　而要稱14克時，按上述規(guī)律增加一個砝碼，其重為

　　14+13=27（克），

　　可以稱到1+3+9+27=40（克）以內(nèi)的任意整數(shù)克重。

　　總之，砝碼的重量為1，3，32，33克時，所用砝碼最少，稱重最大，這也是本題的答案。

　　這個結(jié)論顯然可以推廣，當天平兩端都可放砝碼時，使用1，3，

　　這是使用砝碼最少、稱重最大的砝碼重量設(shè)計方案。