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 }
推荐阅读
-
SICP——换零钱递归解法(树形递归)
-
关于xuzuning版主发的非递归树形数组构造函数有关问题
-
关于xuzuning版主发的非递归树形数组构造函数有关问题
-
thinkPHP实现递归循环栏目并按照树形结构无限极输出的方法_php实例
-
thinkPHP实现递归循环栏目并按照树形结构无限极输出的方法_php实例
-
SQL Server 树形表非循环递归查询的实例详解
-
基于递归实现的php树形菜单代码_PHP
-
利用java+mysql递归实现拼接树形JSON列表的方法示例
-
asp.net TreeView递归循环子节点生成树形菜单实例
-
Vue递归组件+Vuex开发树形组件Tree--递归组件的简单实现