韩信点兵 解法

数学典故：韩信点兵
下面是店铺为大家整理的数学典故，希望大家能够从中有所收获!
我国汉代有位大将，名叫韩信。

他每次集合部队，只要求部下先后按l～3、1～5、1～7报数，然后再报告一下各队每次报数的余数，他就知道到了多少人。

他的这种巧妙算法，人们称为鬼谷算，也叫隔墙算，或称为韩信点兵，外国人还称它为“中国剩余定理”。

到了明代，数学家程大位用诗歌概括了这一算法，他写道：
三人同行七十稀，五树梅花廿一枝，
七子团圆月正半，除百零五便得知。

这首诗的意思是：用3除所得的余数乘上70，加上用5除所得余数乘以21，再加上用7除所得的余数乘上15，结果大于105就减去105的倍数，这样就知道所求的数了。

比如，一篮鸡蛋，三个三个地数余1，五个五个地数余2，七个七个地数余3，篮子里有鸡蛋一定是52个。

算式是：
1×70+2×21+3×15=157
157-105=52(个)
看完以上的这则数学典故，不妨试试用上面的解法来算一下下面的这道题目!
题目：
新华小学订了若干张《中国少年报》，如果三张三张地数，余数为1张;五张五张地数，余数为2张;七张七张地数，余数为2张。

新华小学订了多少张《中国少年报》呢?。

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

据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，先令士兵从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……（三）余同取余这个是最简单的了，意思是，如果余数都相同，直接把余数加到最小公倍数上。

穷举法—韩信点兵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 }结果相同，不再赘述。

【2017年整理】韩信点兵问题的初等解法“韩信点兵”问题的初等解法研究王晓东河北省卢龙县燕河营镇中学 066407韩信，是我国汉代刘邦手下的一员能征善战，智勇双全的大将。

历史上流传着一个关于他运用奇特方法点兵的传说。

有一天，韩信来到操练场，检阅士兵操练。

他问部将，今天有多少士兵操练，部将回答:“大约两千三百人。

”韩信走上点兵台，他先命全体士兵排成7路纵队，问最后一排剩几人，部将说，剩2人;他又命全体士兵排成5路纵队，问最后一排剩几人，部将说，剩3人;最后，他又让全体士兵排成3路纵队，问最后一排剩几人，部将说，剩2人。

韩信告诉部将，今天参加操练的士兵有2333人。

从现代数学的观点来看，解决韩信点兵问题，可以这样思考:设操练士兵的总数为M，则M=3x+2=5y+3=7z+2其中，x，y，z分别表示排成3路纵队，5路纵队，7路纵队的纵队数目。

求出了x，y，z以后，M也求求出来了。

而求x，y，z可以看成求方程组3x+2=5y+33x+2=7z+2的正整数解。

在上面的方程组中，未知数的个数多于方程的个数，则把这种方程(组)叫做不定方程(组)。

不定方程(组)的解是不确定的，一般不定方程总有无穷多个组解，但若加上整数(或正整数)解的特定限制，则不定方程(组)的解有三种可能:有无限组解，有限组解，或无解。

我国古代人民对于不定方程(组)这类问题解法的探讨有着悠久的历史，在中国古代的《孙子算经》中曾作为一个典型问题进行论述。

其中的一个经典例题是:今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物有几何,答曰:二十三。

术曰:三三数之剩二，则置一百四十;五五数之剩三，则置六十三;七七数之剩二，则置三十;并之得二百三十三，以二百一十减之，即得。

凡三三数之剩一，则置七十;五五数之剩一，则置二十一;七七数之剩一，则置十五。

一百(零)六以上，以一百(零)五减之，即得。

在中国民间还广为流传着一个口诀:三人同行七十稀，五树梅花二十一。

【2017年整理】韩信点兵问题的初等解法“韩信点兵”问题的初等解法研究王晓东河北省卢龙县燕河营镇中学 066407韩信，是我国汉代刘邦手下的一员能征善战，智勇双全的大将。

历史上流传着一个关于他运用奇特方法点兵的传说。

有一天，韩信来到操练场，检阅士兵操练。

他问部将，今天有多少士兵操练，部将回答:“大约两千三百人。

”韩信走上点兵台，他先命全体士兵排成7路纵队，问最后一排剩几人，部将说，剩2人;他又命全体士兵排成5路纵队，问最后一排剩几人，部将说，剩3人;最后，他又让全体士兵排成3路纵队，问最后一排剩几人，部将说，剩2人。

韩信告诉部将，今天参加操练的士兵有2333人。

从现代数学的观点来看，解决韩信点兵问题，可以这样思考:设操练士兵的总数为M，则M=3x+2=5y+3=7z+2其中，x，y，z分别表示排成3路纵队，5路纵队，7路纵队的纵队数目。

求出了x，y，z以后，M也求求出来了。

而求x，y，z可以看成求方程组3x+2=5y+33x+2=7z+2的正整数解。

在上面的方程组中，未知数的个数多于方程的个数，则把这种方程(组)叫做不定方程(组)。

不定方程(组)的解是不确定的，一般不定方程总有无穷多个组解，但若加上整数(或正整数)解的特定限制，则不定方程(组)的解有三种可能:有无限组解，有限组解，或无解。

我国古代人民对于不定方程(组)这类问题解法的探讨有着悠久的历史，在中国古代的《孙子算经》中曾作为一个典型问题进行论述。

其中的一个经典例题是:今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物有几何,答曰:二十三。

术曰:三三数之剩二，则置一百四十;五五数之剩三，则置六十三;七七数之剩二，则置三十;并之得二百三十三，以二百一十减之，即得。

凡三三数之剩一，则置七十;五五数之剩一，则置二十一;七七数之剩一，则置十五。

一百(零)六以上，以一百(零)五减之，即得。

在中国民间还广为流传着一个口诀:三人同行七十稀，五树梅花二十一。

韩信点兵算法原理
韩信点兵算法是一种数学问题的解决方法，用于找到一个整数
n的所有因数。

韩信点兵算法具体的原理如下：
1. 用1到n之间的整数依次尝试去除n，若n能够整除该整数，则该整数为n的一个因数。

2. 遍历整数1到n，将能整除n的整数放入一个集合或数组中。

3. 返回这个集合或数组，即可得到n的所有因数。

这种方法的优势在于简单易懂，且时间复杂度较低。

因为它只需要遍历整数1到n一次，每次判断是否能整除n，所以时间
复杂度为O(n)。

需要注意的是，韩信点兵算法找到的是n的所有因数，而不仅仅是质因数。

质因数是因数中的质数，可以通过进一步判断因数是否为质数来得到。

总的来说，韩信点兵算法是一种简单且高效的方法，用于找到一个整数n的所有因数，对于解决数学问题具有一定的帮助。

“韩信点兵”问题的初等解法研究王晓东河北省卢龙县燕河营镇中学066407韩信，是我国汉代刘邦手下的一员能征善战，智勇双全的大将。

历史上流传着一个关于他运用奇特方法点兵的传说。

有一天，韩信来到操练场，检阅士兵操练。

他问部将，今天有多少士兵操练，部将回答：“大约两千三百人。

”韩信走上点兵台，他先命全体士兵排成7路纵队，问最后一排剩几人，部将说，剩2人；他又命全体士兵排成5路纵队，问最后一排剩几人，部将说，剩3人；最后，他又让全体士兵排成3路纵队，问最后一排剩几人，部将说，剩2人。

韩信告诉部将，今天参加操练的士兵有2333人。

从现代数学的观点来看，解决韩信点兵问题，可以这样思考：设操练士兵的总数为M，则M=3x+2=5y+3=7z+2其中，x，y，z分别表示排成3路纵队，5路纵队，7路纵队的纵队数目。

求出了x，y，z以后，M也求求出来了。

而求x，y，z可以看成求方程组3x+2=5y+33x+2=7z+2的正整数解。

在上面的方程组中，未知数的个数多于方程的个数，则把这种方程（组）叫做不定方程（组）。

不定方程（组）的解是不确定的，一般不定方程总有无穷多个组解，但若加上整数（或正整数）解的特定限制，则不定方程（组）的解有三种可能：有无限组解，有限组解，或无解。

我国古代人民对于不定方程（组）这类问题解法的探讨有着悠久的历史，在中国古代的《孙子算经》中曾作为一个典型问题进行论述。

其中的一个经典例题是：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物有几何？答曰：二十三。

术曰：三三数之剩二，则置一百四十；五五数之剩三，则置六十三；七七数之剩二，则置三十；并之得二百三十三，以二百一十减之，即得。

凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五。

一百（零）六以上，以一百（零）五减之，即得。

在中国民间还广为流传着一个口诀：三人同行七十稀，五树梅花二十一。

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

韩信点兵算法及其原理【问题】求最小非负整数N，使他在除以3,5,7以后所得余数分别是a,b,c。

【韩信点兵法的口诀】三人同行七十稀，五树梅花廿一枝，七子团圆整半月，除百零五便得知。

【韩信点兵法口诀的释义】前三句意思较为明确，假如说一个非负整数N，在除以3,5,7以后所得余数分别是a,b,c。

那么70a+21b+15c 一定是符合题意要求的数。

第四句“除”字作“减”字解。

因为符合要求的最小数N必满足0≤N＜105，但是70a+21b+15c 却有可能大于105，甚至大于210，所以还不一定是符合要求的最小数。

那么当他大于或等于105时，还必须减去105，可能还要再减去105，直到比105小为止，才可以得到符合题意要求的最小数。

【说明】这里105是3,5,7的最小公倍数，70a+21b+15c + 105k 也一定满足“除以3,5,7以后所得余数分别是a,b,c”。

【例如】a=b=c=2，70a+21b+15c=212，70a+21b+15c-105=107＞105。

而符合题意要求的最小数是 2，即 212-105-105=2.【再如】a=2,b=4,c=6，70a+21b+15c=314，314-105=209＞105。

而符合题意要求的最小数是 104，即 314-105-105=104.【韩信点兵法口诀的原理】①能被5,7除尽数是35k,其中k=2，即70除3正好余1，70a 除3正好余a。

②能被3,7除尽数是21k,其中k=1，即21除5正好余1，21b 除5正好余b。

③能被3,5除尽数是15k,其中k=1，即15除7正好余1，15c 除7正好余c。

这样——根据①可知 70a+21b+15c 除3正好余a。

根据②可知 70a+21b+15c 除5正好余b。

根据③可知 70a+21b+15c 除7正好余c。

【韩信点兵法口诀的局限性】只适宜于如题所示的一个极为特殊的问题，要推广到同类问题必须另行制作口诀（即公式）。

韩信点兵问题的神解法定理1：一个数除以a余数x，除以b余数y，a、b互质且a<b，求这个数的最小值。

设这个数为z，则z=b(an+x-y)/(b-a)+y (1)或z=a(bn+x-y)/(b-a)+x (2)其中n为使(bn+x-y)/(b-a)为正整数的最小值。

证明：设z=al+x=bm+y 则：al+x-y-am=(b-a)m所以m=(a(l-m)+x-y)/(b-a)将变量l-m用独立变量n代替：m= (an+x-y)/(b-a)将m代入以上等式得到：z=b(an+x-y)/(b-a)+y同理可以证明等式2定理2：在定理1等式中，0<=n<=b-a。

证明：从定理1等式中可知n=l-m，因为a<b，所以l>=m，故n>=0假设n=h(b-a)+k，k<=b-a 代入以上算式z=b(ah(b-a)+ak+x-y)/(b-a)+y=ahb+b(ak+x-y)/(b-a)，由此可知，n可以取值为k。

根据以上两个定理来计算韩信点兵问题，具有两个方面的优点：1、将两个变量合并成了一个变量，从而只需要尝试一个变量即可。

2、这一个变量的范围被两个除数的值界定，需要尝试的最多次数是确定的。

例1：一个数除以9余5，除以13余4，求这个数的最小值列出算式：13*(9n+5-4)/(13-9)+4=13*(9n+1)/4+4显然能让相除结果为整数的n的最小值为3，代入则得：13*(9*3+1)/4+4=95。

例2：一个数除以13余10，除以17余5，求这个数的最小值列出算式：17*(13n+10-5)/(17-13)+5=17*(13n+5)/4+5显然能让相除结果为整数的n的最小值也为3，代入则得：17*(13*3+5)/4+5=192以上算法比传统算法更简便，但依然有缺陷，即如果除数的值比较大时，要获得满足条件的n的值尝试的次数也会相应增大，从而对于大数相除时也会计算量太大，无法手算，用计算机计算也会比较耗时。