作业帮3个数最大公约数算法请用高中必修3的语言来写,C++,JAVA等不适宜.我就是说只有INPUT PRINT IF WHILE那些来写
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/15 09:49:09
3个数最大公约数算法请用高中必修3的语言来写,C++,JAVA等不适宜.我就是说只有INPUT PRINT IF WHILE那些来写
3个数最大公约数算法
请用高中必修3的语言来写,C++,JAVA等不适宜
.我就是说只有INPUT PRINT IF WHILE那些来写
3个数最大公约数算法请用高中必修3的语言来写,C++,JAVA等不适宜.我就是说只有INPUT PRINT IF WHILE那些来写
对于3个数A,B,C,最小公倍数=A*B*C/最小公约数的平方
对于对小公约数,可以采用两次辗转相除法
先求A,B的最小公约数D
再求出C与D的最小公约数E
那么E就是这三个数的最小公约数
A*B*C/E/E就是三个数的最小公倍数
举例如下
求1734,816和1343的最大公约数：
首先求1734,816的最大公约数：
gcd(1734,816)表示开始求1734,816的最大公约数.
gcd(1734,816)
=gcd(1734,816)1734=2*816+102
（102为1734除以816的余数,而2为商,以后的如此类推）
=gcd(816,102)816=8*102
（至此余数为0,则102为1734和816的最大公约数）
运用3个数的最大公约数的求解原理：
只需求的1343和102的最大公约数即为1734,816和1343的最大公约数.
gcd(1343,102)
=gcd(1343,102)1343=13*102+17
=gcd(102,17)102=6*17
（至此余数为0,则17为即为1734,816和1343的最大公约数）
则17为即为1734,816和1343的最大公约数
更相减损术求解（也是现学现卖的）
原理：
第一步：任意给定两个正整数；判断它们是否都是偶数.若是,则用2约简；若不是则执行第二步.
第二步：以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数.继续这个操作,直到所得的减数和差相等为止,则这个等数就是所求的最大公约数.
其中所说的“等数”,就是最大公约数.求“等数”的办法是“更相减损”法,实际上就是辗转相除法.
首先看1734和816.
两个数都是偶数,为了简化计算,都除以2得到867和408.
下面是计算过程：
867-408=459
459-408=51
408-51=357
357-51=306
306-51=255
255-51=204
204-51=153
153-51=102
102-51=51
至此所得的减数和差相等,由于867和408是1734和816除以2得到的数字.故
1734和816的最大公约数还是102（51*2=102）.
在用更相减损术求102和1343的的最大公约数即为1734,816和1343的最大公约数.
1343-102=1241(由于102*10=1020,1343-1020=323,323还是大于102的）
...
...
...
323-102=221
221-102=119
119-102=17
102-17=85
85-17=68
68-17=51
51-17=34
34-17=17
至此所得的减数和差相等.故17为1734,816和1343的最大公约数