大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
硬币找零&&爬楼梯&&猴子摘香蕉
假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。
#include”CoinProblem.h”
#include
intcountNum=MAX;
voidCoinProblem(int*coin,intLength,intValue,intcount){
if(Value==0){
if(countNum>count){
countNum=count;
}
return;
}
for(inti=0;i
if(Value>=coin[i]){
CoinProblem(coin,Length,Value-coin[i],count+1);
}
}
}
#ifndefCOIN_PROBLEM_H
#defineCOIN_PROBLEM_H
#defineMAX65535
externintcountNum;
voidCoinProblem(int*coin,intLength,intValue,intcount);
#endif
#include”CoinProblem.h”
#include
intmain(){
intcoin[3]={1,3,5};
CoinProblem(coin,3,5,0);
std::cout<
}
这些问题都是一类问题，你猴子摘香蕉、硬币找零、爬楼梯等。
这类问题的共同点就是你要问题解决问题，也就是说你要恰好把问是不多不少地解决，不管你怎么摘香蕉，不管你一次
是摘几个，你得把香蕉摘完。你得恰好找别人那么钱，不能多也不能少。爬楼梯也一样啰。。反下是解决问题。
这个不像背包问题，因为背包是不一定能装满的，也就是结束条件是不确定的。
但是我们不要管是不是恰好，因为我们采用了梯归。因为递归的好处是把所有能考虑的问题都考虑了，包括恰好解决问题和
把问题所要求的多，或者少。。
if(Value==0){
if(countNum>count){
countNum=count;
}
return;
}
如上面的代码就是专门用来限制结束条件的，只有当我们找的钱恰好是那么多是，我们才会计数。
于是我们可能通过自己的限定条件来限制要计数的情况。
特注意的是：
由于我自己的疏忽，导致在以前写这些代码的时候出了些小问题，以前我是这样写的
voidCoinProblem(int*coin,intLength,intValue,intcount){
if(Value==0){
if(countNum>count){
countNum=count;
}
return;
}
for(inti=0;i
if(Value>=coin[i]){
CoinProblem(coin,Length,Value-coin[i],++count);
}
}
}
看代码中红色的部分，这里成了++count,这里是改变了count的值，我这意思是改变了在这一次递归运算中的所有count的值，也就是说，i=0时
如count=2，同时也符合条件，也就是说进入那个条件判断语句，于是用++count时会发现count变成了3，这确实是我们所期望的，但是
如果下一次“归”回来后，i=1时，那时发现count一开始就是3了。不再是我们期望的2了。
于是正确的写法应该是这样：
voidCoinProblem(int*coin,intLength,intValue,intcount){
if(Value==0){
if(countNum>count){
countNum=count;
}
return;
}
for(inti=0;i
if(Value>=coin[i]){
CoinProblem(coin,Length,Value-coin[i],count+1);
}
}
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/189390.html原文链接：https://javaforall.net
