巧斷金鏈中學(xué)趣味數學(xué)教案
巧斷金鏈中學(xué)趣味數學(xué)教案
巧斷金鏈中學(xué)趣味數學(xué)教案
一位來(lái)自阿肯色州的年輕太太格羅麗亞，正在加利福尼亞州旅行.她想在旅館租用一個(gè)房間，租期一周.辦事員此時(shí)正心緒不佳。辦事員：房費每天20元，要付現錢(qián).格羅麗亞：很抱歉，先生，我沒(méi)帶現錢(qián).但是我有一根金鏈，共7節，每節都值20元以上.辦事員：好吧，把金鏈給我.格羅麗亞：現在不能給你.我得請珠寶匠把金鏈割斷，每天給你一節，等到周末我有了現錢(qián)再把金鏈贖回.辦事員終于同意了，但格羅麗亞必須決定如何斷開(kāi)金鏈的方法.格羅麗亞：我該三思而行，因為珠寶匠是按照他所切割和以后重新連接的節數來(lái)索價(jià)的.格羅麗亞想了一下，悟到她不必把每一節都割斷，因為她可以把一段段金鏈換進(jìn)換出，以這種方式來(lái)付房費.當她算出需要請珠寶匠割斷的節數時(shí)，她幾乎不能自信。你想一想需要割開(kāi)多少節?
只需要割開(kāi)一節。這一節應是從一端數起的第三節.把金鏈斷開(kāi)成1節，2節，4節這樣三段后就能以換進(jìn)換出的方式每天付給辦事員一節作為房費。
啊哈!領(lǐng)悟到下列兩點(diǎn)才能解題.第一，至少需要有1節，2節，4節這樣三段(即其節數成二重級數的一些段)，這樣才能以各種不同的組合方式組成1節，2節，3節，4節，5節，6節和7節.我們在藥品混亂問(wèn)題中已經(jīng)知道，這就是作為二進(jìn)制記數法基礎的冪級數.
第二，只需要割開(kāi)一節就可以把金鏈分成符合要求的三段.關(guān)于這個(gè)問(wèn)題，若把金鏈的長(cháng)度增加，則可以想出一些新的問(wèn)題.例如，假設格羅麗亞有一根63節的金鏈，她想把金鏈割開(kāi)，以上面那種方式來(lái)付63天的房費(價(jià)格不變).要達到此種目的只需要割開(kāi)三節.你想出來(lái)了嗎?你能否根據金鏈的不同長(cháng)度設計一個(gè)通用的解題程序，要求分割開(kāi)的節數為最少?
有一個(gè)有趣的變相問(wèn)題：若所經(jīng)手的n節首尾相連的閉合回路，例如說(shuō)格羅麗亞有一串金項鏈，由79節相連而成，若每天房費為一節，試問(wèn)最少需要分割開(kāi)幾節才能支付79天房費?
所有這些問(wèn)題都跟二進(jìn)制記數法有密切的關(guān)系.比如格羅麗亞的63節金項鏈如何分割?只要將63化成二進(jìn)制表示：等于111111即63=1+2+4+8+16+32只要將從第二節開(kāi)始的兩節割開(kāi)，再將從第八節開(kāi)始的八節割下來(lái)，和從第32節開(kāi)始的32節割下來(lái)即可，這樣就有了從1，2，3，4，5，6，直到63的所有節數.一般地，若有n節金鏈，n是形如2k-1類(lèi)型的數，將n化成二進(jìn)制表示，再將所有1的位置所代表的2的冪的數相間隔地割開(kāi)即可達到目的.但是對于其他任意類(lèi)型的數，卻不能奏效，比如對于格羅麗亞的79節金項鏈，79的二進(jìn)制記數法表示為1001111.即79=1+2+4+8+0+0+64，這樣從1到15都能表示，可是從16到63都沒(méi)法表示，我把這個(gè)問(wèn)題做到這里，也一時(shí)糊涂起來(lái)，但這個(gè)問(wèn)題畢竟不是很復雜，咱們也學(xué)一學(xué)閔科夫斯基在課堂上口出狂言要解決四色問(wèn)題的勁頭，摸索著(zhù)來(lái)解決一把.咱們可以這樣：你不是要求節數最少嗎?假設n=a+b其中a是已經(jīng)找到的最大的那一節數，b是比n小的已經(jīng)解決了的金鏈問(wèn)題，由于b已經(jīng)解決，因此b的拆分能夠表示從1，2，3，...b-1，b的所有金鏈節數，而再大一些的數就不能夠表示了，比如b+1，所以必須要a參加進(jìn)來(lái)，如果n是奇數，可令a=b+1，這樣n=2b+1，所以b=(n-1)/2，a=(n+1)/2，這樣就找到了最大的一節的節數a，然后對b=(n-1)/2繼續應用如上的辦法，即可解決問(wèn)題.如果n是偶數，可令a=b，這樣雖然a本身不能表示出b+1，但是可以從b的拆分中拿出一個(gè)1來(lái)(這個(gè)1是必須存在的，因為要表示從1，2，3，...b-1，b的所有數)與a組成a+1也就是b+1.所以n=a+b=2a=2b，a=b=n/2.這樣也找到了n為偶數時(shí)最大的一節金鏈的節數.對于b繼續如上的過(guò)程，就可以找到全部應該斷開(kāi)的金鏈節數，我算出了從1到15的所有拆分如下：
1=1
2=1+1
3=1+2
4=1+1+2
5=1+1+3
6=1+2+3
7=1+2+4
8=1+1+2+4
9=1+1+2+5
10=1+1+3+5
11=1+1+3+6
12=1+2+3+6
13=1+2+3+7
14=1+2+4+7
15=1+2+4+8
對于上面的格羅麗亞太太的79節金項鏈，79+1=80，80/2=40，所以最大的一節就是40節，79-40=39，39+1=40，40/2=20，所以第二大的一節就是20節，39-20=19，19+1=20，20/2=10，第三大的一節是10節，19-10=9，9+1=10，10/2=5，又找到了一節是5，9-5=4，4的表示法如上已經(jīng)列出來(lái)了：4=1+1+2.最后得到79節的金項鏈的分割法：1，1，2，5，10，20，40.過(guò)去我也碰到過(guò)一道類(lèi)似的題，是23節金項鏈，也能夠很容易地解決：23+1=24，24/2=12;23-12=11，11=1+1+3+6;所以23的分割法為：1，1，3，6，12.顯然，對于2k-1類(lèi)型的數，用這里的辦法與用二進(jìn)制記數法得出的結果是一致的.
從上面所列出的拆分法可以看出，如果2k=2k+1，那么n一定要用k+1個(gè)數來(lái)表示，即：n=a0+a1+a2+...+ak.
可以用數學(xué)歸納法很容易地證明這是正確的.那么還有沒(méi)有比這更少的分割法呢?可以證明沒(méi)有了.從我們的分析方法中可以看出，這是一個(gè)構造性的推理過(guò)程，假如還有比這更少的分割法，那么相當于在表達式n=a0+a1+a2+...+ak.中進(jìn)行了某些組合，比如將a1+a2合并成新的a1，那么原來(lái)的有些組合就表示不出來(lái)了，例如a0+a2，就沒(méi)有辦法組合了.當然，一個(gè)數的拆分不是唯一的，前面的23節金鏈還可以分成1，2，3，6，11.你可以試試，這種分割法照樣能滿(mǎn)足要求.前面的分析中也可以把(n-1)/2留下來(lái)作為最大的節數，但是這樣分出來(lái)的節數就不一定都是最少的了，例如把15這樣分割，會(huì )得到：1，1，2，4，7.雖然能夠滿(mǎn)足付房費的要求，但是就不是最優(yōu)解了.最后總結一下，把前面的算法過(guò)程公式化可以得到：
k-1r-1k-1
n=(n+c0)/2+{[n-cs2s+cr2r]/2r+1}+[n-cr2r]/2k
r=1s=0r=0
其中c0，c1，...ck-1等等是1或是0取決于每一步得出的數的奇偶性.其實(shí)最后一項等于1，這樣可以得出：
k-1
n-2k=cr2r
r=0
a0=(n+c0)/2
i-1
ai=[n-cs2s+ci2i]/2i+11(i=1，2，3，...k-1)
s=0
ak=1
當然，編成計算機程序還是用遞歸程序比較簡(jiǎn)單.這里列出這些公式是為了保留存照。
【巧斷金鏈中學(xué)趣味數學(xué)教案】相關(guān)文章：
小學(xué)美術(shù)《巧折巧剪》教學(xué)設計03-15
關(guān)于《有趣的七巧板》教學(xué)設計（通用11篇）07-08
趣味語(yǔ)文活動(dòng)課教案01-30
職工趣味運動(dòng)會(huì )感想（精選14篇）05-08
三年級上冊巧求周長(cháng)教學(xué)設計（通用11篇）08-07
數學(xué)教案：圓的認識02-12
認識球體數學(xué)教案03-20
數學(xué)教案模版之數軸03-20