如何在 Golang 中使用递归查找两个给定数字的最大公约数 (GCD)？

在本教程中，我们将了解如何使用 Golang 语言和递归来查找两个数字的最大公约数。我们将看到两种使用递归查找两个数字 GCD 的方法。第一种方法需要更多时间，我们通过将两个数字中的较小者减 1，然后检查这两个数字是否都可被该最小数整除。第二种方法需要更少的时间，我们通过将较大的数字减去较小的数字，直到两个数字相等。

算法

  • 步骤 1 - 声明变量来存储两个数字和答案。

  • 步骤 2 - 初始化变量。

  • 步骤 3 - 调用函数以使用将减少每次函数调用的最小数字查找 GCD，对两个数字进行取模运算，并在模为零时返回。

  • 步骤 4 - 打印结果。

方法 1：使用递归函数的非高效方法。

在此示例中，我们通过将两个数字中的较小者减 1，然后检查这两个数字是否都可被该最小数整除。

示例

Open Compiler
package main

// fmt package provides the function to print anything
import (
   "fmt"
)

// this function finds the GCD of two numbers with three parameters
// of int type and have a return type of int type
func gcdOfTwoNumbers(number1, number2, minNumber int) int {

   // checking if the number minNumber can be divided by both number1, and number2
   if minNumber == 1 || (number1%minNumber == 0 && number2%minNumber == 0) {
      return minNumber
   }
   
   // returning the GCD
   return gcdOfTwoNumbers(number1, number2, minNumber-1)
}
func main() {

   // declaring the variable to store the value of two numbers
   // and a variable to store an answer
   var number1, number2, answer, minNumber int
   
   // initializing both the variables
   number1 = 20
   number2 = 15
   fmt.Println("Program to find the GCD of two numbers using the recursion function.")
   if number1 < number2 {
      minNumber = number1
   } else {
      minNumber = number2
   }
   
   // calling a function to find the GCD of two number
   // and passing a minimum of number1 and number2
   answer = gcdOfTwoNumbers(number1, number2, minNumber)
   
   // printing the result
   fmt.Println("The GCD of", number1, "and", number2, "is", answer)
}

输出

Program to find the GCD of two numbers using the recursion function.
The GCD of 20 and 15 is 5

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

方法 2：使用递归函数的高效方法

在此示例中，我们将通过将较大的数字减去较小的数字，直到两个数字相等，从而节省时间。

示例

Open Compiler
package main

// fmt package provides the function to print anything
import (
   "fmt"
)

// this function finds the GCD of two numbers with two parameters
// of int type and have a return type of int type
func gcdOfTwoNumbers(number1, number2 int) int {

   // returning if both the numbers become equal
   if number1 == number2 {
      return number1
   }
   
   // reducing the lesser one with the greater one
   if number1 > number2 {
      number1 -= number2
   } else {
      number2 -= number1
   }
   
   // calling the function
   return gcdOfTwoNumbers(number1, number2)
}
func main() {

   // declaring the variable to store the value of two numbers
   // and a variable to store an answer
   var number1, number2, answer int
   
   // initializing both the variables
   number1 = 20
   number2 = 15
   fmt.Println("Program to find the GCD of two numbers in efficient way using the recursion function.")
   
   // calling a function to find the GCD of two number
   answer = gcdOfTwoNumbers(number1, number2)
   
   // printing the result
   fmt.Println("The GCD of", number1, "and", number2, "is", answer)
}

输出

Program to find the GCD of two numbers in an efficient way using the recursion function.
The GCD of 20 and 15 is 5

结论

这些是使用递归查找两个数字 GCD 的不同方法。第二种方法比第一种方法更有效。要了解更多关于 go 的信息，您可以浏览这些教程。

更新于: 2023年1月11日

264 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告