兑换货币的问题

xiaoyi20 2003-07-12 11:00:07

if某人要把一元人民币兑换成零币，问最多有多少种不同的兑换方法？
（PS：面值低于一元的零币有五角，二角，一角和五分，二分，一分工六种。）

...全文

306 5 打赏收藏转发到动态举报

写回复

用AI写文章

5 条回复

切换为时间正序

请发表友善的回复…

发表回复

ZhangYv 2003-07-13

打赏
举报

用一个递归来搜啊,分治...

mmmcd 2003-07-13

打赏
举报

整数拆分问题

f(n,m)：正整数n拆分的最大项为m的种数。
f(n,n-1)+1 n=m
f(n,m) = f(n,m-1)+f(n-m,m) n>m
f(n,n) n<m

看看这个题：http://acm.uva.es/p/v1/147.html

我AC.PE的程序
#include<iostream.h>
#include<stdio.h>

int m[11]={5,10,20,50,100,200,500,1000,2000,5000,10000};
unsigned long note[1002][11];
unsigned long q(int n,int i)
{
if(note[n/5][i]>0)return note[n/5][i];
if(n==5||i==0)
{
note[n/5][i]=1;return 1;
}
if(n<m[i]){
while(n<m[i])i--;
if(!note[n/5][i])note[n/5][i]=q(n,i);
return note[n/5][i];
}
if(n==m[i])
{
note[n/5][i]=q(n,i-1)+1;
return note[n/5][i];
}
note[n/5][i]=q(n,i-1)+q(n-m[i],i);
return note[n/5][i];
}

void main(){
double money;
int n,i;
for(;;){
cin>>money;
if(money==0)break;
n=(int)(money*100);
for(i=0;i<11;i++)
if(m[i]>n)break;
printf("%5.2f ",money);
printf("%-4d\n",q(n,i-1));
}
}

xiaoyi20 2003-07-13

打赏
举报

bulesky2008的观点我看过了，我对这个很感兴趣，并且在
http://expert.csdn.net/Expert/topic/1943/1943535.xml?temp=.8314478
有回复，麻烦bulesky2008帮我详细阐述一下我的回复所问的问题。

mmmcd（超超的）方法好象不能算出来所有的兑换方法。

我用四层循环编的程序结果是3649代码如下：
(PS:把一元看做100分)
#include "conio.h"
main()
{
int n=0,n1,n2,n3,n4,n5,n6;
for(n1=0;n1<=2;n1++)
for(n2=0;n2<=(100-50*n1)/20;n2++)
for(n3=0;n3<=(100-50*n1-20*n2)/10;n3++)
for(n4=0;n4<=(100-50*n1-20*n2-20*n3)/5;n4++)
n=n+(int)((100-50*n1-20*n2-10*n3-5*n4)/2)+1;
printf("n=%d",n);
getch();
}
原理是50*n1+20*2+10*n3+5*n4+2*n5+n6=100
当然我对后面的两个循环做了优化，也就是省去了后面的两个循环。

BlueSky2008 2003-07-13

打赏
举报

由人民币面值设计的特殊性，任何金额都可以表示出来。
你可以去参考下面这个贴子，我证明了半天就是为该题证明这个性质，然后每一步就可以直接确定可选取的数。

http://expert.csdn.net/Expert/topic/1943/1943535.xml?temp=.8314478

设按照由大到小选取零币，每一次选取的币值不超过上一次的币值，同时不超过余下的金额。
大概是这样：
第1次： 50， 20， 10 5 2 1
第2次： 50，20，10，5，2，1 20，10，5，2，1 10，5，2，1 5，2，1 2，1 1
...

xiaoyi20 2003-07-12