問題描述:
假設(shè)1元錢買一瓶水，三個(gè)空瓶可以換一瓶水。初始n元最終可以喝到幾瓶水？

初步思路:
1、利用遞推的思想，將現(xiàn)有空瓶可兌換的瓶數(shù)加上余下的空瓶數(shù)作為新的空瓶數(shù)進(jìn)行下一步計(jì)算，直到新的空瓶數(shù)小于3時(shí)停止。
2、每三個(gè)空瓶可以得到一瓶水和一個(gè)空瓶，也就是說每兩個(gè)空瓶可以使喝到的水+1，因此可以得出遞推公式:
3、由遞推公式易知每兩個(gè)空瓶可得1瓶水，因此整理后可得到通用計(jì)算公式：
其中表示整除，mod表示取余

代碼如下:

def buy_water(n):
    # 遞推實(shí)現(xià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):
    # 公式實(shí)現(xià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