SICP——换零钱递归解法(树形递归)

2019-03-10 11:47:54来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

将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 }

 


原文链接:https://www.cnblogs.com/skylfy/p/10506604.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:【算法笔记】B1010 一元多项式求导

下一篇:ExcludeClipRect区域裁剪问题