一道题目
有1元面值、5元面值、10元面值的钞票，请问有多少种找零n元的方案？比如找10元钱一共有 4 种方法：
10张1元
1张5元，5张1元
2张5元
1张10元
输入格式
第一行，一个整数n。
输出格式
一行，一个数字。表示找零的方案数。
样例输入
10
样例输出
4
数据范围
对于100%的数据，保证1≤n≤100。
请人帮我解一下,谢谢.附上思路
#include<stdio.h>
// x + 5y + 10z = n
// 5(y + 2z) + x = n
// 设 k = n % 5, l = (n - k) / 5, 即 5l + k = n
// 则 5(y + 2z) + x = 5l + k
// 5(y + 2z - l) + x = k, x = k + 5(l - y - 2z)
// 设 l - y + 2z = m, x = k + 5m, 其中 0 < m <= l
// 则可以从 0 ~ l 枚举 m, 枚举 x 的值。
// 又 l - y - 2z = m, y + 2z = l - m
// 若 l - m 为偶数，则有 ((l - m) / 2 + 1) 种解
// 若 l - m 为奇数，则有 (l - m + 1) / 2 种解
int main()
{
int sum_ = 0; // 总解法
int n;
scanf("%d", &n);
int k = n%5, l = n / 5;
for(int m = 0; m <= l; ++m) {
if((l-m) % 2 == 0) sum_ += ((l - m) / 2 + 1);
else sum_ += (l - m + 1) / 2;
}
printf("%d", sum_);
return 0;
}
页:
[1]