韩信点兵算法答案

| 励志口号 |

【www.guakaob.com--励志口号】

韩信点兵算法答案(一)
韩信点兵算法及C程序

韩信点兵

时间限制:3000 ms | 内存限制:65535 KB

难度: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

韩信点兵算法答案(二)
韩信点兵算法流程图

韩信点兵算法流程图

韩信点兵是一个有趣的猜数游戏。如果你随便拿一把蚕豆(数目约在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年代被解决了,这是近代数学的五个重大成就。据证明人说,在解决问题的过程中,他是受到了“中国剩余定理”的启发的。

韩信点兵算法答案(三)
韩信点兵 解法

韩信点兵解法

韩信点兵是一个有趣的猜数游戏。如果你随便拿一把蚕豆(数目约在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年代被解决了,这是近代数学的【韩信点兵算法答案】

五个重大成就。据证明人说,在解决问题的过程中,他是受到了“中国剩余定理”的启发的。

韩信点兵算法答案(四)
韩信点兵问题的神算法

韩信点兵问题的神解法

定理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的值尝试的次数也会相应增大,从而对于大数相除时也会计算量太大,无法手算,用计算机计算也会比较耗时。以下介绍一种即使对大数计算也非常有效的方法,无论多大的数,计算量都增加很少。

首先证明两个定理:

定理3:

在定理1中,z=b(an+x-y)/(b-a)+y,必存在一个m,使得z= b(am+(x-y)mod(a))/(b-a)+y。

证明:设x-y=ak+(x-y)mod(a)则:z=b(a(m+k)+(x-y)mod(a))/(b-a)+y,故m=n-k即可。

定理4:

在算式(an+x)/b中,必存在一个m,使得(am+x)/((b)mod(a))= (an+x)/b。

证明:设k=(an+x)/b,b=al+(b)mod(a)则:an+x=bk=alk+k((b)mod(a))

所以k=(a(n-lk)+x)/((b)mod(a))= (an+x)/b,只要n=n-lk即可。

定理5:

算式(an+x)/b,当a<b时,必存在一个m使得(an+x)/b=(am+xmod(a))/(bmod(a))。 证明:根据定理3

(an+x)/b=(al+xmod(a))/b

根据定理4

(al+xmod(a))/b=(am+xmod(a))/(bmod(a))【韩信点兵算法答案】

所以(an+x)/b=(am+xmod(a))/(bmod(a))

设m=(an+x)/b,则可以假设z=an+x=bm,则问题转化为:z除以a余x,除以b余0,求z的值。而根据定理5,则可以将算式中的b的值不断递归取余,直至其值为1,而此时n的值则为0。

由此实现的算法,最终不需要计算n的值,只需要分母的值递归至1即可,此时满足条件的n的最小值必定是0。

以下举例说明算法:

例3:一个数z除以347余159,除以362余181,求其值。

z=362*(347n+159-181)/(362-347)+181

=362*(347n+(-22)mod(347))/15+181

=362*(347n+325)/15+181

以下求347n+325的最小值z1,满足:除以347余325,除以15余0,所以其值为: 347*(15n-325)/(347-15)+325

=347*(15n+(-325)mod(15))/332mod(15)+325

=347*(15n+5)/2+325

以下求15n+5的最小值z2,满足:除以15余5,除以2余0,所以其值为:

15*(2n-5)/(15-2)+5

=15*(2n+(-5)mod(2))/13mod(2)+5

=15*(2n+1)/1+5

【韩信点兵算法答案】

分母为1,令n=0,则z2=20,所以z1=347*(z2)/2+325=347*20/2+325=3795

所以z=362*z1/15+181=362*3795/15+181=91767

经过2次递归计算出结果。共进行3次乘法,三次除法,三次加法,6次减法,6次求余。

例4:一个数z除以385余251,除以793余563,求其值。

z=793*(385n+251-563)/(793-385)+563

=793*(385n+(251-563)mod(385))/408mod(385)+563

=793*(385n+73)/23+563

以下求385n+73的最小值z1,满足:除以385余73,除以23余0,所以其值为: 385*(23n-73)/(385-23)+73

=385*(23n+(-73)mod(23))/362mod(23)+73

=385*(23n+19)/17+73

以下求23n+19的最小值z2,满足:除以23余19,除以17余0,所以其值为: 23*(17n-19)/(23-17)+19

=23*(17n+(-19)mod(17))/6+19

=23*(17n+15)/6+19

以下求17n+15的最小值z3,满足:除以17余15,除以6余0,所以其值为:

17*(6n-15)/(17-6)+15

=17*(6n+(-15)mod(6))/11mod(6)+15

=17*(6n+3)/5+15

以下求6n+3的最小值z4,满足:除以6余3,除以5余0,所以其值为:

6*(5n-3)/(6-5)+3

=6*(5n+(-3)mod(5))/1mod(5)+3

=6*(5n+2)/1+3

分母为1,所以令n=0,则z4=6*2+3=15,

所以z3=17*z4/5+15=17*15/5+15=66,

所以z2=23*66/6+19=272

【韩信点兵算法答案】

所以z1=385*z2/17+73=385*272/17+73=6233

所以z=793*z1/23+563=793*6233/23+563=215466

共经过四次递归计算出结果。共进行5次乘法,5次除法,5次加法,10次减法,10次求余。 由此可知,计算量由递归次数决定。设递归次数为n,则乘法、除法和加法的次数为n+1,减法和求余的次数为2(n+1)。

从以上两例可以看出,与传统计算方法相比,大大简化。其递归模式可以非常容易用程序实现,而且当除数比较大时,只要最终结果值不大于数据类型的最大值,用程序计算就不会发生溢出。以下给出javascript代码,将以下代码拷贝到一个空白文档,并以.html为后缀名保存文件后,用浏览器打开该文件即可运行(其中:a1为第一个除数,a2为第一个余数,b1为第二个除数,b2为第二个余数):

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"

"

<html xmlns="

<head>

<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />

<title>韩信点兵神器,无论多大的数都能算</title>

</head>

<script type="text/javascript" language="javascript">

var count=0;

function doCalculate(){

var a1=parseInt(document.getElementById("devider1").value); var a2=parseInt(document.getElementById("rest1").value);

} var b2=parseInt(document.getElementById("rest2").value); var result=calculate(a1,a2,b1,b2); if(result>0){ } else window.alert("两个除数不是互质"); return; document.getElementById("result").value=result; alert("共进行了"+count + "次乘法、除法和加法,"+count*2 + "次减法和求余"); count=0;

function calculate(a1,a2,b1,b2){

}

function getMod(x,n){【韩信点兵算法答案】

}

function isRelativelyPrime(m,n){

var d1,d2,d3=1; if(m<=n){ //将小数放到d1中 d1=m; d2=n; while(x<0){ } return x%n; x+=n; if(isRelativelyPrime(a1,b1)==false) return 0; count += 1; var temp=a1; if(a1>b1){ } var newA1=a1; var newA2=getMod(a2-b2,a1); //保证余数大于0 var newB2=0; var newB1=(b1-a1)%a1; if(newB1==1) return b1*newA2+b2; return b1*(calculate(newA1,newA2,newB1,newB2)/newB1)+b2; a1=b1; b1=temp; temp=a2; a2=b2; b2=temp;

}

else{ } while(d3!=0){ } if(d2==1) return true; return false; d3=d2%d1; d2=d1; d1=d3; d1=n; d2=m;

</script>

<body>

<form METHOD=POST ACTION="" name="frm1" id="frm1">

除以

<input type="text" name="devider1" id="devider1" value="5" /> 余

<input type="text" name="rest1" id="rest1" value="3" />

<br />

除以

<input type="text" name="devider2" id="devider2" value="7" /> 余

<input type="text" name="rest2" id="rest2" value="4" /> <br />

结果:

<input type="text" name="result" id="result" />

<input value="计算" type="button" onClick="doCalculate()" /> </form>

</body>

</html>

本文来源:http://www.guakaob.com/lizhiwendang/522369.html