如何编写一个简单的 Java 程序来找到两个数字之间的最大公约数? [英] How to write a simple Java program that finds the greatest common divisor between two numbers?
问题描述
问题来了:
" 编写一个名为 gcd 的方法,它接受两个整数作为参数并返回这两个数的最大公约数.两个整数 a 和 b 的最大公约数 (GCD) 是两个整数 a 的因数的最大整数b. 任意数与1的GCD为1,任意数与0的GCD为该数.
"Write a method named gcd that accepts two integers as parameters and returns the greatest common divisor of the two numbers. The greatest common divisor (GCD) of two integers a and b is the largest integer that is a factor of both a and b. The GCD of any number and 1 is 1, and the GCD of any number and 0 is that number.
计算两个数的 GCD 的一种有效方法是使用欧几里得算法,该算法说明如下:
One efficient way to compute the GCD of two numbers is to use Euclid's algorithm, which states the following:
GCD(A, B) = GCD(B, A % B)
GCD(A, 0) = Absolute value of A"
我真的很困惑如何解决这个问题.我只是想要一些提示和技巧,以了解我在迄今为止的程序中做错了什么.(我必须放一个扫描仪,这是我老师的要求.)不要给我完整的代码,因为我有点想自己解决这个问题.也许只是给我一个关于我如何合并你在上面看到的这个公式的提示.(如果你想知道我为什么要输入 == 0,那是因为我认为如果你有两个数字,比如 0 和 90,它们的 GCD 应该是 0,对吗??)
I'm really confused as to how to solve this problem. I just want some hints and tips as to what I did wrong in the program I have so far. (I have to put in a Scanner, that is my teacher's requirement.) Don't give me a full code as I kinda want to solve this out myself. Maybe just give me a hint on how I incorporate this formula that you see above. (And if you're wondering why I put in the == 0, it's because I thought that if you have two numbers, say 0 and 90, their GCD would be 0 right??)
此外,我的代码必须包含 while 循环...我更喜欢 if 循环...
Also, my code has to include while loops...I would've preferred if loops...
提前致谢!:)
我目前的程序:
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
int a = console.nextInt();
int b = console.nextInt();
gcd (a, b);
}
public static void gcd(int a, int b) {
System.out.print("Type in two numbers and I will print outs its Greatest Common Divisor: ");
int gcdNum1 = console.nextInt();
int gcdNum2 = console.nextInt();
while (gcdNum1 == 0) {
gcdNum1 = 0;
}
while (gcdNum2 > gcdNum1) {
int gcd = gcdNum1 % gcdNum2;
}
System.out.print(gcdNum1 + gcdNum2);
}
}
推荐答案
递归方法是:
static int gcd(int a, int b)
{
if(a == 0 || b == 0) return a+b; // base case
return gcd(b,a%b);
}
使用while循环:
static int gcd(int a, int b)
{
while(a!=0 && b!=0) // until either one of them is 0
{
int c = b;
b = a%b;
a = c;
}
return a+b; // either one is 0, so return the non-zero value
}
当我返回 a+b
时,我实际上返回的是非零数字,假设其中一个是 0.
When I'm returning a+b
, I'm actually returning the non-zero number assuming one of them is 0.
这篇关于如何编写一个简单的 Java 程序来找到两个数字之间的最大公约数?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!