C++编写程序解决“百钱问题 |21xrx.com

C++编写程序解决“百钱问题

2023-07-09 00:59:12 深夜i -- --

- C++ - 百钱问题 - 编程 - 算法 - 解决方案

百钱问题是一道经典的数学问题，也是一道被广泛应用的编程问题。该问题的基本思路是：如何使用 100 元人民币凑出若干元钱的最小硬币数量，并输出所有可能的情况。这个问题看似简单，但涉及到了贪心算法、动态规划以及组合数学等多个数学和计算机科学领域的知识。下面介绍使用 C++ 编写程序解决该问题的思路。

1. 确定问题模型

首先需要确定问题的模型。由于该问题要求求出硬币的数量，因此采用动态规划方法是较为合适的。假设使用 dp(x) 函数表示凑出 x 元钱所需要的最小硬币数，那么 dp(x) 可以表示为：

dp(x) = min{dp(x-c(i))+1}

其中，i 表示硬币的面值，c(i) 表示第 i 种硬币的面值。转移方程的意思是，在凑出 x 元钱的过程中，使用 c(i) 硬币得到的最小硬币数为 dp(x-c(i)) + 1。同时，为了输出所有的凑钱方案，可以使用二维数组记录每个 dp(x) 的来源。

2. 编写程序

采用 C++ 编写程序，程序中定义了两个函数，分别用于计算最小硬币数和输出所有方案。代码如下：


#include<iostream>
using namespace std;
#define MAX 200
int dp[MAX]; // 记录凑出每一元钱所需的最小硬币数量
int pre[MAX][MAX]; // 记录每个 dp 值的来源
int minCoins(int coins[], int n, int sum)
{
  // 初始化 dp 数组，将凑钱数为 1~sum 的最小硬币数均赋值为 MAX
  for(int i = 1; i <= sum; i++)
  {
   dp[i] = MAX;
  }
  dp[0] = 0; // 凑 0 元钱不需要硬币
  for(int i = 1; i <= sum; i++)
  {
   for(int j = 0; j < n; j++)
   {
     if(coins[j] <= i && dp[i-coins[j]]+1 < dp[i])
     {
      dp[i] = dp[i-coins[j]] + 1;
      // 记录 dp 值的来源
      for(int k = 0; k < n; k++)
      {
        pre[i][k] = pre[i-coins[j]][k];
      }
      pre[i][j]++;
     }
   }
  }
  return dp[sum];
}
void printCombination(int coins[], int n, int sum)
{
  // 递归输出方案
  if(sum == 0)
  {
   for(int i = 0; i < n; i++)
   {
     if(pre[0][i] != 0)
     {
      cout<<coins[i]<<"*"pre[0][i]<<"+";
     }
   }
   cout<<endl;
   return;
  }
  for(int i = 0; i < n; i++)
  {
   if(sum >= coins[i] && pre[sum][i] > 0)
   {
     pre[sum][i]--;
     printCombination(coins, n, sum-coins[i]);
     pre[sum][i]++;
   }
  }
}
int main()
{
  int coins[] = {1, 5, 10, 25, 50};
  int n = 5, sum = 100; // n 表示硬币种数，sum 表示要凑的钱数
  int min_num = minCoins(coins, n, sum);
  cout<<"最小使用硬币数："<min_num<<endl;
  cout<<"所有方案为："<<endl;
  printCombination(coins, n, sum);
  return 0;
}

3. 运行程序

编写完程序后，可以进行测试。运行程序，输入硬币的种数和要凑的钱数，程序会输出最小的硬币数量和所有的凑钱方案。

总结

通过上述的学习，我们可以了解到，C++ 编写程序解决百钱问题是非常有挑战性和有趣的。通过动态规划的思想，可以较为简单地解决该问题，并且输出所有方案，有助于我们更好地理解计算机科学和组合数学中的知识。同时，我们也应该不断学习和探索，提高我们的编程能力和解决实际问题的能力。

上一篇: idea打包java可执行jar包

下一篇: C++中如何处理赋值数过大的问题

评论区

()

相似文章