钱币兑换问题
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 114 Accepted Submission(s) : 57
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input
每行只有一个正整数N,N小于32768。
Output
对应每个输入,输出兑换方法数。
Sample Input
2934
12553
Sample Output
718831
13137761
//这题目用母函数要超时,可以用多重背包解
#include <stdio.h>
#include <string.h>
#include <time.h>
#define _MAX 32790
long c1[_MAX], c2[_MAX];
int m[4] = {0, 1, 2, 3};
int main()
{
int nNum;
int i, j, k;
while(~scanf("%d", &nNum))
{
for(i = 0; i <= nNum; i++)
{
c1[i] = 0;
c2[i] = 0;
}
c1[0] = 1;
//1 *(1 + x + x^2 + ...) *( 1 + x ^2 + x^4 + ...) * (1 + x^3 + x^ 6 + ...)
for(i = 1; i <= 3; i++)
{
for(j = 0; j <= nNum; j++)
for(k = 0; k + j <= nNum; k+=m[i])
c2[k + j] += c1[j];
for(j = 0; j <= nNum; j++)
{
c1[j] = c2[j];
c2[j] = 0;
}
}
printf("%ld\n", c1[nNum]);
//printf("Time Used = %.2lf\n", (double)clock() / CLOCKS_PER_SEC);
}
return 0;
}
分享到:
相关推荐
2.求解钱币兑换问题 题目描述: 某个国家仅有1分、2分、5分硬币,将钱n(n>=5)兑换成硬币有很 多种兑法,编写实验程序计算出10分钱有多少种兑法,并列出每种 兑换方式。 3.沙漠问题 题目描述: -辆吉普车来到1000km宽的...
对最少硬币兑换问题的算法进行了分析,并给出了实现
用下拉框编写各类货币的兑换。给定货币兑换率。
问题描述:设有 n 种不同的钱币各若干张,可用这 n 种钱币产生许多不同的面值。试 设计一个算法,计算给定的某个面值,能有多少种不同的产生方法。例如有 1 分3 张,2 分 3 张,5 分 1 张,则能组成 7 分面值的...
蛮力法新手可看一下,超级入门代码,看看入门蛮力法,高手绕路
货币兑换_VB源程序:实现各国之间的货币兑换功能,主要使用VB的selectcase语句。
在线的货币兑换平台,可帮助全球各地的个人和企业将货币从一种货币兑换为另一种货币。该货币兑换平台是 Codecanyon 中最先进的脚本。
在线的货币兑换平台,可帮助全球各地的个人和企业将货币从一种货币兑换为另一种货币。该货币兑换平台是 Codecanyon 中最先进的脚本。
//设有6种不同面值的硬币,各硬币的面值分别为5分、1角、2角、5角、1元和2元。 //现在要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数 //存于数组Coins[1:6]中,假设商店里各面值的硬币有足够...
网站虚拟货币兑换商家优惠系统.ppt
钱币兑换方法(1).cpp
欧美货币兑换网站模板
汇率兑换小工具
个人货币兑换协议书范本.doc
hdu杭电所有题目按照ac数量排序,python分析
网站虚拟货币兑换商家优惠系统.pptx
货币兑换计算器 货币兑换计算器
##部署Heroku 货币兑换货币兑换
货币兑换appUI界面设计 sketch素材下载 app界面设计、GUI界面设计、sketch、ui界面设计、货币兑换、金融
货币兑换