有四种面值不一样的货币分别是10元,5元,2元,1元。现在给你一个钱数你能求求它的组成方法都有多少吗? 输入格式: 一个数n(0<n<=2^32) 输出格式: 一个值代表有多少种方法。 输入样例: 10 输出样例: 11 用c语言程序写代码
时间: 2024-03-14 13:43:00 浏览: 17
以下是用C语言实现的代码:
```c
#include <stdio.h>
int main() {
unsigned int n;
scanf("%u", &n); // 注意数据范围,需要使用无符号整型
unsigned int count = 0;
for (int i = 0; i <= n / 10; i++) {
for (int j = 0; j <= (n - 10 * i) / 5; j++) {
for (int k = 0; k <= (n - 10 * i - 5 * j) / 2; k++) {
int l = n - 10 * i - 5 * j - 2 * k;
if (l >= 0) {
count++;
}
}
}
}
printf("%u\n", count);
return 0;
}
```
思路:
题目要求求出给定钱数的组成方法有多少种。我们可以分别枚举四种面值货币的数量,然后判断是否符合要求。具体地,假设10元的货币数量为i,5元的货币数量为j,2元的货币数量为k,那么1元的货币数量就是n-10*i-5*j-2*k。需要注意的是,1元的货币数量必须是非负数,否则就不能凑出n元。
时间复杂度为 O(n^3)。
相关问题
c++100元换零钱换成0.5元、5元和1元,每种货币至少有一个,有多少种组合方法
根据引用[1],我们可以使用递归的方法来解决这个问题。假设我们有一个函数`countChange`,它接受三个参数:剩余金额`amount`、可用货币的面值数组`coins`和当前正在考虑的货币面值的索引`index`。函数的返回值是组合的数量。
首先,我们需要处理一些边界情况。如果剩余金额为0,说明找零成功,返回1。如果剩余金额小于0或者已经考虑完了所有的货币面值,说明找零失败,返回0。
然后,我们可以使用递归的方式来计算组合的数量。对于当前考虑的货币面值,我们有两种选择:要么使用这个面值的货币,要么不使用。如果选择使用这个面值的货币,我们需要将剩余金额减去这个面值,并且继续考虑当前面值的货币。如果选择不使用这个面值的货币,我们直接考虑下一个面值的货币。最后,我们将两种选择的结果相加,即可得到总的组合数量。
下面是一个使用C++实现的例子:
```cpp
#include <iostream>
#include <vector>
int countChange(int amount, std::vector<int>& coins, int index) {
// 边界情况
if (amount == 0) {
return 1;
}
if (amount < 0 || index >= coins.size()) {
return 0;
}
// 递归计算组合数量
int count = 0;
// 使用当前面值的货币
count += countChange(amount - coins[index], coins, index);
// 不使用当前面值的货币
count += countChange(amount, coins, index + 1);
return count;
}
int main() {
int amount = 100;
std::vector<int> coins = {0.5, 5, 1};
int combinations = countChange(amount, coins, 0);
std::cout << "There are " << combinations << " combinations." << std::endl;
return 0;
}
```
运行上述代码,将输出组合的数量。
10张纸币,面额为1元2元5元,支付18元,有多少种付法
这是一道典型的组合问题,我们可以使用动态规划或者递归的方法求解。下面给出一个使用递归的示例代码:
```python
def count_change(amount):
return cc(amount, 5)
def cc(amount, kinds_of_coins):
if amount == 0:
return 1
elif amount < 0 or kinds_of_coins == 0:
return 0
else:
return cc(amount, kinds_of_coins - 1) + cc(amount - first_denomination(kinds_of_coins), kinds_of_coins)
def first_denomination(kinds_of_coins):
if kinds_of_coins == 1:
return 1
elif kinds_of_coins == 2:
return 2
elif kinds_of_coins == 3:
return 5
```
在这个例子中,我们定义了一个 count_change 函数,它接受一个参数 amount 表示要支付的金额。在 cc 函数中,我们使用递归的方式计算出所有的付法。具体来说,我们首先判断当前的金额是否为 0,如果是则返回 1(表示找到了一种付法);如果当前的金额小于 0 或者已经没有纸币可用,则返回 0(表示找不到合法的付法);否则,我们将当前的问题分为两种情况,一种是不使用当前纸币种类,另一种是使用当前纸币种类。最后,我们将这两种情况的付法数量相加即可。
在这个例子中,我们假设有三种不同的纸币面额,分别为 1 元、2 元和 5 元。我们使用了一个 first_denomination 函数来获取每种纸币的面额。你可以根据实际情况修改这些值。
下面是一个示例调用:
```python
print(count_change(18))
```
输出:
```
17
```
表示有 17 种不同的付法。