HDU1284-钱币兑换问题-阿里云开发者社区

开发者社区> 光仔december> 正文

HDU1284-钱币兑换问题

简介:
+关注继续查看

钱币兑换问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5258    Accepted Submission(s): 2989


Problem Description
在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
 

Input
每行只有一个正整数N,N小于32768。
 

Output
对应每个输入,输出兑换方法数。
 

Sample Input

2934 12553
 

Sample Output

718831 13137761
 

Author
SmallBeer(CML)
 

Source



//数学问题

/*思路:n分钱分成零钱符合x1+2*x2+3*x3的公式,随着x1,x2,x3取不同值就有不同的分法。

那么,先确定x3的值就可以确定x1与x2的值,确定x2的值那x1的值一定是定值,不需要求。

所以,先定x3的值,假设x3=k,那么x1+2*x2=n-3*k,重点来了,此时只要知道x2的取值范围就可以

得到当x3等于k时有多少种分法了。x2的范围并不难求,假设没有x1,那么2*x2<=n-3*k,则0<=x2<=(n-3*k)/2,

即x2一共有(n-3*k)/2+1种可能,也就是当k3取某个值时一共有(n-3*k)/2+1种分法。

所以,将k3的所有值(k3*3<=n)取完,每取一次值就加一次(n-3*k)/2+1,最终得到分n分钱所有的可能性!*/

AC代码:

#include<stdio.h>
#include<string.h>
int main()
{
	int i,n,sum;
	while(scanf("%d",&n)!=EOF)
	{
		sum=0;
        for(i=0;i*3<=n;i++)
		{
			sum+=(n-i*3)/2+1;
		}
		printf("%d\n",sum);
	}
	return 0;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【HDU 4547 CD操作】LCA问题 Tarjan算法
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4547 题意:模拟DOS下的cd命令,给出n个节点的目录树以及m次查询,每个查询包含一个当前目录cur和一个目标目录tar,返回从cur切换到tar所要使用的cd命令次数: 注意这里的cd命令是简化版,只能进行如下两种操作:   1.
819 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
10840 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10203 0
hdu 3790 最短路径问题
点击打开链接hdu 3790 思路:最短路+Dijkstra 分析:由于题目要求在最短路径的时候花费最少,那么这就是在做松弛操作的时候判断一下当前的选择的边的花费是不是最少的,那么这样就可以求出最少的花费。
669 0
+关注
光仔december
目前致力于JavaEE(struts/hibernate/spring/MyBatis等框架)、数据库(Mysql/oracle)、静态页面(Html/Css)技术和脚本(JavaSript/JQuery/Ajax)等技术方面的研究
497
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载