韩信点兵程序实例

韩信点兵时间限制：3000ms |内存限制：65535KB难度：1描述相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只掠一眼队伍的排尾就知道总人数了。

输入3个非负整数a,b,c ，表示每种队形排尾的人数（a<3,b<5,c<7），输出总人数的最小值（或报告无解）。

已知总人数不小于10，不超过100 。

输入输入3个非负整数a,b,c ，表示每种队形排尾的人数（a<3,b<5,c<7）。

例如,输入：2 4 5输出输出总人数的最小值（或报告无解，即输出No answer）。

实例，输出：89#include<stdio.h>int main(){int a,b,c,m;scanf("%d%d%d",&a,&b,&c);m=(a*70+b*21+c*15);if(m>105)m=m-105;printf("%d\n",m);return 0;}三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。

这就是韩信点兵的计算方法，它的意思是：凡是用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欢迎您的下载，资料仅供参考！致力为企业和个人提供合同协议，策划案计划书，学习资料等等打造全网一站式需求。

中国剩余定理的应用实例——韩信点兵物不知其数问题出自一千六百年前我国古代数学名著《孙子算经》。

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

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

问：这批物品共有多少件?变成一个纯粹的数学问题就是：有一个数，用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的一个倍数的和。

因为8加上3与5的任何整数倍所得之和除以3仍然余2，除以5仍然余3.于是我们让新数为8+15m，分别把m=1，2，…代进去试验。

当试到m=3时，得到8+15m=53，53除以7恰好余4，因而53合乎题目要求。

【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的正整数解。

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

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

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

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

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

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

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

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

韩信点兵问题的神解法定理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的值尝试的次数也会相应增大，从而对于大数相除时也会计算量太大，无法手算，用计算机计算也会比较耗时。

韩信点兵算法介绍韩信点兵算法，也称为“合璧算法”，是中国古代著名将军韩信所使用的一种军事策略。

该算法的目的是从一组士兵中找出符合特定条件的人数。

韩信点兵算法在计算机领域中有着广泛的应用，尤其在数据处理与分析中起着重要的作用。

算法原理韩信点兵算法的核心思想是利用取模运算将问题转化为求解一次一元一次方程。

算法的具体步骤如下：1.首先，根据题设条件确定要找的士兵的特征，例如身高、年龄、编号等。

2.将每个士兵的特征与条件进行对比，如果符合条件，则给这个士兵编一个号码。

同时，利用取模运算，将该士兵的编码除以总人数，取余数。

3.继续遍历所有的士兵，每个符合条件的士兵也要进行取模运算，并将结果与之前的结果进行累加。

4.最后，对累加结果进行取模运算，得到最终的结果，即为符合条件的士兵数量。

算法示例下面以一个具体的例子来说明韩信点兵算法的应用。

假设有一支由1000名士兵组成的队伍，韩信要从中找出年龄为30岁的士兵，且编号为1的倍数或者身高大于180cm 的士兵。

根据韩信点兵算法，我们可以得到以下的答案：total =1000# 队伍总人数count =0# 计数器，用于记录符合条件的士兵数量for soldier in range(1, total +1):if soldier %30==0or soldier %180>0:count +=1result = count % total在上述代码中，我们使用了一个循环来遍历所有的士兵。

对于每个士兵，我们首先判断其年龄是否为30岁，如果是，则条件一成立。

接着，我们判断其编号是否为1的倍数或者身高是否大于180cm，只要有一个条件满足，就符合条件。

最后，我们将符合条件的士兵数量进行取模运算，并将结果累加到计数器中。

算法优化韩信点兵算法在实际应用中可能会面临数据量巨大的情况，这时可以对算法进行优化，以提高执行效率。

以下是一些常用的优化方法：1.使用并行计算：对于大规模的士兵队伍，可以利用并行计算的思想，将任务分给多个处理器并行执行，以提高算法的效率。

“韩信点兵多多益善”这句话大家都知道那究竟这“多多”的士兵共有多少呢韩信说“如果每3个人编为一队那最后剩下1个人如果每5个人编为一队那最后剩下2个人如果每7个人编为一队最后也剩下2个人。

请你自己算一个我有多少士兵”假设士兵总数不超过100人◇古代解法在我国古代的数学著作中对这个问题也做了非常详细的研究并总结了解题的方法三人同行七十70稀五树梅花廿一21枝七子团圆正半月15 余百零五105便得知意思是说把除以3、5、7所得的余数分别乘以70、21、15加起来的和再减去105的倍数所得的差小于105时就是我们所求的这个数了。

如本题
1×702×212×15142 142-10537 ◇数学解法设士兵共有S名。

S除以357所得的商分别为ABC那么由题意有3A1S 5B2S 7C2S 韩信点兵算法①. S100 ②. 判断如果S除以3余1、S除以5余2、S除以7余2同时成立那么S就是解输出解S的值程序结束否则转③③. S减1转②重复这个判断过程。

程序Dim a1 b1 a2 b2 a3 b3 s s1 As Long a1
3 b1 1 a2 5 b2 2 a3 7 b3 2 s 100 Text1.Text”” While s 0 If s Mod a1 b1 And s Mod a2 b2 And s Mod a3 b3 Then Text1.Text 韩信一共有Strs 名士兵s -1 结束搜索过程Else s s - 1 End If Wend。

SCAU1077韩信点兵1077 韩信点兵时间限制:500MS 内存限制:65536K提交次数:507 通过次数:51题型: 编程题语⾔: ⽆限制Description相传汉⾼祖刘邦问⼤将军韩信统御兵⼠多少，韩信答说，每3⼈⼀列余1⼈、5⼈⼀列余2⼈、7⼈⼀列余4⼈、13⼈⼀列余6⼈、17⼈⼀列余2⼈、19⼈⼀列余10⼈、23⼈⼀列余1⼈、29⼈⼀列余11⼈。

刘邦茫然⽽不知其数。

你呢？你是⼀位优秀的程序员，请你帮刘邦解决这⼀问题。

Input要求由键盘输⼊A,B,C,D,E,F,G,H,a,b,c,d,e,f,g,h⼗六个数，分别代表每A⼈⼀列余a、每B⼈⼀列余b、每C⼈⼀列余c、每D⼈⼀列余D、每E⼈⼀列余e、每F⼈⼀列余f、每G⼈⼀列余g、每H⼈⼀列余h，其中A,B,C,D,E,F,G,H为互不相等的质数Output输出总兵⼠数，要求输出满⾜条件的最⼩的⼀个，但要满⾜8种排法的每⼀种排法⾄少可排⼀列。

（保证给的数据，有结果且计算的结果不会超过2的63次⽅）Sample Input2 3 5 7 11 13 17 191 1 1 1 1 1 1 1Sample Output9699691Provideradmin#include<stdio.h>#include<math.h>int main(){double a[8], b[8], c[8], flag, max;int i, k;double answer = 0, plus = 1, j;for(i = 0; i < 8; i ++){scanf("%lf", &a[i]);plus *=a[i];}for(i = 0; i < 8; i ++)scanf("%lf", &b[i]);max = a[0];for(i = 0; i < 8;i ++){max = max < a[i]? a[i]:max;for(j = 1; ; j ++){flag=j * plus/a[i];if(fmod(flag , a[i]) == b[i]) break; }c[i] = flag;answer += c[i];}j =fmod(answer, plus);if(j < max) j +=plus;printf("%.0lf\n", j);return0;}。

第11课时5.4 算法案例重点难点重点：通过案例分析，体会算法思想，熟练算法设计，进一步理解算法的基本思想，发展有条理的思考和表达能力，提高逻辑思维能力。

难点：在分析案例的过程中设计规范合理的算法学习要求1．理解剩余定理的内涵 2．能利用剩余定理解决“韩信点兵—孙子问题” 【课堂互动】 历史背景： 韩信是秦末汉初的著名军事家，据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么办法，不要逐个报数，就能知道场上士兵的人数。

韩信先令士兵排成3列纵队，结果有2人多余；接着他立刻下令将队形改为5列纵队，这一改，又多出3人；随后他又下令改为7列纵队，这一次又剩下2人无法成整行。

韩信看此情形，立刻报告共有士兵2 333人。

众人都愣了，不知韩信用什么办法清点出准确人数的。

这个故事是否属实，已无从查考，但这个故事却引出一个著名的数学问题，即闻名世界的“孙子问题”。

这种神机妙算，最早出现在我国《算经十书》之一的《孙子算经》中，原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三。

”所以人们将这种问题的通用解法称为“孙子剩余定理”。

【分析】“孙子问题”相当于求关于x ，y ，z 的不定方程组⎪⎩⎪⎨⎧+=+=+=273523z m y m x m 的正整数解。

根据题意，m 应该满足三个条件： （1）m 被3除后余2，即 2)3,(=m Mod （2）m 被5除后余3，即3)5,(=m Mod（3）m 被7除后余2，即2)7,(=m Mod在自然数中可能存在满足条件的数，首先让m=2开始检验条件，若三个条件中有任何一个不满足，则检验下一个数，即m 递增1，如此循环下去，一直到m 满足三个条件为止。

这种解决问题的方法也称为“穷举法”，这种方法在利用计算机解决问题时非常有效，因为计算机最擅长重复机械的操作。

【流程图】【伪代码】【思考】上述算法只能求出最小的满足条件的数，如果要求出10个满足条件的数，程序要做何修改？你能否用数学上最小公倍数的知识分析出解决该问题的方法吗？可以这样考虑：5和7的公倍数中能被3除余2的最小的公倍数是35；3和7的公倍数中能被5除余3的最小的公倍数是63；3和5的公倍数中能被7除余2的最小的公倍数是30；因此满足条件的其中的一个数就应是35+63+30，为128，若减去3,5,7的最小公倍数105得23，23就是满足题目要求的最小的数。