[已解决]一道很简单的找钱问题，呜呜呜，蒟蒻不会TOT

zhangjinxuan

前几天去考试，有一道题我挂了

问题是这样的：

我有 n 元钱，我想把它们兑换成面值为 1, 2, 5 的钱，问有多少种方法？1 <= n <= 1e5

输入样例：
输入：5
输出：4

输入：10
输出：10

我直接写了一个斐波那契数列，然后我挂了……原因很简单，有重复的方案……

但是枚举钱数也不对，十的五次啊喂

唉，我真是个……蒟蒻

求思路，谢谢大佬们！

最佳答案

月排行榜 / 总排行榜

tommyyu

2023-1-20 17:30:50

思路就是解不定方程，枚举5元钱的个数，再针对每一种情况进行求解，最后相加

#include <iostream>
using namespace std;
long long one_and_two_count(int n) {
        if(n == 1) return 1;
        if(n == 0) return 1;
        if(n % 2) return one_and_two_count(n-1);
        return n/2+1;
}
int main()
{
        int n;
        cin >> n;
        long long s = 0;
        for(int five = 0; five*5 <= n; ++five) {
                int one_two = n - 5 * five;
                s += one_and_two_count(one_two);
        }
        cout << s;
        return 0;
}

建议如果学有余力可以直接提前学数学，对文化课打比赛都很有帮助（个人建议，未必准确）

跳转到最佳答案楼层

zhangjinxuan

@tommyyu @xiaosi4081 @柿子饼同学 @陈尚涵 我**连这道题都不会，脸都丢光了

tommyyu

思路就是解不定方程，枚举5元钱的个数，再针对每一种情况进行求解，最后相加

#include <iostream>
using namespace std;
long long one_and_two_count(int n) {
        if(n == 1) return 1;
        if(n == 0) return 1;
        if(n % 2) return one_and_two_count(n-1);
        return n/2+1;
}
int main()
{
        int n;
        cin >> n;
        long long s = 0;
        for(int five = 0; five*5 <= n; ++five) {
                int one_two = n - 5 * five;
                s += one_and_two_count(one_two);
        }
        cout << s;
        return 0;
}

建议如果学有余力可以直接提前学数学，对文化课打比赛都很有帮助（个人建议，未必准确）

zhangjinxuan

tommyyu 发表于 2023-1-20 17:30
思路就是解不定方程，枚举5元钱的个数，再针对每一种情况进行求解，最后相加
建议如果学有余力可以直接提 ...

数学真没学好……要是我考试之前补点数学就好了