JAVA递归思想求解

Question

题目：每 3 个可乐盖可兑换 1 瓶子可乐，求买 n 瓶可乐最终可获得的可乐瓶子数。
拿到题目，于是小弟先把从1-24的列了出来，解决发现当买24瓶可乐的时候，公式不满足了，求推解过程，小弟想彻底理解递归

// 1 = 1
// 2 = 2
// 3 = 3 + 1 = 4 n + n/3
// 4 = 4 + 1 = 5 n + n/3
// 5 = 5 + 1 = 6 n + n/3
// 6 = 6 + 2 = 8 n + n/3
// 7 = 7 + 2 = 9 n + n/3
// 8 = 8 + 2 = 10 n + n/3
// 9 = 9 + 3 + 1= 13 n + n/3 + n/3/3
// 10 = 10 + 3 + 1 = 14 n + n/3 + n/3/3
// 11 = 11 + 3 + 1 = 15 n + n/3 + n/3/3
// 12 = 12 + 4 + 1 = 17 n + n/3 + n/3/3
// 13 = 13 + 4 + 1 = 18 n + n/3 + n/3/3
//...
// 24 = 24 + 8 + 2 + 1=35 n + n/3 + n/3/3 + 1
//如果购买瓶数推解成n 结果是s

private static int recursion(int n) {
if(n<3){
return n;
}else{//大于3瓶要开始换算了
return n + recursion(n/3);
}
}
当购买24 瓶可乐的时候，最后的一个1怎么表示
24 = 24 + 8 + 2 + 1=35 n + n/3 + n/3/3 + ？

Answer 1

public static void main(String[] args) {
System.out.println(recursion(24, 24));
}

/***
 * 
 * @param drink
 *            多少瓶饮料
 * @param lid
 *            多少个盖子
 * @return
 */
private static int recursion(int drink, int lid) {
if (lid < 3) {
// 如果盖子小于3个，则不符合条件，结束递归
return drink;
}
// 可以用盖子再兑换多个瓶饮料
int addDrink = lid / 3;
// 剩余的盖子
int leftLid = lid - addDrink * 3 + addDrink;
return recursion(drink + addDrink, leftLid);

}追问

大神您好，知道这个是解出来了，但是我没理解这个推算过程，可以给小弟详细解释一下吗？谢谢

追答

把饮料和盖子的变量分开，事情就简单点

递归问题要一点，什么时候结束递归；这个问题就是盖子少于3个结束

我画了个流程图，你看下

网页链接

Answer 2

你公式从根本上就错了， 试下下面的公式吧
F(n) = n + n/3
F ： 最终得到的可乐瓶数
n : 购买的可乐数量

Answer 3

@org.junit.Test
public void colaCount(){
getCola(5,false);
System.out.println(allCount);
System.out.println(residue);
}

int residue = 0;//记录剩余瓶盖
int allCount = 0;

public void getCola(int count,boolean cleanResidue){
allCount = allCount+count;
residue= residue + count%3;
if(cleanResidue){
residue = residue-3;
}
if(count<3){
if(residue>=3){
getCola(residue/3,true);
}
}else{
int exchangeCount = count/3;
if(residue>=3){
getCola(residue/3,true);
}

getCola(exchangeCount,false);
}

}