[已解决]一道题目

刘子诺

有1元面值、5元面值、10元面值的钞票，请问有多少种找零n元的方案？

比如找10元钱一共有 4 种方法：

10张1元
1张5元，5张1元
2张5元
1张10元
输入格式
第一行，一个整数n。

输出格式
一行，一个数字。表示找零的方案数。

样例输入
10
样例输出
4
数据范围
对于100%的数据，保证1≤n≤100。

请人帮我解一下,谢谢.附上思路

最佳答案

月排行榜 / 总排行榜

tommyyu

2022-12-19 15:25:32

#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;
}

跳转到最佳答案楼层

tommyyu

#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;
}