C++ 寻找 GCD 的程序-立地货

查找 GCD 的 C++ 程序

使用循环和决策语句计算两个整数(正整数和负整数)的 GCD 的不同方法示例。

要理解此示例，您应该了解以下C++ 编程主题:

C++ if, if...else 和嵌套 if...else

C++ for Loop

C++ while 和 do...while 循环

可以完美整除两个整数的最大整数称为这两个数的 GCD 或 HCF。

例如，4 和 10 的 GCD 是 2，因为它是可以整除 4 和 10.

示例: 1. 使用 for 循环查找 HCF/GCD

#include <iostream>
using namespace std;
int main() {
  int n1, n2, hcf;
  cout << "Enter two numbers: ";
  cin >> n1 >> n2;
  // swapping variables n1 and n2 if n2 is greater than n1.
  if ( n2 > n1) {   
    int temp = n2;
    n2 = n1;
    n1 = temp;
  }
    
  for (int i = 1; i <=  n2; ++i) {
    if (n1 % i == 0 && n2 % i ==0) {
      hcf = i;
    }
  }
  cout << "HCF = " << hcf;
  return 0;
}

这个程序的逻辑很简单。

在这个程序中， n1 和 n2 之间的较小整数存储在 n2 中。然后循环从 i = 1迭代到 i <= n2，每次迭代， i的值加1、

如果两个数都可以被 i 整除，那么这个数就存储在变量 hcf 中。

这个过程在每次迭代中重复。迭代完成后，HCF 将存储在变量 hcf 中。

示例 2: 使用 while 循环查找 GCD/HCF

#include <iostream>
using namespace std;
int main() {
  int n1, n2;
  cout << "Enter two numbers: ";
  cin >> n1 >> n2;
  
  while(n1 != n2) {
    if(n1 > n2)
      n1-= n2;
    else
      n2-= n1;
  }
  cout << "HCF = " << n1;
  
  return 0;
}

输出

Enter two numbers: 16
76
HCF = 4

在上面的程序中，从较大的数字中减去较小的数字，然后将该数字存储在较大的数字位置。

这里， n1-= n2 与 n1 = n1-n2 相同。类似地， n2-= n1 与 n2 = n2-n1 相同。

这个过程一直持续到两个数字相等，即 HCF。

让我们看看这个程序在 n1 = 16 和 n2 = 76 时是如何工作的。

n1	n2	n1 > n2	n1-= n2	n2-= n1	n1 != n2
16	76	`假`	-	60	`true`
16	60	`假`	-	44	`true`
16	44	`假`	-	28	`true`
16	28	`假`	-	12	`true`
16	12	`true`	4	-	`true`
4	12	`假`	-	8	`true`
4	8	`假`	-	4	`假`

这里，当 n1 != n2 变为 false 时，循环终止。

在循环的最后一次迭代之后， n1 = n2 = 4。这是 GCD/HCF 的值，因为这是可以同时整除 16 和 76 的最大数。

我们还可以使用函数递归找到两个数字的 GCD。