前言
经过前期的数据结构和算法学习,开始以OD机考题作为练习题,继续加强下熟练程度。
描述
正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值,设计一个算法,求输入A和B的最小公倍数。
数据范围:1≤?,?≤100000 1≤a,b≤100000
输入描述:
输入两个正整数A和B。
输出描述:
输出A和B的最小公倍数。
示例1
输入:
5 7输出:
35
实现原理与步骤
最大公约数 (GCD) 的计算:
- 使用欧几里得算法计算两个数的最大公约数。
- 在
gcd
方法中,使用while
循环不断交换a
和b
,并将b
赋值为a % b
,直到b
为0。最后返回a
作为最大公约数。
最大公倍数 (LCM) 的计算:
- 使用公式 LCM(a,b)=∣a×b∣/GCD(a,b)计算两个数的最大公倍数。
- 在
lcm
方法中,先调用gcd
方法计算两个数的最大公约数,然后用上述公式计算最大公倍数。
实现代码
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int a = in.nextInt();
int b = in.nextInt();
if (a > b) {
int temp = a;
a = b;
b = temp;
}
int res=lcm(a,b);
System.out.println(res);
}
//最大公约数
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
//最小公倍数
public static int lcm(int a,int b){
return a*b/gcd(a,b);
}
}
1.QA:
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » 华为OD机考题(HJ108 求最小公倍数)
发表评论 取消回复