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

zhangjinxuan

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

问题是这样的：

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

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

输入：10
输出：10

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

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

唉，我真是个……蒟蒻

求思路，谢谢大佬们！

最佳答案

月排行榜 / 总排行榜

tommyyu

2023-1-20 17:30:50

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

1. #include <iostream>
   
2. using namespace std;
   
3. long long one_and_two_count(int n) {
   
4.         if(n == 1) return 1;
   
5.         if(n == 0) return 1;
   
6.         if(n % 2) return one_and_two_count(n-1);
   
7.         return n/2+1;
   
8. }
   
9. int main()
   
10. {
    
11.         int n;
    
12.         cin >> n;
    
13.         long long s = 0;
    
14.         for(int five = 0; five*5 <= n; ++five) {
    
15.                 int one_two = n - 5 * five;
    
16.                 s += one_and_two_count(one_two);
    
17.         }
    
18.         cout << s;
    
19.         return 0;
    
20. }

复制代码

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

跳转到最佳答案楼层

zhangjinxuan

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

tommyyu

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

1. #include <iostream>
   
2. using namespace std;
   
3. long long one_and_two_count(int n) {
   
4.         if(n == 1) return 1;
   
5.         if(n == 0) return 1;
   
6.         if(n % 2) return one_and_two_count(n-1);
   
7.         return n/2+1;
   
8. }
   
9. int main()
   
10. {
    
11.         int n;
    
12.         cin >> n;
    
13.         long long s = 0;
    
14.         for(int five = 0; five*5 <= n; ++five) {
    
15.                 int one_two = n - 5 * five;
    
16.                 s += one_and_two_count(one_two);
    
17.         }
    
18.         cout << s;
    
19.         return 0;
    
20. }

复制代码

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

zhangjinxuan

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

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