题目的主要信息：

• 规定：三个空汽水瓶可以换一瓶汽水，喝完之后的空汽水瓶可以继续换，如果最后剩两个空瓶，可以找老板借一瓶，喝掉后用三个空瓶换一瓶汽水还给老板
• 问有n个汽水瓶最多能喝多少瓶汽水
• 多次输入，最后一次输入是0，不处理

方法一：递归

具体做法：

我们整理一下，三个空汽水瓶可以换一个，喝掉后增加一个空汽水瓶，因此在$n>=3n>=3$的时候，相当于用两瓶空汽水瓶换一瓶喝的，而按照题目的意思最后剩余两瓶可以喝到一瓶，而最后剩余一瓶则不能喝到一瓶，因此可以递归解决。

#include<iostream>
using namespace std;

int recursion(int n){
    if(n == 1) //只剩1个空瓶，没办法喝到
        return 0;
    if(n == 2) //剩2个空瓶，可以喝一瓶
        return 1;
    return recursion(n - 2) + 1; //减去三个空瓶得到可以喝一瓶，之后得到一个空瓶
}

int main(){
    int n;
    while(cin >> n){
        if(n == 0) //0表示结束
            break;
        cout << recursion(n) << endl; //递归处理
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，递归过程中$nn$每次减少2，要递归$n\mathrm{/}2n/2$次
• 空间复杂度：$O(n)O(n)$，递归栈的大小为$n\mathrm{/}2n/2$

方法二：迭代

具体做法：

上面也提到了，两个空瓶换一个汽水，因此我们也可以迭代减少$nn$的值，增加喝汽水的瓶数，最后检查是1还是2即可。

#include<iostream>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        if(n == 0) //0表示结束
            break;
        int count = 0;
        while(n > 2){
            count++;
            n -= 2; //每次两个空瓶换一瓶汽水
        }
        //检查最后剩余
        if(n == 2) 
            cout << ++count << endl;
        else
            cout << count << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一共迭代$n\mathrm{/}2n/2$次
• 空间复杂度：$O(1)O(1)$，无额外空间

方法三：数学规律

具体做法：

其实从方法二我们就可以看出，每两个空的换一瓶，最后剩余2就再换，剩余1就不换，那不就是n/2吗？直接计算即可。

#include<iostream>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        if(n == 0) //0表示结束
            break;
        cout << n / 2 << endl; //直接输出n/2
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(1)O(1)$，直接输出
• 空间复杂度：$O(1)O(1)$，无额外空间