資源簡介

(共16張PPT)
第11課
韓信點兵同余法的實現
浙教版六年級上冊
目錄
CONTENTS
①
韓信點兵同余法的實現
01
韓信點兵同余法的實現
例 1我們先考慮下列的問題:假設兵不滿一萬，每5人一列、9人一列、13人一列、17人一列都剩3人，則兵有多少
首先我們先求5、9、13、17之最小公倍數9945(注:因為5、9、13、17為兩兩互質的整數，故其最小公倍數為這些數的積)，然后再加3，得9948(人)。
例 2有一個數，除以3余2，除以4余1，問這個數除以12余幾
解 :除以3余2的數有:2，5，8，11，14，17，20，23….它們除以12的余數是:2，5，8，11，2，5，8，11，….除以4余1的數有:1，5，9，13，17，21，25，29，….它們除以12的余數是:1，5，9，1，5，9，….一個數除以12的余數是唯一的.上面兩行余數中，只有5是共同的，因此這個數除以12的余數是5.如果我們把問題改變一下:有一個數，除以3余2，除以4余1，問這個數是幾 不求被12除的余數，而是求這個數是幾 .
很明顯，這個數最小是5，滿足條件的數是很多的，它們是5+12xn(n=0，1，2，3…)，事實上，我們首先找出5后，注意到12是3，4的最小公倍數，再加上12的整數倍，就都是滿足條件的數.這樣就是把“除以3余2，除以4余1”兩個條件合并成“除以12余5”一個條件.題目中提出的條件有三個，我們可以先把兩個條件合并成一個.然后再與第三個條件合并，就可找到答案.
例3秦朝末年，楚漢相爭.韓信帥1500名將士與楚王大將李鋒交戰。苦戰一場，楚軍不敵，敗退回營，漢軍也死傷四五百人，于是韓信整頓兵馬也返回大本營。當行至一山坡，忽有后軍來報，說有楚軍騎兵追來。只見遠方塵土飛揚，殺聲震天。漢軍本來已十分疲憊，這時隊伍大嘩。韓信急速點兵迎敵。他命令士兵3人一排，結果多出2名;接著命令士兵5人一排，結果多出3名;他又命令士兵7人一排，結果又多出2名。韓信馬上向將士們宣布:我軍有1073人，敵人不足五百，我們居高臨下，以眾擊寡，一定能打敗敵人。一個數除以3余2，除以5余3，除以7余2，求符合條件的最小數。
解:第1步先列出滿足其中一個條件的數(一般從小到大)，即除以3余2的數:2，5，8，11，14，17，20，23，26，…，
01
第 2步再列出滿足其中第二個條件的數，即除以5余3的數:3，8，13，18，23，28，….
02
第 3步歸納前面第3步首先出現的公共數是8，8就是滿足除以3余2，除以5余3的最小的那個數。3與5的最小公倍數是15.兩個條件合并成一個就是8+15xn，(n=0，1，2，…) 。列出這一串數是8，23，38，…，
03
第4步再列出滿足其中第三個條件的數，即除以7余2的數，2，9，16，23，30，... ，
04
05
第5步歸納第3步第4步得到的數列。就得出符合題目條件的最小數是23.事實上，我們已把題目中三個條件合并成一個。3，5，7的最小公倍數是105，滿足三個條件的所有數是23+105xn (n=0，1，2，…)。
第6步那么韓信點的兵在1000-1100之間，應該是23+105x10=1073人。
06
如果你隨便拿一把蠶豆(數目約在100粒以內)，假如3粒一數余1粒，5粒一數余2粒，7粒一數余2粒，那么，原有蠶豆有多少粒呢
中國剩余定理(韓信點兵)的計算方法是:
01
第1步用3個一數剩下的余數，將它乘以70(因為70既是5與7的倍數，又是以3去除余1的數);
02
第 2步用5個一數剩下的余數，將它乘以21(因為21既是3與7的倍數，又是以5去除余1的數);
中國剩余定理(韓信點兵)的計算方法是:
中國剩余定理(韓信點兵)的計算方法是:
03
第3步7個一數剩下的余數，將乘以15(因為15既是3與5的倍數，又是以7去除余1的數)。
04
第4步將這些數加起來，若超過105(105是3,5,7的最小公倍數)，就減掉105，如果剩下來的數目還是比105大，就再減去105，直到得數比105小為止。這樣，所得的數就是原來的數了。根據這個道理，你可以很容易地把前面的題目列成算式:1x70+2x21+ 2x15-105=142-105=37因此，可以知道，原來這一堆蠶豆有37粒。
中國剩余定理(韓信點兵)的計算方法是:
練習1
練習1
有一個數，除以3余1，除以5余3，問這個數除以16余幾
感謝聆聽

展開更多......

收起↑