文档文库
手机版
投诉建议
热门搜索： 心得体会 演讲稿 思想汇报
首页 > 韩信点兵(同余问题)

韩信点兵(同余问题)

发布时间：   来源：文档文库   
小 中 大
字号：
手机查看
二韩信点兵
例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＋12×n(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，…，
第2步再列出满足其中第二个条件的数，即除以5余3的数：3，8，13，18，23，28，….
第3步归纳前面第3步首先出现的公共数是8.
8就是满足除以3余2，除以5余3的最小的那个数。3与5的最小公倍数是15.两个条件合并成一个就是8＋15×n(n=0，1，2，…。列出这一串数是8，23，38，…，
第4步再列出满足其中第三个条件的数，即除以7余2的数2，9，16，23，30，…，
第5步归纳第3步第4步得到的数列。就得出符合题目条件的最小数是23.事实上，我们已把题目中
三个条件合并成一个。3，5，7的最小公倍数是105，满足三个条件的所有数是23+105×n(n=0，1，2，…第6步那么韩信点的兵在1000-1100之间，应该是23+105×10=1073人
如果你随便拿一把蚕豆（数目约在100粒以内），假如3粒一数余1粒，5粒一数余2粒，7粒一数余2粒，那么，原有蚕豆有多少粒呢？

中国剩余定理（韩信点兵）的计算方法是：
第1步用3个一数剩下的余数，将它乘以70（因为70既是5与7的倍数，又是以3去除余1的数）；第2步用5个一数剩下的余数，将它乘以21（因为21既是3与7的倍数，又是以5去除余1的数）；第3步7个一数剩下的余数，将乘以15（因为15既是3与5的倍数，又是以7去除余1的数），第4步将这些数加起来，若超过105（105是3,5,7的最小公倍数），就减掉105，如果剩下来的数目还是比105大，就再减去105，直到得数比105小为止。这样，所得的数就是原来的数了。根据这个道理，你可以很容易地把前面的题目列成算式：1×70＋2×21＋2×15－105＝142－105＝37因此，可以知道，原来这一堆蚕豆有37粒。
【例4】求最小非负整数N，使他在除以5,7,11以后所得余数分别是a,b,c。【韩信点兵法口诀的原理】
①能被7,11除尽数是77k,当k=3，即231除5正好余1，231a除5正好余a。②能被5,11除尽数是55k,当k=6，即330除7正好余1，330b除7正好余b。③能被5,7除尽数是35k,当k=6，即210除11正好余1，210c除11正好余c。那么231a+330b+210c除以5,7,11以后所得余数一定分别是a,b,c。
5,7,11的最小公倍数是385，根据【符合要求的最小数N必满足0≤N＜385】，所以当231a+330b+210c大于或等于385时，还必须减去若干个385直到比385小为止，才可以得到符合题意要求的最小数。【说明】231a+330b+210c+385k也一定满足“除以5,7,11以后所得余数分别是a,b,c”。
【例5】求最小非负整数N，使他在除以5,7,11以后所得余数分别是3,5,7。【解】231a+330b+210c=231×3+330×5+210×7=3813.
因为3813＞385，所以减去9个385后，得到比385小的3813-9×385=348就是符合题意的最小非负整数了
这些题可转化为余数问题解决。如果你知道中国剩余定理，可直接用，如果不知道，也没有关系，可采取余数常用方法，先找一个最小的满足第一个数，然后调整一下满足第二个数，再调整满足第三个数。在调整时，一定不要改变你前面已经满足的数的特点，每次加前面已经满足的数的最小公倍数，这样它的余数就不会被改变。

课堂练习(用上面介绍的两种方法
1有一个数，除以3余1，除以5余3，问这个数除以16余几？

本文来源：https://www.2haoxitong.net/k/doc/8b12f31b824d2b160b4e767f5acfa1c7aa00822e.html

《韩信点兵(同余问题).doc》
将本文的Word文档下载到电脑，方便收藏和打印
推荐度：
点击下载文档

文档为doc格式
相
关
案
例

相关推荐

推荐内容

1.1.3 一个粗心的故事 有理数混合运算 一种基于手机APP蓝牙遥控的空调及其控制系统 彷徨读后感800字高中 4M2与汇率：中国“货币超发”会令人民币必有一跌吗？ 买年货作文600字 社会主义核心价值观征文比赛活动方案 静观育儿--杯子打碎后的四种结局 钢铁是怎样炼成的读后感400字左右 人民医院病案管理科工作职责范本 新年的钟声作文5篇
网站内容来自网络，如有侵权请联系我们，立即删除！ Copyright © 范文写作网京ICP备16605803号