资源简介

(共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余几
感谢聆听

展开更多......

收起↑