一、问题引入

有这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是5瓶，方法如下：先用9个空瓶子换3瓶汽水，喝掉3瓶满的，喝完以后4个空瓶子，用3个再换一瓶，喝掉这瓶满的，这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水，喝掉这瓶满的，喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有n个空汽水瓶，最多可以换多少瓶汽水喝？

有一位同学给出了如下图所示的算法

编程思维题目-对喝汽水问题的解法整理

那么问题来了，这样写到底正确吗？？？？？？？

二、实际操作

将上图代码运行一下

1. public class Test02 {

2. public static int empty(int x){

3. if (x>3){

4. return x+empty(x/3+x%3);

5. }

6. if (x==2){

7. return 1;

8. }

9. return 0;

10. }

11.

12. public static void main(String[] args) {

13. System.out.println(empty(10)-10);

14. }

15. }

结果确实是5

三、理论分析

(一) 算法描述

换汽水的过程描述如下

1. （拿着空瓶子）手里有n个空瓶子，0瓶未喝的汽水

2. （换汽水）换n/3个汽水，余下n%3个空瓶子

3. （喝汽水）喝掉换来的汽水，手里有n/3+n%3个空瓶子，0瓶未喝的汽水

4. （判断）如果现在手里拿的空瓶子>2，执行1

如果手里拿的空瓶子==2，再换一瓶汽水，结束

手里拿的空瓶子<2，结束

(二) 实例演示算法

手里有10个空瓶子的计算过程如下

现在手里有的空瓶子	现在手里有的汽水数	喝在肚子里的汽水数
10	0
10%3=1	10/3=3
10%3+10/3=4	0	3
4%3=1	4/3=1
4%3+4/3=2	0	1

现在手里有的汽水数为0代表把用空瓶换来的汽水喝掉了

最后剩2个空瓶子，还能换一瓶汽水

喝在肚子汽水数 = 3+1+1 = 5

(三) 问题中提到的程序运算过程

empty(10)-10

= 10+empty(4)-10

= 10+4+empty(2)-10

= 10+4+1-10

根据分析，汽水数应该 = 3+1+1 ，而不是= 10+4+1-10

显然虽然程序运行的结果和正确答案相同，但是计算过程很可能有问题

四、进一步验证程序

上面的分析只是表达原代码的计算过程可能有问题，下面我们用手里20个空瓶子的情况再进一步验证程序

现在手里有的空瓶子	现在手里有的汽水数	喝在肚子里的汽水数
20	0
20%3=2	20/3=6
20%3+20/3=8	0	6
8%3=2	8/3=2
8%3+8/3=4	0	2
4%3=1	4/3=1
4%3+4/3=2	0	1

因为最后剩2个空瓶子，还能再换一瓶汽水

喝在肚子里的汽水数 = 6+2+1+1 = 10

其实现在问题就来了，10个空瓶的时候，原程序输出empty(10)-10

那20个空瓶，后面应该减几呢?

我试了一下，empty(20)-10=23，empty(20)-20=13，和我们算出的答案都不一样

五、解决问题

下面给出两种程序的写法，来实现这个问题

(一) 根据算法描述，用循环解决

public static void main(String[] args) {
    int empty = 10; //现在手里有的空瓶子数
    int soda = 0;   //换来汽水后，现在手里拿着的汽水数
    int sum = 0;    //计算一共喝了几瓶汽水

    while (empty > 2) { //如果现在手里拿的空瓶子>2，循环
        soda = empty / 3; //开始换汽水
        sum = sum + soda;
        soda = 0;          //把汽水喝掉
        empty = empty%3+empty/3;   //喝掉换来的汽水后，手里有的空瓶子
    }
   if (empty == 2) {
        System.out.println(sum + 1);
    } else if (empty < 2) {
        System.out.println(sum);
    }
}

(二) 递归实现

a. 定义函数：int soda(intempty)

b. 函数描述：empty代表手里有的空瓶，返回一共喝了几瓶汽水

c. 递归公式描述：喝总汽水数 = 直接换来的汽水+剩的空瓶还能换的汽水

d. 递归公式：soda = empty/3+soda(empty/ 3 + empty % 3)

private static int soda(int empty) {
    if (empty > 2) {
        return empty / 3 + soda(empty / 3 + empty % 3);
    }
    if (empty == 2) {
        return 1;
    }
    return 0;
}
  
  public static void main(String[] args) {
    int sodaCount = soda(10);
    System.out.println(sodaCount);
}

六、结语

1. 卖汽水的老板真好，2个空瓶都给换汽水

2. 小张真能喝汽水

编程思维题目-对喝汽水问题的解法整理

一、 问题引入

二、 实际操作

三、 理论分析