A - 钱币兑换问题

爱被打了一巴掌 2022-03-07 15:22 192阅读 0赞

### 题目描述： ###

在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。  
Input  
每行只有一个正整数N，N小于32768。  
Output  
对应每个输入，输出兑换方法数。  
Sample Input  
2934  
12553  
Sample Output  
718831  
13137761

##### 分析： #####

这道题，首先第一反应，暴力绝对错。  
我们可以这样想，n元，有i个3分的。那么2分的只能有0到（n-i\*3）/2个。剩下的都是一分的。  
那么，我们通过一次遍历就可以得到正确的答案了。  
参考博客：[https://blog.csdn.net/hj1553910/article/details/81488120][https_blog.csdn.net_hj1553910_article_details_81488120]  
参考博客：[https://www.cnblogs.com/A--Q/p/5728315.html][https_www.cnblogs.com_A--Q_p_5728315.html]  
AC代码：

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
     using namespace std;
    int main()
    {
        int n;
        int cnt=0;
        while(~scanf("%d",&n))
        {
            cnt=0;
            for(int i=0;i<=n/3;i++)
            {
                int t=(n-3*i)/2+1;//这里加1的原因是一个2分的都没有，只有1分的
                cnt+=t;
            }
            printf("%d\n",cnt);
        }
    }

[https_blog.csdn.net_hj1553910_article_details_81488120]: https://blog.csdn.net/hj1553910/article/details/81488120
[https_www.cnblogs.com_A--Q_p_5728315.html]: https://www.cnblogs.com/A--Q/p/5728315.html

发表评论取消回复

表情：

评论列表（有 0 条评论，192人围观）

还没有评论，来说两句吧...

相关阅读

相关 2023华为OD面试手撕真题【钱币兑换问题】

来自2023年11月牛客网的网友分享的面经：[华为od面经分享\_牛客网][od] ![6ea5d38f84bc443f80d2ff196fb55f5c.png][] 题目

缺乏、安全感/ 2024年02月18日 11:48/ 0 赞/ 50 阅读

相关钱币兑换问题（完全背包）

钱币兑换问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

￡神魔★判官ぃ/ 2022年08月02日 14:53/ 0 赞/ 201 阅读

相关钱币兑换问题（母函数）

钱币兑换问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

超、凢脫俗/ 2022年08月02日 14:52/ 0 赞/ 199 阅读

相关钱币找零问题

钱币找零问题这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6

待我称王封你为后i/ 2022年06月18日 04:20/ 0 赞/ 250 阅读

相关问题 : 最少钱币数

题目描述这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了 6 种钱币面值为 2、5、10、20、50、100，用来凑 15 元，

短命女/ 2022年06月10日 03:07/ 0 赞/ 207 阅读

相关 hdu 1284 钱币兑换问题

钱币兑换问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

客官°小女子只卖身不卖艺/ 2022年05月31日 09:44/ 0 赞/ 165 阅读

相关 A - 钱币兑换问题

题目描述：在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。 Input 每行只有一个正整数N，N小于32768

爱被打了一巴掌/ 2022年03月07日 15:22/ 0 赞/ 193 阅读

相关 G - 钱币兑换问题

题目描述：在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。 Input 每行只有一个正整数N，N小于32768

我不是女神ヾ/ 2022年02月24日 06:52/ 0 赞/ 255 阅读

相关贪心算法 - 钱币找零问题

这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱

深藏阁楼爱情的钟/ 2022年02月21日 07:10/ 0 赞/ 255 阅读

相关 HDU 1284 钱币兑换问题

include<cstdio> include<cstring> include<cmath> include<algorithm> u

落日映苍穹つ/ 2021年12月22日 11:39/ 0 赞/ 173 阅读