当前位置： 移动技术网 > IT编程>开发语言>C/C++ > SICP——换零钱递归解法（树形递归）

SICP——换零钱递归解法（树形递归）

2019年03月11日  | 移动技术网IT编程  | 我要评论

广东省委常委刘可为,综漫半神,秦宜智父亲

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

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网