【2017年整理】韩信点兵问题的初等解法

660和108题题目660：韩信点兵题目描述：韩信在战斗中点兵，他看到的队列有一定的规律。

第一个士兵报数1，第二个士兵报数2，第三个士兵报数3，以此类推。

当士兵报数到某个数时，他们将会喊“嘿”替代这个数字，即士兵报数4时喊“嘿”，报数8时也喊“嘿”，以此类推。

你的任务是写一个程序，给定一个士兵报数的上限数n，输出士兵报数的序列。

660题解：要解决这个问题，我们可以使用一个循环来依次遍历1到n，然后判断每个数是否是4的倍数，如果是的话就将其替换为“嘿”。

最后，将所有的数字拼接起来，就得到了士兵报数的序列。

具体的实现方法如下：1. 首先，创建一个空的字符串result，用来存储最终的报数序列。

2. 使用一个循环从1遍历到n，对于每个数i，执行以下步骤：- 如果i是4的倍数，将字符串result拼接上“嘿”，否则将i转换为字符串并拼接到result上。

3. 循环结束后，输出result即可。

下面是一个使用Python语言实现的示例代码：```pythondef hanxin_pointing(n):result = ""for i in range(1, n+1):if i % 4 == 0:result += "嘿"else:result += str(i)return resultn = int(input("请输入士兵报数的上限数n："))print(hanxin_pointing(n))```通过运行上述代码，我们可以根据输入的士兵报数的上限数n得到相应的报数序列。

例如，当输入n为15时，输出的报数序列为："123嘿567嘿91213嘿15"。

题目108：水仙花数题目描述：水仙花数是指一个n位数（n≥3），它的每个位上的数字的n次幂之和等于它本身。

例如，153是一个水仙花数，因为1^3 + 5^3 + 3^3 = 153。

[趣味数学] 韩信点兵民间故事《韩信点兵》：韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的兴建立下了卓绝的功劳。

据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从1至5报数，也记下最后一个士兵所报之数；最后令士兵从1至7报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵。

比如，已知军队人数大概在1000-1100左右，如果1-3报数余2人，1-5报数余3人，1-7报数余2人，则韩信立刻知道总人数1073人。

汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。

于是每次出战都士气大振，经常大获全胜。

把韩信点兵问题再换个更简单的说法，就是说，有个数除3余2，除5余3，除7余2，问你这个数字最小是几？也可以给定一个范围，问你是几。

这类问题，纠结应该怎么下手解决呢？对于这样的问题，要先观察，是否存在规律，如果符合一定的规律，则可以通过简单口诀来实现；如果没有规律，那么就要通过一些特殊方法处理。

一、有规律问题的解法重要口诀：和同加和，差同减差，余同取余，最小公倍加先来说说最后一句，最小公倍加，意思是，不管什么情况，先把最小公倍数求出来，这个是作为基础。

然后根据不同情况进行辨别，如何继续处理。

（一）和同加和意思是，如果不同被除数和余数的和相同，那么就把这个和，加到最小公倍数上。

例：一个数除5余3，除6余2，除7余1解题思路：5、6、7的最小公倍数是210，因为5＋3＝6＋2＝7＋1＝8，所以这个数最小就是8，其余满足条件的数字是210的倍数＋8，比如218、428……（二）差同减差意思是，如果不同被除数和余数的差相同，那么就把这个差，用最小公倍数减掉。

例：一个数除5余3，除6余4，除7余5解题思路：5、6、7的最小公倍数是210，因为5－3＝6－4＝7－5＝2，所以这个数最小就是：210－2＝208，其余满足条件的数字是210的倍数＋208，比如418、628……（三）余同取余这个是最简单的了，意思是，如果余数都相同，直接把余数加到最小公倍数上。

本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==中国剩余定理的应用实例——韩信点兵物不知其数问题出自一千六百年前我国古代数学名著《孙子算经》。

原题为："今有物不知其数，三三数之二，五五数之三，七七数之二，问物几何?"这道题的意思是：有一批物品，不知道有几件。

如果三件三件地数，就会剩下两件;如果五件五件地数，就会剩下三件;如果七件七件地数，也会剩下两件。

问：这批物品共有多少件?变成一个纯粹的数学问题就是：有一个数，用3除余2，用5除余3，用7除余2.求这个数。

这个问题很简单：用3除余2，用7除也余2，所以用3与7的最小公倍数21除也余2，而用21除余2的数我们首先就会想到23;23恰好被5除余3，所以23就是本题的一个答案。

这个问题之所以简单，是由于有被3除和被7除余数相同这个特殊性。

如果没有这个特殊性，问题就不那么简单了，也更有趣儿得多。

我们换一个例子;韩信点一队士兵的人数，三人一组余两人，五人一组余三人，七人一组余四人。

问：这队士兵至少有多少人?这个题目是要求出一个正数，使之用3除余2，用5除余3，用7除余4，而且希望所求出的数尽可能地小。

如果一位同学从来没有接触过这类问题，也能利用试验加分析的办法一步一步地增加条件推出答案。

例如我们从用3除余2这个条件开始。

满足这个条件的数是3n+2，其中n是非负整数。

要使3n+2还能满足用5除余3的条件，可以把n分别用1，2，3，…代入来试。

当n=1时，3n+2=5，5除以5不用余3，不合题意;当n=2时，3n+2=8，8除以5正好余3，可见8这个数同时满足用3除余2和用5除余3这两个条件。

最后一个条件是用7除余4.8不满足这个条件。

我们要在8的基础上得到一个数，使之同时满足三个条件。

为此，我们想到，可以使新数等于8与3和5的一个倍数的和。

初中数学兴趣题目大全之韩信点兵
韩信点兵
韩信是我国汉代有名的大将，以前统率过千军万马，他敌手
下士兵的数量如数家珍。

他统计士兵数量有个独到的方法，
后代称为“韩信点兵”。

他的方法是这样的，队伍会合齐
后，他让士兵1、 2、3－－ 1、2、 3、 4、5－－ 1、 2、 3、 4、5、 6、 7 地报三次数，而后把每次的余数再报告给他，他便
知道队伍的实质人数和缺席人数。

他的这类计算方法历史上
还称为“鬼谷算”，“隔墙算”，“剪管术”，外国人则叫
“中国节余定理”。

有人用一首诗归纳了这个问题的解法：
三人同行七十稀，五树梅花廿一枝，七子团聚月正半，除百
零五便得悉。

这意思就是，第一次余数乘以70，第二次余数乘以 21，第三次余数乘以15，把这三次运算的结果加起来，
再除以105，所得的除不尽的余数即是所求之数（即总数）。

比如，假如 3 个 3 个地报数余 1， 5 个 5 个地报数余 2， 7 个 7 个地报数余 3，则总数为 52。

算式以下：
1×70＋2×21＋3×15＝157
157÷105＝152
下面给同学们出一道题，请用“韩信点兵法”算一算。

小红暑期时期帮着张二婶放鸭子，她总也数不清一共有多少
只鸭子。

她先是 3只 3只地数，结果剩3只；她又 5只 5
第 1页
只地数，结果剩 4 只；她又7 个 7 个地数了一遍，结果剩6只。

她算来算去仍是算不清一共有多少只鸭子。

小朋友，请
你帮着小红算一下，张二婶一共喂着多少只鸭子？
第 2页。

韩信点兵解法韩信点兵是一个有趣的猜数游戏。

如果你随便拿一把蚕豆（数目约在100粒左右），先3粒3粒地数，直到不满3粒时，把余数记下来；第二次再5粒5粒地数，最后把余数记下来；第三次是7粒一数，把余数记下来。

然后根据每次的余数，就可以知道你原来拿了多少粒蚕豆了。

不信的话，你还可以试验一下。

例如，假如3粒一数余1粒，5粒一数余2粒，7粒一数余2粒，那么，原有蚕豆有多少粒呢？这类题目看起来是很难计算的，可是我国古时候却流传着一种算法，名称也很多，宋朝周密叫它“鬼谷算”，又名“隔墙算”；杨辉叫它“剪管术”；而比较通行的名称是“韩信点兵”。

最初记述这类算法的是一本名叫《孙子算经》的书，后来在宋朝经过数学家秦九韶的推广，又发现了一种算法，叫做“大衍求一术”。

这在数学史上是极有名的问题，外国人一般把它称为“中国剩余定理”。

至于它的算法，在《孙子算经》上就已经有了说明，而且后来还流传着这么一道歌诀：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。

这就是韩信点兵的计算方法，它的意思是：凡是用3个一数剩下的余数，将它用70去乘（因为70是5与7的倍数，而又是以3去除余1的数）；5个一数剩下的余数，将它用21去乘（因为21是3与7的倍数，又是以5去除余1的数）；7个一数剩下的余数，将它用15去乘（因为15是3与5的倍数，又是以7去除余1的数），将这些数加起来，若超过105，就减掉105，如果剩下来的数目还是比105大，就再减去105，直到得数比105小为止。

这样，所得的数就是原来的数了。

根据这个道理，你可以很容易地把前面的五个题目列成算式：1×70＋2×21＋2×15－105 ＝142－105 ＝37 因此，你可以知道，原来这一堆蚕豆有37粒。

1900年，德国大数学家大卫·希尔伯特归纳了当时世界上尚未解决的最困难的23个难题。

后来，其中的第十问题在70年代被解决了，这是近代数学的五个重大成就。

最全汇总>>>上海公务员历年真题2017上海公务员考试行测：剩余定理之韩信点兵通过最新上海公务员考试资讯、大纲可以了解到，《行政职业能力测验》主要测查从事公务员职业必须具备的基本素质和潜在能力，测试内容包括言语理解与表达能力、判断推理能力、数理能力、常识应用能力和综合分析能力。

上海中公教育整理了上海市考资料大全供考生备考学习。

需要更多指导，请选择在线咨询一对一解答。

传说汉朝大将韩信用一种特殊方法清点士兵的人数。

他的方法是：让士兵先列成三列纵队(每行三人)，再列成五列纵队(每行五人)，最后列成七列纵队(每行七人)。

他只要知道这队士兵大约的人数，就可以根据这三次列队排在最后一行的士兵是几个人，而推算出这队士兵的准确人数。

韩信当时看到的三次列队，最后一行的士兵人数分别是2人、2人、4人，并知道这队士兵约在三四百人之间，你能很快推算出这队士兵的人数吗?如果你掌握了中国剩余定理，你是可以做到的，下面给大家介绍一下中国剩余定理的几种形式。

一.余同加余现在有一堆苹果，分给一群人，每个人分3个，剩两个，每个人分4个，剩两个，如何求苹果总数的表达式呢?我们来分析一下，根据已知条件我们可知苹果数除以3余2，除以4也余2，余数相同都为2，我们如果设苹果总数为X,说明(X-2)既能被3整除又能被4整除，也就是能被3和4的最小公倍数12整除，所以X-2=12N,X=12N+2，所以当余数相同时，表达式为除数的公倍数加上相同的余数，这就是余同加余的含义。

二.和同加和现在还是有一堆苹果，每个人分4个剩1个，每个人分3个剩2个，求苹果总数的表达式，分析一下题干，两种情况余数不同，但是除数与余数的和相同，都为5，除以4余1，是相当于除以4余5，除以3余2，相当于除以3余5，那么现在我们就把和同的形式转化成了余同的形式，根据上段的结论，苹果数的表达式X=12N+5，从而我们得出了第二个结论，当除数与余数的和相同时，就用除数的公倍数加上这个相同的和。

韩信点兵例今有物不知其数，凡三三数之剩二，五五数之剩三，七七数之剩二，问物几何？意思为：一个数除以3余2，，除以5余3，除以7余2，求适合这个条件的最小数。

解答方法一：先分别求出能被5和7整除而被3除余1的数（70），能被3和7整除而被5除余1的数（21），能被3和5整除而被7除余1的数（15），然后用原题中被3、5、7除所得的余数2、3、2分别去乘70、21、15，再把所得的积相加。

70×2＋21×3＋15×2＝233例1一个数除以3余2，，除以5余2，除以7余4，求适合这个条件的最小数。

例2一个数除以5余3，，除以6余4，除以7余1，求适合这个条件的最小数。

解答方法二［6、7］=42 而42÷5余2 并且2×（4）=8 8÷5余3 所以取42×4=168［5、7］=35 而35÷6余5 并且5×（2）=10 10÷6余4 所以取35×2=70［5、6］=30 而30÷7余2 并且2×（4）=8 8÷7余1 所以取30×4=120168+70+120=358 而［5、6、7］=210 358—210=148 所以：适合条件的数为148。

例3 篮子里有鸡蛋若干只，每次取出3只，最后剩1只；每次取出5只，最后剩2只；每次取出7只，最后剩3只；问篮子里至少有多少只鸡蛋？例4 一个自然数被7、8、9除分别余1、2、3，并且三个商数的和使570，求这个自然数。

例5 有一个数，除以3余数是2，除以4余数是1，这个数除以12余数是几？例6 卫兵一队列成5行纵队，末行1人；列成6行纵队，末行5人；列成7行纵队，末行4人；列成11行纵队，末行10人；求兵数。

课后练习：1 一个数除以3余2，，除以5余3，除以7余4，求适合这个条件的最小数。

2 一筐苹果，三三数之余一，四四数之余三，五五数之不足一只，这筐苹果最少有几只?3 召开学生座谈会，每组5人则多1人，每组6人则多2人，每组7人则多3人，问至少有多少个学生？4 某班学生若4人一组多1人，5人一组正好分，6人一组少3人，这个班最少有几人？5 用一辆卡车运货，如果每次运9袋余1袋，如果每次运8袋余3袋，如果每次运7袋余2袋，问这批货物至少有多少袋？6 今有物不知其数，九九数之，八八数之，七七数之……三三数之，二二数之皆余一，问物至少几何？7 篮子里有鸡蛋若干只，每次取出3只，最后剩2只；每次取出5只，最后剩3只；每次取出7只，最后剩1只；问篮子里至少有多少只鸡蛋？8 有铅笔若干支，若按12支一扎多11支，按15支一扎多14支，原有铅笔多少支？9 箩筐里有一批橘子，三个三个一数余一个，五个五个一数余四个，七个七个一数余二个，箩筐里原有多少个橘子？10 一个数除以5余数是2，除以3余数是1，这个数除以15余数是几？11 一排吊灯，3个3个的数剩2个，4个4个的数剩3个，6个6个的数剩5个，这排吊灯至少有几个？12 某数被2、3、4、5、6除都余1，正好被7整除，求符合条件的最小数。

穷举法—韩信点兵1. 问题描述：韩信点兵。

韩信有⼀队兵，他想知道有多少⼈，便让⼠兵排队报数。

按从1⾄ 5报数，最末⼀个⼠兵报的数为1；按从1⾄6报数，最末⼀个⼠兵报的数为5；按从 1⾄ 7报数，最末⼀个⼠兵报的数为 4；按从 1⾄ 11报数，最末⼀个⼠兵报的数为 10。

你知道韩信⾄少有多少兵吗？2、【算法思想】设兵数为x，则按题意x应满⾜下述关系式：x%5 ==1 && x%6==5 &&x %7==4 && x%11==10采⽤穷举法对x从 1开始试验，可得到韩信⾄少有多少兵。

3、代码实战：穷举法，设置标志find#include<stdio.h>#include "stdlib.h"int main( ){int x =1;int find = 0; /*设置找到标志为假*/while (!find){if (x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10){find = 1;}x++;printf(" x = %d\n", x);}system("pause"); /*解决快闪问题*/}运⾏结果：（运⾏结果是从1—找到的最⼩数）4、其他代码：goto1 #include<stdio.h>2 #include "stdlib.h"3int main( )4 {5int x ;6for(x=1; ;x++)7 {8if(x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10 ) 9 { printf("最⼩值是x= %d\n ",x);10goto end;11 }12 }13 end:;14 system("pause");15 }break语句执⾏代码1 #include<stdio.h>2 #include "stdlib.h"3int main( )4 {5int x ;6for(x=1; ;x++)7 {8if(x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10 ) 9 { printf("最⼩值是x= %d\n ",x);10break;11 }12 }1314 system("pause");15 }结果相同，不再赘述。

韩信点兵问题的初等解法
“韩信点兵”的由来
据说有一次韩信出兵千余人打仗，让军士清点人数，军士回报说：士兵们站3人一排，多出2人；站5人一排，多出4人；站7人一排，多出6人。

韩信稍加思索就得到了准确的士兵数量：1049人。

这个小故事就成为了“韩信点兵”问题的由来了。

事实上，早在《孙子算经》当中就曾经出现过类似的问题：
今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？
用“韩信点兵”的表达方式就是：每3个士兵站一排，那么就多出来2个人；每5个士兵站一排，就多出来3个人；每7个士兵站一排，就多出来2个人。

那么士兵总共有多少人？
大家可以发现这两道题的相似之处了吧，这就是“韩信点兵”问题通常的题目结构，在数学上属于初等数论当中的“解同余式”问题。

“韩信点兵”的解题思路
通常我们接触到的这类题目都会出现3个左右的同余式。

我们简单的解题技巧就是两两处理已知条件。

实际上对于这个问题是可以利用口诀进行解题的，即：
三人同行七十稀，五树梅花二十一。

七子团圆正半月，除百零五便得知。

这个口诀其实是针对《孙子算经》中那道题目的一个通用解题规则的，四句话意思是：
三人同行七十稀：将除以3的余数乘以70
五树梅花二十一：将除以5的余数乘以21
七子团圆正半月：将除以7的余数乘以15（正半月即15）
除百零五便得知：将以上三个数字相加，求得这个和除以105的余数。

这样就很容易知道《孙子算经》当中所要求的数为23了。

二韩信点兵例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人，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。