欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-01-26 23:22:58
将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:... ......
将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 }