java 用java编写一个程序段,输入两个正整数m和n,求其最大公约数和最小公倍数?
浏览量:2812
时间:2021-04-10 04:41:26
作者:admin
用java编写一个程序段,输入两个正整数m和n,求其最大公约数和最小公倍数?
递归分治法口诀?
1.1递归
自上而下分析,然后回溯:从n->的情况下到1(特殊情况)->,然后反算->,最后得到n的情况
必须满足以下要求:
每次你叫自己,在某种意义上你必须更接近解(每一次运算都是收敛的):问题的规模越来越小
必须有一个终止处理或计算的准则必须有一个退出
1.2分治法
用分治法来解决子问题,子问题的类型往往与原问题相同,所以自然采用递归解法
自然语言描述计算两个非负整数P和Q的最大公约数:如果Q为0,则最大公约数为P。否则,将P除以Q得到余数R。P和Q的最大公约数是Q和R的最大公约数。Java代码公约数
public static int GCD(int P,int Q){如果(Q==0)返回P int R=P%Q返回GCD(Q,R)}]公倍数是两个数除以最大公约数的乘积。公共静态int g(int p,int q){返回p*q/gcd(q,r)}
版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
下一篇
百度手机seo排名 搜索排名