大家好,又见面了,我是你们的朋友全栈君。
今天老范问了我一个问题 问题: 一个人买汽水,一块钱一瓶汽水,三个瓶盖可以换一瓶汽水,两个空瓶可以换一瓶汽水 问20块钱可以买多少汽水? 注意:使用递归
这一题乍一看,哎哟,这么简单,能买几瓶?恩。。 五瓶! 为啥啊?
多了我喝不完啊!
老范说,喝不完关你屁事,又不是给你喝
哦哦哦,那没事儿了,我想想。 在知道自己的人生安全得到了保障之后,我冷静下来仔细思考了如何用递归实现这个问题
首先想了想什么是递归
以及递归的注意事项:
不能100%成立也就是说,要有终止条件,达成某个条件,就要跳出递归调用
瓶盖和空瓶子换饮料,这是一个怎么样的过程?了解了这个过程,才能分析出这中间哪些变量在发生变化,转换,以及变化到哪个程度,就不满足继续递归的条件了,也就是满足终止条件了。
(这是用processon画的https://www.processon.com/很好用) (推荐一波,processon速打钱来!!!!!) drink表示购买和置换的饮料 cup表示瓶盖 bottle表示空瓶子 首先分析每一个成员变量,
**所以置换的过程就是cup-3,drink+1 或者bottle-2,drink+1的过程。 所以递归调用的条件就是每一轮置换后,cup>=3||bottle>=2, &&drinks<1也就是跳出递归的条件是:每一轮置换后cup<3&&bottle<2 &&drinks<1**
因为在这个过程中,三个元素drink, cup, bottle都有连续的变化,所以递归调用时要将三个参数都传就去。 定义方法体 `public static int Soda(int drink, int cup, int bottle){
} ` 除了第一轮之外,每一轮的drink=cup/3+bottle/2, cup=cup%3, bottle=bottle%2 所以我本来是这么写的(错的):
public static int Soda(int drinks,int caps,int bottles){
if(caps<3&&bottles<2&&drinks<1){
return drinks;
}else{
caps+=drinks;bottles+=drinks;
drinks=caps/3+bottles/2;
caps%=3; bottles%=2;
return Soda(drinks,caps,bottles)+drinks;
}
}
得出来是93,我惊呆了,拿给老范,老范说,不不不还有更多,应该是113。
113,那就是说,我缺少20个,正好是第一轮拿钱买的20个。我分析了一下,发现这个代码在第一次递归过程中,return Soda(drinks,caps,bottles)+drinks 这后面跟的drinks已经被第二次置换的drinks替换掉了,导致少了第一次花20块大洋买的drinks。
所以得调整顺序 将drinks=caps/3+bottles/2的过程放在return内部 return Soda(caps/3+bottles/2,caps,bottles)+drinks; 然后崩了,因为caps%=3;bottles%=2已经发生了,所以caps/3+bottles/2已经小于1了,直接满足了终止条件跳出了循环
将这两句调换顺序并放在if前,这样在每次递归时,首先将caps和bottles置换掉,之后再加上就不会影响drinks的置换数量。
然后我还发现,终止条件caps<3&&bottles<2&&drinks<1有点啰嗦,因为caps+=drinks;bottles+=drinks;只要drinks<1,就表示caps和drinks肯定满足终止条件。
最终代码:
public static int Soda(int drinks,int caps,int bottles){
caps%=3; bottles%=2;
caps+=drinks; bottles+=drinks;
if(caps<3&&bottles<2){
return drinks;
}
else{
return Soda(caps/3+bottles/2,caps,bottles)+drinks;
}
}
得出113瓶。。。。 久久不能释怀,感觉错过了一个亿 v_v
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/127468.html原文链接:https://javaforall.cn