有四种面值不一样的货币分别是10元,5元,2元,1元。现在给你一个钱数你能求求它的组成方法都有多少吗? 输入格式: 一个数n(0<n<=2^32) 输出格式: 一个值代表有多少种方法。 输入样例: 10 输出样例: 11 用c语言写代码
时间: 2024-02-28 16:53:51 浏览: 82
好的,这是一个经典的动态规划问题,我们可以使用一个数组dp[i]表示钱数为i时的组成方法数,递推式为dp[i] = dp[i] + dp[i-c[j]],其中c[j]表示第j种货币的面值。具体实现代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAXN 1000000
int dp[MAXN];
int main()
{
int n, i, j;
int c[4] = {1, 2, 5, 10};
memset(dp, 0, sizeof(dp));
dp[0] = 1;
scanf("%d", &n);
for (i = 0; i < 4; i++) {
for (j = c[i]; j <= n; j++) {
dp[j] += dp[j - c[i]];
}
}
printf("%d\n", dp[n]);
return 0;
}
```
注意,这里的数组dp要开到足够大的范围,否则会导致数组越界错误。
相关问题
有四种面值不一样的货币分别是10元,5元,2元,1元。现在给你一个钱数你能求求它的组成方法都有多少吗? 输入格式: 一个数n(0<n<=2^32) 输出格式: 一个值代表有多少种方法。 输入样例: 10 输出样例: 11 用c语言程序写代码
以下是用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语言编写“输入一个整数代表钱,计算它可以用1元,2元,5元组合的种数”
在C语言中,你可以通过动态规划的方法来解决这个问题。这种问题属于背包问题的一个特例,也被称为零钱找零问题。下面是一个简单的示例程序:
```c
#include <stdio.h>
int change(int n) {
int dp[n+1]; // 初始化一个数组,长度等于你要找的零钱的最大值加1
dp[0] = 1; // 如果没有钱,有0种组合
for (int i = 1; i <= n; i++) { // 遍历从1到n的所有金额
dp[i] = 0; // 每次开始时默认没有组合
if (i >= 5) dp[i] += dp[i - 5]; // 如果这个金额大于等于5,可以包含一枚5元硬币
if (i >= 2) dp[i] += dp[i - 2]; // 同理,如果大于等于2,可以包含一枚2元硬币
dp[i] += dp[i - 1]; // 最基本的情况,不包含任何特定面额的硬币,就是直接找零
}
return dp[n];
}
int main() {
int money;
printf("请输入一个整数代表钱:");
scanf("%d", &money);
int num_combinations = change(money);
printf("用1元、2元、5元组合的种数为:%d\n", num_combinations);
return 0;
}
```
在这个程序里,`change`函数通过填充动态规划数组`dp`计算出给定金额的所有组合方式。
阅读全文