Golang 找到组成给定金额所需的最小硬币数

在这篇Golang文章中，我们将找到组成给定金额所需的最小硬币数，如果给定了一组具有不同面额的硬币。我们可以使用贪婪算法解决这个问题。

步骤

• 第1步 - 首先，我们需要导入 fmt 包。

• 第2步 - 然后创建一个名为 minCoins() 的函数，用于计算最小硬币数。该函数接受两个参数，一个是包含硬币数量的整数数组，另一个是要组成的金额。

• 第3步 - 在这个函数内部，将所需的硬币数量初始化为 0。

• 第4步 - 反向迭代硬币数组。当剩余金额大于或等于当前硬币时，从剩余金额中减去硬币的值，并增加所需硬币数。

• 第5步 - 返回所需的硬币数量。

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

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

示例

在此示例中，我们将编写一个Go语言程序，通过使用外部用户定义的函数，找到组成给定金额所需的最小硬币数。

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)
}

输出

Minimum number of coins needed: 5

结论

我们已成功编译并执行了一个Go语言程序，用于找到组成给定金额所需的最小数量的硬币。我们在这里使用了贪心算法来实现这个结果。该算法基于始终选择剩余金额中最大可能面额的硬币，对于大多数货币中使用的标准面额的硬币来说效果很好。然而，需要注意的是贪心算法并不总是最优的，在某些情况下可能无法提供所需的最小数量的硬币，特别是当硬币面额不是标准的或者遵循特定的模式时。