C++入门：找零代码实例 |21xrx.com

C++入门：找零代码实例

2023-07-04 23:32:23 深夜i -- --

C++ 入门找零代码实例

在生活中，我们经常需要进行找零的操作，而在程序设计中，也有类似的需求。使用C++语言编写找零代码，可以帮助我们更好地理解程序设计和算法。下面，我们将通过一个具体的代码实例来展示如何使用C++进行找零操作。

首先，让我们分析一下找零的过程。假设我们需要找零的金额为x元，我们手头有若干个硬币和纸币，它们的面额分别为d1元、d2元、……、dn元。现在，我们需要找出一种方案，使得使用的硬币和纸币总金额最小，且能够凑出x元。这个问题就是一个典型的最小找零问题。

接下来，我们来看一下如何用C++代码实现求解最小找零问题。首先，我们可以定义一个数组dp，用于记录凑齐不同金额所需的最小硬币数（或纸币数）。设dp[i]代表凑齐i元所需的最小硬币数，那么dp的初始化应该为dp[0]=0，因为凑齐0元不需要任何硬币。

然后，我们可以使用动态规划的思想来更新dp数组。假设当前需要凑齐的金额为i元，我们枚举手头可用的硬币和纸币，从中选择面额为dj元的一个硬币或纸币（j=1,2,……n），那么凑齐i元所需的最小硬币数就是：

dp[i]=min(dp[i],dp[i-dj]+1)

其中，dp[i-dj]表示凑齐i-dj元所需的最小硬币数，因为如果我们已经使用了一张面额为dj元的纸币或硬币，那么剩下的金额就是i-dj元。而+1则表示使用了一张面额为dj元的纸币或硬币。

最后，当我们更新完所有的dp[i]时，需要输出的结果就是dp[x]，即凑齐x元所需的最小硬币数或纸币数。

接下来，我们来看一下具体的C++代码实现：


#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000010;
int n,x,a[N],dp[N];
int main(){
  scanf("%d%d",&n,&x);
  for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
  for(int i=1;i<=x;i++){
    dp[i]=N;
    for(int j=1;j<=n;j++){
      if(i==a[j])
        dp[i]=1;
      else if(i>a[j])
        dp[i]=min(dp[i],dp[i-a[j]]+1);
    }
  }
  if(dp[x]>=N)
    printf("-1\n");
  else
    printf("%d\n",dp[x]);
  return 0;
}

这段代码首先输入了硬币和纸币的种类数n和需要凑齐的金额x。然后，我们通过一个数组a来记录不同硬币和纸币的面额，输入a数组的值。接着，我们进行动态规划的操作，更新dp数组，最后输出结果。

这个C++找零代码实例可以帮助我们理解动态规划算法和C++语言的语法和结构。当我们需要解决类似最小找零问题时，可以借助这个代码实例进行参考和实践，也可以根据具体情况进行代码的调整和优化。

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

下一篇: 使用C++生成chm文档的代码

评论区

()

相似文章