韩信点兵算法,韩信点兵是如何计算的

2023-05-14 136阅读 0评论

韩信点兵算法，韩信点兵是如何计算的？

相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只掠一眼队伍的排尾就知道总人数了。输入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

输出

输出总人数的最小值（或报告无解，即输出Noanswer）。实例，输出：89

样例输入

2 1 6

样例输出

定理1 如a被n除所得的余数等b被n除所得的余数，c被n除所得的余数等于d被n除所得的余数，则ac被n除所得的余数等于b d被n除所得的余数。

用同余式叙述就是：

如a≡b（mod n ），c≡d（mod n ）

则ac≡b d（mod n ）

定理2 被除数a加上或减去除数b的倍数，再除以b，余数r不变。即

如a ≡ r（mod b ），则a ± b n≡r（mod b ）

例如70≡1（mod 3 ）可得70±10×3≡1（mod 3 ）

【韩信点兵法口诀的原理】

①能被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。

（70a+21b+15c）%（3*5*7）为最小值，然后再判断最小值是否满足条件。

复制代码

1 #include <stdio.h>

3 int main(){

4 int a;

5 int b;

6 int c;

7 int result;

9 scanf("%d%d%d",&a,&b,&c);

10 result=(70*a+21*b+15*c)%(3*5*7);

12 if(result>=10 && result<=100)

13 printf("%d\n",result);

15 else

16 printf("No answer\n");

18 return 0;

19 }

韩信点兵法的算法是什么意思？

韩信点兵，多多益善

我国汉代有位大将,名叫韩信.他每次集合部队,只要求部下先后按l～3、1～5、1～7报数,然后再报告一下各队每次报数的余数,他就知道到了多少人.他的这种巧妙算法,人们称为鬼谷算,也叫隔墙算,或称为韩信点兵,外国人还称它为“中国剩余定理”.到了明代,数学家程大位用诗歌概括了这一算法

韩信点兵

韩信点兵又称为中国剩余定理,相传汉高祖刘邦问大将军韩信统御兵士多少,韩信答说,每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人…….刘邦茫然而不知其数.

我们先考虑下列的问题：假设兵不满一万,每5人一列、9人一列、13人一列、17人一列都剩3人,则兵有多少?

首先我们先求5、9、13、17之最小公倍数9945（注：因为5、9、13、17为两两互质的整数,故其最小公倍数为这些数的积）,然後再加3,得9948（人）.

中国有一本数学古书「孙子算经」也有类似的问题：「今有物,不知其数,三三数之,剩二,五五数之,剩三,七七数之,剩二,问物几何?」

答曰：「二十三」

术曰：「三三数之剩二,置一百四十,五五数之剩三,置六十三,七七数之剩二,置三十,并之,得二百三十三,以二百一十减之,即得.凡三三数之剩一,则置七十,五五数之剩一,则置二十一,七七数之剩一,则置十五,即得.」

孙子算经的作者及确实着作年代均不可考,不过根据考证,着作年代不会在晋朝之後,以这个考证来说上面这种问题的解法,中国人发现得比西方早,所以这个问题的推广及其解法,被称为中国剩余定理.中国剩余定理（Chinese Remainder Theorem）在近代抽象代数学中占有一席非常重要的地位.

韩信点兵for语句？

韩信点兵，多多益善

韩信巧点兵解题方法？

韩信点兵的数学解法

我国汉代有一位大将，名叫韩信。他每次集合部队，都要求部下报三次数，第一次按1～3报数，第二次按1～5报数，第三次按1～7报数，每次报数后都要求最后一个人报告他报的数是几，这样韩信就知道一共到了多少人。他的这种巧妙算法，人们称为“鬼谷算”、 “隔墙算”、“秦王暗点兵”等。

这种问题在《孙子算经》中也有记载：“今有物不知其数：三三数之余二，五五数之余三，七七数之余二，问物几何?” 它的意思就是，有一些物品，如果3个3个的数，最后剩2个；如果5个5个的数，最后剩3个；如果7个7个的数，最后剩2个；求这些物品一共有多少？人们通常把这个问题叫作“孙子问题”，西方数学家把它称为“中国剩余定理”。现在，这个问题已成为世界数学史上著名的问题。

到了明代，数学家程大位把这个问题的算法编成了四句歌诀：

三人同行七十稀，五树梅花廿一枝；

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

用现在的话来说就是：一个数用3除，除得的余数乘70；用5除，除得的余数乘21；用7除，除得的余数乘15。最后把这些乘积加起来再减去105的倍数，就知道这个数是多少。

《孙子算经》中这个问题的算法是：

70×2＋21×3＋15×2＝233

233－105－105＝23

所以这些物品最少有23个。

根据上面的算法，韩信点兵时，必须先知道部队的大约人数，否则他也是无法准确算出人数的。你知道这是怎么回事吗？

这是因为，

被5、7整除，而被3除余1的最小正整数是70；

被3、7整除，而被5除余1的最小正整数是21；

被3、5整除，而被7除余1的最小正整数是15。

所以，这三个数的和是15×2＋21×3＋70×2，必然具有被3除余2，被5除余3，被7除余2的性质。

以上解法的道理在于：

被3、5整除，而被7除余1的最小正整数是15；

被3、7整除，而被5除余1的最小正整数是21；

被5、7整除，而被3除余1的最小正整数是70。

因此，被3、5整除，而被7除余2的最小正整数是 15×2＝30；

被3、7整除，而被5除余3的最小正整数是 21×3＝63；

被5、7整除，而被3除余2的最小正整数是 70×2＝140。

于是和数15×2＋21×3＋70×2，必具有被3除余2，被5除余3，被7除余2的性质。但所得结果233（30＋63＋140＝233）不一定是满足上述性质的最小正整数，故从它中减去3、5、7的最小公倍数105的若干倍，直至差小于105为止，即 233－105－105＝23。所以23就是被3除余2，被5除余3，被7除余2的最小正整数。