算法题：空瓶换可乐问题

2015-04-12 13:03 数据结构与算法算法 , python

算法题：空瓶换可乐问题

问题描述

可乐1元一瓶，两个空瓶可以换一瓶可乐。问：给你一些钱，计算出最多可以喝几瓶可乐？

分析

假定g(n)表示给n元钱最多能喝的可乐数（即我们最终要求的值）；假定f(n)表示给定n个空瓶，能换得到的总可乐数。它们有如下关系：

$g(n)=f(n) + n$ ，说明：n块钱能买n瓶，另外产生n个空瓶又能得到f(n)瓶可乐。所以总共是f(n) + n

$f(n) = f(n/2 + n \% 2) + n/2$ ，说明：n个空瓶能换得n/2瓶，另外产生和剩于的n/2 + n%2个空瓶又能得到f(n/2 + n % 2)瓶可乐。所以总共是f(n/2 + n % 2) + n/2

有了递推公式之后，要实现就比较简单了。有递归和非递归两种方式：

非递归实现


xxxxxxxxxx
def calculate_drinks2(n):
    """
    给定n元钱，返回总共能喝到的可乐瓶数。
    """
    total = n
    empty = n
    while empty > 1:
        total += empty // 2
        empty = empty // 2 + empty % 2
    return total

递归实现


x
def calculate_drinks(n):
    """
    给定n元钱，返回总共能喝到的可乐瓶数。
    """
    def _calculate_by_bottle(m):
        """
        给定空瓶数量，返回总共能喝到的可乐瓶数。
        """
        if m == 2:
            return 1
        return _calculate_by_bottle(m // 2 + m % 2) + m // 2
    return n + _calculate_by_bottle(n)