已知可兑换的纸币面额包括100,50,20,10,5,1,编写程序,输入金额(小于等于1000的整数),输出等价兑换后所用纸币的最少数量。
时间: 2024-05-12 09:19:53 浏览: 11
思路:
- 首先将所有可兑换的纸币面额按照从大到小的顺序排列。
- 对于每一种纸币面额,计算出需要用几张纸币才能凑够目标金额。
- 将所有纸币张数加起来,得到最少的纸币张数。
代码实现:
```python
money = int(input("请输入金额(小于等于1000的整数):"))
denominations = [100, 50, 20, 10, 5, 1] # 可兑换的纸币面额
count = 0 # 纸币张数计数器
for d in denominations:
num = money // d # 计算需要用几张纸币
count += num # 累加纸币张数
money -= num * d # 减去已经用掉的金额
print("最少需要用 %d 张纸币" % count)
```
示例输出:
```
请输入金额(小于等于1000的整数):326
最少需要用 6 张纸币
```
相关问题
X星最新版纸币的面额很奇怪,一共有1元、4元、9元、16元、25元、100元六种不同的面额。 已知每种面额纸币的数量不限,现在需要从中选取若干张纸币组成N元(N为正整数)。 请编写一个程序计算组成N元最少需要的纸币数量。c++完整代码
以下是C++的完整代码,采用动态规划的方法解决此问题:
```c++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> dp(n+1, INT_MAX); // 初始化为正无穷
dp[0] = 0; // 组成0元需要0张纸币
vector<int> coins = {1, 4, 9, 16, 25, 100}; // 纸币面额
for(int i=1; i<=n; i++) {
for(int j=0; j<coins.size(); j++) {
if(i >= coins[j]) {
dp[i] = min(dp[i], dp[i-coins[j]] + 1);
}
}
}
cout << dp[n] << endl; // 输出组成n元最少需要的纸币数量
return 0;
}
```
首先读入需要组成的金额n,然后初始化一个大小为n+1的数组dp,表示组成i元所需的最少纸币数量。将dp数组中除了dp[0]以外的所有元素初始化为正无穷,因为组成一个金额的最多纸币数量不会超过该金额本身。
接着定义一个vector coins,存储所有纸币的面额。
接下来使用双重循环,外层循环i从1到n,内层循环j遍历所有纸币面额。如果当前纸币面额不大于i,则可以将dp[i]更新为dp[i-coins[j]]+1,表示组成i元所需的最少纸币数量为组成i-coins[j]元所需的最少纸币数量加上1张面额为coins[j]的纸币。
最后输出dp[n]即可得到组成n元最少需要的纸币数量。
运行示例:
输入:
```
36
```
输出:
```
2
```
解释:
最少需要两张纸币,分别为16元和20元。
x星最新版纸币的面额很奇怪,一共有1元、4元、9元、16元、25元、100元六种不同的面额。 已知每种面额纸币的数量不限,现在需要从中选取若干张纸币组成n元(n为正整数)。 请编写一个程序计算组成n元最少需要的纸币数量。c语言
实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n, i, j, min, coins[6] = {1, 4, 9, 16, 25, 100}, dp[1001];
scanf("%d", &n);
for(i = 1; i <= n; i++)
{
min = 0x3f3f3f3f; // 初始化为无穷大
for(j = 0; j < 6; j++)
{
if(i >= coins[j])
min = dp[i - coins[j]] + 1 < min ? dp[i - coins[j]] + 1 : min;
}
dp[i] = min;
}
printf("%d\n", dp[n]);
return 0;
}
```
这个程序的思路是使用 DP(动态规划)算法,使用 dp[i] 来表示组成 i 元最少需要的纸币数量。每次遍历到 i,就遍历每种面额的纸币,如果当前面额小于等于 i,就看用当前面额能得到更优解没有。具体实现可以看代码。