将1美元(100美分)换成半美元,1/4美元,10美分,5美分,1美分的零钱,一共有多少种换法?
书上写的思路很简单,就是把一美元换成:
1:半美元+其他5种硬币的组合;
2:不加半美元,其他4种硬币的组合;
数学函数是,f(m,n)=f(m-coin[n-1],n)+f(m,n-1);不过有特殊情况:
1:m=0时,表示有1种组合;
2:m<0或n=0时无法组合;
综上,代码如下:
1 /* 2 2019,3,10 3 from sicp changecoin by sky 4 */ 5 #include<iostream> 6 using namespace std; 7 int changecoin(int money,int n); 8 int coin[5]={1,5,10,25,50}; //type of coins 9 int main(void){ 10 int money,n; 11 int type=0; 12 cout<<"money:"; 13 cin>>money; 14 cout<<"n:"; 15 cin>>n; 16 type=changecoin(money,n); 17 cout<<"type:"<<type<<endl; 18 return 0; 19 } 20 int changecoin(int money,int n){ 21 if(money==0){ 22 return 1; 23 } 24 else if(money<0||n==0){ 25 return 0; 26 } 27 else{ 28 return changecoin(money-coin[n-1],n)+changecoin(money,n-1); 29 } 30 }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/604870.html