SICP——换零钱递归解法(树形递归)
2019-03-10 11:47:54来源:博客园 阅读 ()
将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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- DSA_07:递归算法 2020-03-30
- 递归函数使用动态数组遇到的问题 2020-03-26
- 递归遍历树 2019-11-16
- RWMutex:共享/专有的递归互斥锁 2019-10-12
- c++递归函数 2019-09-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash