递归求解汽水瓶问题

解题思路:
由题可知每3个空瓶可换一瓶汽水

换来的汽水喝完后又会产生空瓶

则可利用递归来循环调用解决此题

即：设一共有10个空瓶

10%3=3......1

此时还有3+1=4个空瓶（用9个空瓶换3瓶水，喝完了产生3个空瓶，加上上次换完了还剩的一个空瓶换不出去）

4%3=1......1

此时有2个空瓶，可以找老板借一瓶水喝完还剩2+1=3个瓶子，再换一瓶水还给老板（此处为固定情况，每当最后还剩两个瓶子时可换得一瓶水）

以上面的式子可推广为

n（用户输入）%3=a(换得的水)......b(换完剩下的瓶子)

（a+b）%3=c......d

......

以此类推，则可用递归调用求解此题

直到最后剩下的空瓶不够换一瓶水的时候退出递归输出最后换得的总水数

注意事项:

用于记录的中间数据在每次用完后需要做置零操作

参考代码:

#include<iostream>

using namespace std;

int b = 0;

int c = 0;

int d = 0;//记录已喝的瓶数

int dfs(int a)

{

    b = a % 3;//未换完的空瓶

    c = a / 3;//已换到的满瓶

    d += c;//记录已喝的瓶数

    if (b + c < 3)//退出条件，当空瓶数不足3个时，再也换不到了

    {

        if (b + c == 2)

            return ++d;//根据题意可知，当剩2个空瓶时可找老板借一瓶，再多喝一瓶

        else

            return d;

    }

    dfs(b + c);

}

int main()

{

    int a = 0;

    while(cin >> a&&a>0)//输入a且当a>0时循环继续

    {

        b = c = d = 0;//把原有参数重新置零以免出错

        cout << dfs(a) << endl;

    }

    return 0;

}