题目主要信息

1、三个空汽水瓶换一瓶汽水

2、如果有两个空气水瓶可以先问老板借一个空瓶子

3、多组输入，输入0表示输入结束

方法一：递归和模拟

具体方法

直接举例来分析，开始是10个空瓶子。 1、换了10/3=3瓶，之后这三瓶又加上10%3=1瓶，一共4瓶。 2、4瓶又去换，就是又一次整除3的过程，换了4/3=1瓶，再加上4%3=1瓶。 3、此时还有2瓶，先不考虑去找老板借。

这是一个重复过程，即整除3以后加上对3取余，然后再整除3加上对三取余。 可以总结下面的一个while循环

            while(num/3>0){
                count+=num/3;
                //此时还有多少瓶盖
                num = num/3+num%3;
                //可以向老板借一个
                if(num == 2){
                    num = num+1;
                }
            }

根据上面的代码，我们直接写Java代码，代码如下

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while((s = bf.readLine())!=null){
            int num = Integer.parseInt(s);
            if(num == 0){
                return;
            }
            int count = 0;
            while(num/3>0){
                count+=num/3;
                //此时还有多少瓶盖
                num = num/3+num%3;
                //可以向老板借一个
                if(num == 2){
                    num = num+1;
                }
            }
            System.out.println(count);
        }
    }
}

复杂度分析

• 时间复杂度：$O(lo{g}_3(n))O(log\_3(n))$,需要遍历到num为0为止
• 空间复杂度：$O(1)O(1)$

方法二：数学方法

具体做法

通过分析题目我们可以得到当有两个瓶盖的时候可以先向老板借一个，喝完再还给老板，所以可以理解成我们只要有两个瓶盖就可以喝一瓶，那么我们直接用num除于2就可以得到最终可以喝到的瓶数。

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while((s = bf.readLine())!=null){
            int num = Integer.parseInt(s);
            if(num == 0){
                return;
            }
            System.out.println(num/2);
        }
    }
}

复杂度分析

• 时间复杂度：$O(1)O(1)$,不用遍历直接输出。
• 空间复杂度：$O(1)O(1)$,直接输出，只用一个num存数字