解题总结-1-空瓶换汽水

题目描述

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

解题思路

假如有n个空水瓶，那么n div 3 = a ... b，就是说n个水瓶直接能够换到的汽水为a个，那么剩下b个空瓶子不能够换汽水，加上喝完a瓶汽水剩下a个空瓶。现在又剩下a+b个空瓶，做下一次交换。因此这是一个递归问题。注意到当剩下两个瓶子时可以“借”一瓶汽水得到3个空瓶来抵账，递归的结束条件有两个。

我的解法（C++）

#include <iostream>
#include <vector>
using namespace std ;

auto SWAPBOTTLENUM = 3 ;//3个konp
int solution(int emptyBottles)
{
    if(emptyBottles == SWAPBOTTLENUM-1)
        return 1 ;
    else if(emptyBottles < SWAPBOTTLENUM-1)
        return 0 ;
    int drinked = 0 ;
    int rest = 0 ;
    drinked = emptyBottles / SWAPBOTTLENUM ;
    rest = drinked + emptyBottles % SWAPBOTTLENUM ;
    return drinked + solution(rest) ;
}

int main(int argc, char *argv[])
{
    vector<int> emp ;
    vector<int> sol ;
    int temp ;
    while(cin >> temp && temp != 0)
        emp.push_back(temp) ;

    for(auto item : emp)
        sol.push_back(solution(item)) ;

    for(auto item : sol){
        cout << item << endl ;
    }
    return 0;
}

方案改进

我的算法完全就是按照问题描述的思路来写的，可以用递归也可以使用迭代方法。
不过在评论区看到了更优的解法。
因为两个空瓶可以完全兑换一瓶汽水，那么我可以每次拿出两个空瓶换一瓶汽水，也没有空瓶留下，这种兑换的次数一共有n / 2次，所以一共可以得到n / 2瓶汽水。过程太简单，算法就不写了。