Python3多思路解决空瓶换酒问题

思路导航


前言

  空瓶换酒是一类很经典的智力趣题,也有很多不同的问题版本。本文旨在小结其解决方法,以加深理解。
  空瓶换酒的目标是求解最终能喝多少瓶酒?问题的版本有很多种:共有x元,y元一瓶酒,初始有x/y瓶酒,m个酒瓶可以换一瓶酒,n个瓶盖可以换一瓶酒。其还分为不可赊账和可赊账,此处讨论的是不可赊账版本,x/y取为num,m取2,n取4.(可赊账类转换为函数求解问题)


一、一行代码

此类思路的解法也有几种,最简单的思路便是总结规律,手动推导前几次便可发现其规律。

num sum bottle lid
1 1 1 1
2 3 1 3
3 7 1 3
4 11 1 3

故可发现在num>1时:

sum = 4*num-5 if num>1 else 1

故可直接求解出相应答案,还可以利用动态规划的思想进行公式推导(最终结果同)。


二、迭代求解

代码如下(思路见注释):

# 空瓶换酒问题
""" wine:当前酒数量 bottle瓶子数 lid:瓶盖数 """
num = eval(input())
# 非递归思路
wine = num
bottle = 0
lid = 0
sum = 0
while True:
    if wine==0 and bottle//2==0 and lid//4==0:  #终止条件
        break
    elif wine!=0:     #消耗酒
        bottle+=wine
        lid+=wine
        sum+=wine
        wine=0
    elif bottle//2!=0:  #瓶子换酒
        bot_num = bottle//2
        wine+=bot_num
        bottle=bottle%2
    else:
        lid_num = lid//4   #瓶盖换酒
        wine += lid_num
        lid = lid%4
print(sum)

思路很简单,即迭代求解最终的喝酒数量,迭代的终止条件:当前可饮酒数为0且瓶子数和瓶盖数不支持换新酒。喝酒增加对应的瓶子数和瓶盖数,兑酒消耗对应瓶子数和瓶盖数。


三、递归求解

递归的思路相同,只不过换了种实现方式:

# 递归思路
num = int(input())
def for_wine(sum,wine,bottle,lid):
    if wine==0 and bottle//2 ==0 and lid//4 ==0:  #终止条件
        return sum
    elif wine!=0:   #消耗酒
        sum+=wine
        return for_wine(sum,0,bottle+wine,lid+wine)
    elif bottle //2!=0:  #瓶兑酒
        wine+=bottle//2
        return for_wine(sum,wine,bottle%2,lid)
    else:
        wine+=lid//4    #瓶盖兑酒
        return for_wine(sum,wine,bottle,lid%4)

print(for_wine(0,num,0,0))


总结

  以上就是本文的主要内容,本文简要地介绍了空瓶换酒问题,并引出了三种解决思路,并且以python语言模拟实现其求解过程,其他编程语言的实现类似。
  本文的实现可能还存在可以优化的地方,其主要目的是梳理相关解题思路,如有帮助,请点赞支持一下ヽ( ̄▽ ̄)ノ

上一篇:数组


下一篇:Codeforces Round #772 (Div. 2) A - E