换水瓶

问题描述:
假设1元钱买一瓶水，三个空瓶可以换一瓶水。初始n元最终可以喝到几瓶水？

初步思路:
1、利用递推的思想，将现有空瓶可兑换的瓶数加上余下的空瓶数作为新的空瓶数进行下一步计算，直到新的空瓶数小于3时停止。
2、每三个空瓶可以得到一瓶水和一个空瓶，也就是说每两个空瓶可以使喝到的水+1，因此可以得出递推公式:
3、由递推公式易知每两个空瓶可得1瓶水，因此整理后可得到通用计算公式：
其中表示整除，mod表示取余

代码如下:

def buy_water(n):
    # 递推实现
    num = n
    empty = num
    while True:
        if empty < 3:
            break
        num += empty // 3
        empty = empty // 3 + empty % 3
    return num


def buy_water_(n):
    # 空瓶换水递推
    def exchange(x):
        if x < 3:
            return 0
        else:
            return 1 + exchange(x - 2)

    return n + exchange(n)


def buy_water_formula(n):
    # 公式实现
    if n % 2 == 0 and n != 0:
        return n + n // (3 - 1) - 1
    else:
        return n + n // (3 - 1)


if __name__ == '__main__':
    print(buy_water(30))
    print(buy_water_(30))
    print(buy_water_formula(30))
    # all out 44