Go 语言程序：查找凑成指定金额所需的最小硬币数量

在这篇 Go 语言文章中，我们将探讨如何找到在给定一系列不同面值的硬币的情况下，凑成指定金额所需的最小硬币数量。我们可以使用贪心算法来解决这个问题。

算法

  • 步骤 1 − 首先，我们需要导入 fmt 包。

  • 步骤 2 − 然后创建一个名为 minCoins() 的函数，用于计算最小硬币数量。该函数接受两个参数：一个包含硬币数量的整数数组，以及需要凑成的金额。

  • 步骤 3 − 在函数内部，将所需的硬币数量初始化为 0。

  • 步骤 4 − 逆序遍历硬币数组。当剩余金额大于或等于当前硬币时，从剩余金额中减去硬币值，并将所需的硬币数量加 1。

  • 步骤 5 − 返回所需的硬币数量。

  • 步骤 6 − 现在，开始 main() 函数。在 main() 函数内部，初始化包含硬币的数组，并将需要凑成的金额存储在一个变量中。

  • 步骤 7 − 调用上面创建的函数，并将硬币数组和金额作为参数传递给它。将结果存储在另一个变量中，并在屏幕上打印出来。

示例

在本示例中，我们将编写一个 Go 语言程序，使用外部用户自定义函数来查找凑成指定金额所需的最小硬币数量。

Open Compiler
package main

import "fmt"

// function to calculate number of coins
func minCoins(coins []int, amount int) int {
   numCoins := 0
   for i := len(coins) - 1; i >= 0; i-- {
      for amount >= coins[i] {
         amount -= coins[i]
         numCoins++
      }
   }
   return numCoins
}

func main() {
   coins := []int{1, 5, 10, 25}
   amount := 57
   result := minCoins(coins, amount)
   fmt.Printf("Minimum number of coins needed: %d\n", result)
}

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

输出

Minimum number of coins needed: 5

结论

我们已经成功编译并执行了一个 Go 语言程序，用于查找凑成指定金额所需的最小硬币数量。我们在这里使用了贪心算法来实现结果。该算法基于始终为剩余金额选择尽可能大的硬币面值，这对于大多数货币中使用的标准硬币面值非常有效。但是，需要注意的是，贪心算法并不总是最优的，在某些情况下（例如硬币面值不标准或遵循特定模式），它可能无法提供所需的最小硬币数量。

更新于： 2023年4月5日

235 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告