瓶盖换水问题

问题

矿泉水 2 块钱 1 瓶, 4 个瓶盖或 2 个空瓶可以换 1 瓶矿泉水( 瓶盖跟空瓶要单独计算, 即 2瓶盖 + 1空瓶 ≠ 1瓶水 ), 100块钱可以喝多少瓶?

解题思路

先将钱全部花掉买水, 喝完再用瓶盖或者空瓶换水, 之后每次喝完都用剩下的瓶盖跟空瓶去换水直到瓶盖跟空瓶都不足以换水.
很明显，我们可以用递归来解决:

C 语言实现

/**
 买水函数
 
 @param money 用于买水的钱
 @return 最终可以买到多少瓶水
 */
int drinkPlentyOfFluids(int money);

/**
 瓶盖循环利用
 
 @param gai 盖子数
 @param ping 瓶子水数
 @return 最终可以用盖子跟瓶子换多少瓶水
 */
int cyclicuUtilization(int gai, int ping);

int main(int argc, const char * argv[])
{
    int money = 100;
    int waterCount = drinkPlentyOfFluids(money);
    printf("%d 块可以喝 %d 瓶\n", money, waterCount); // 算得100块可以195瓶, 哭晕卖水的
    return 0;
}

int drinkPlentyOfFluids(int money)
{
    int moneyBuyCount = money / 2;
    int waterCount = moneyBuyCount + cyclicuUtilization(moneyBuyCount, moneyBuyCount);
    return waterCount;
}

int cyclicuUtilization(int gai, int ping)
{
    // 多少个 瓶盖 / 空瓶 可以换 1 瓶水
    int gaiExchangeNum = 4, pingExchangeNum = 2;
    // 当盖子跟瓶子都不够换水就结束
    if(gai < gaiExchangeNum && ping < pingExchangeNum)
        return 0;
    // 水的瓶数 = 盖子 / 多少个盖子可以换 + 瓶子 / 多少个瓶子可以换;
    int count = gai / gaiExchangeNum + ping / pingExchangeNum;
    // 计算换完之后还剩多少个盖子跟瓶子
    int gaiRemain = gai % gaiExchangeNum, pingRemain = ping % pingExchangeNum;
    // 再用之前剩下的盖子跟瓶子 + 新换的空瓶跟盖子换水
    count += cyclicuUtilization(gaiRemain + count, pingRemain + count); // 递归
    return count;
}

思考

运行之后我们可以发现: 喝完195瓶水之后还剩下3个瓶盖跟1个空瓶换不了.
我该怎么才能将我的盖子跟空瓶换成水, 不造成浪费呢?

骚操作

这时我们发现：3瓶盖+1瓶盖 = 1瓶水、1空瓶+1空瓶 = 1瓶水，假设我们能到回收站借一个带瓶盖的空瓶，我们就可以再喝两瓶水，喝完还一个带瓶盖的空瓶给回收站。
这时候，我们还剩一个带瓶盖的空瓶。
同理，我们借1还1余0瓶2盖。
最后借2还2余0瓶0盖。
∴我们极限状态下100块能喝到的水 = 195 + 2 + 1 + 2 = 200瓶，也就是每两块钱能喝4瓶水（1块钱买不了一瓶， 要是允许再借则各位自己脑补了）。

最终代码

/**
 买水函数
 
 @param money 用于买水的钱
 @param canBorrow 0 -> 不能去借 else -> 能借
 @return 最终可以买到多少瓶水
 */
int drinkPlentyOfFluids(int money, int canBorrow);

/**
 瓶盖循环利用
 
 @param gai 盖子数
 @param ping 瓶子水数
 @return 最终可以用盖子跟瓶子换多少瓶水
 */
int cyclicuUtilization(int gai, int ping);

int main(int argc, const char * argv[])
{
    int money = 101;
    int waterCount = drinkPlentyOfFluids(money, 1);
    printf("%d 块可以喝 %d 瓶\n", money, waterCount); // 算得101块可以200瓶, 更加哭晕卖水的了
    return 0;
}

int drinkPlentyOfFluids(int money, int canBorrow)
{
    if(canBorrow != 0)
    {
        return money / 2 * 4;
    }
    int moneyBuyCount = money / 2;
    int waterCount = moneyBuyCount + cyclicuUtilization(moneyBuyCount, moneyBuyCount);
    return waterCount;
}

int cyclicuUtilization(int gai, int ping)
{
    // 多少个 瓶盖 / 空瓶 可以换 1 瓶水
    int gaiExchangeNum = 4, pingExchangeNum = 2;
    // 当盖子跟瓶子都不够换水就结束
    if(gai < gaiExchangeNum && ping < pingExchangeNum)
        return 0;
    // 水的瓶数 = 盖子 / 多少个盖子可以换 + 瓶子 / 多少个瓶子可以换;
    int count = gai / gaiExchangeNum + ping / pingExchangeNum;
    // 计算换完之后还剩多少个盖子跟瓶子
    int gaiRemain = gai % gaiExchangeNum, pingRemain = ping % pingExchangeNum;
    // 再用之前剩下的盖子跟瓶子 + 新换的空瓶跟盖子换水
    count += cyclicuUtilization(gaiRemain + count, pingRemain + count); // 递归
    return count;
}