摘要:但是由于不能使用作为,所以将表示状态的列表转换为后再用作的。上一篇将牌洗为逆序下一篇糖果恶作剧本系列总目录参见程序员的算法趣题详细分析和全解
目录
2.3 路径历史记忆以及判断邻节点是否在路径历史中
有A,B,C这三个大小各不相同的玻璃杯。从A杯装满水、B和C空杯的状态开始,不断地从一个杯子倒到其它杯子里去。假设不能使用任何辅助测量工具,且倒水时只能倒到这个杯子变为空,或者目标杯子变为满。重复这样的倒水操作,使A杯剩余水量是最初的一般。举个例子,如果A、B、C的初始容量分别为8、5、3,则可以通过以下操作序列使得A的水量变为4:(A to B), (B to C), (C to A), (B to C), (A to B), (B to C), (C to A)。读者可以自行手动演算验证。
在B和C的容量互质,且满足B+C=A,B>C的条件下,当A为10~100之间的偶数时,请问能使得“倒水操作后A杯水量减半”的A、B、C容量的组合有多少个?
图搜索问题,深度优先递归搜索(随口杜撰的名词大杂烩。。。做了一些题后一些概念开始在脑子里乱炖到一块儿了,后面要适时地总结整理夯实一下地基巩固一下训练成果)!本系列中有相当多题目都是这一个类型,用同样的套路就可以解决,后面有时间要回头来做一次总结。相比之下,原书还提供了另外一种更为精妙的解法,但是那个是只适用于当前题目的特定技巧,没有通用性。
图搜索问题的过程的关键就是构建搜索树,这一类问题的通用解题思路的要点:
通用很重要!灵光一现的解题技巧(可遇而不可求)就留给天才们去做好了。掌握了一个通用技巧,你可以确保碰到一个同类型的问题你有一个重型坦克般的保底的解决方案,虽然有时候不免显得笨拙,但是没有什么能拦得住!
本题节点状态很简单,就是当前三个杯子中的水量,用列表[a,b,c]表示即可。
邻节点搜索就是指搜索从当前状态/节点能够去往的下一个节点/状态,这些邻节点在搜索树中就对应着当前节点的子节点。所以这里邻节点和子节点是可以互换使用的等价概念。
但是邻节点要避免回到当前路径上已经到达过的节点,因为那样的话就形成了环路(loop),破坏了树的结构。如何防止形成环路参见下一节。
与单纯的深度优先搜索(for reachability judge only)不同的是,本类问题需要搜索所有可能的路径(呃。。。后来发现我误解了题目,主动提高了解题要求,不过油多不坏菜,就按‘误解’后的扩展版本来解吧,反正扩展版本包含了原题的答案),不同路径有可能共享一部分的节点或者甚至一部分edge。所以在搜索过程中需要记住当前搜索路径的历史,而不是一个全局的visited,因为只用于防止本路径形成环路。每条路径的搜索需要维护自己的路径历史。
在本题解中,用python dict来存储路径历史。但是由于python dict不能使用list作为key,所以将表示状态的列表[a,b,c]转换为tuple后再用作dict的key。那为什么不直接用tuple表示节点/状态呢?这是因为tuple的值不能修改,对于在处理过程需要更新状态值时不太方便。当然这些都不过是细枝末节。
在每次递归调用时,将当前节点/状态加入pathHistory,然后在退出本次递归调用时又将进入本次递归调用时加入的当前节点/状态清除掉。这相当于伴随着递归调用的隐式栈,并行地维护了一个显式的路径历史堆栈。我还没有想清楚这个是不是不可避免的,或许有什么办法可以回避掉。。。有时间再琢磨琢磨。
# -*- coding: utf-8 -*-"""Created on Wed Sep 1 07:34:21 2021@author: chenxy"""import sysimport timeimport datetimeimport math# import randomfrom typing import List# from queue import Queue# from collections import dequeclass Solution: def pourWaterGame(self, capacity:List) -> int: """ :A: The Capacity of cup A :B: The Capacity of cup B :C: The Capacity of cup C :ret: The total number of possibale combinations """ # capacity = (A,B,C) pathHistory = {} initState = [capacity[0],0,0] def pourWater(curstate, fromCup, toCup): """ pour warter from cup X to cup Y. Because curstate is pass-by-reference argument, to avoid it is modified, it should be firstly copied to newstate, and then update newstate. Because in the recursiion, the original "curstate" has its use after return from this call. """ newstate = curstate.copy() # instead of newstate = curstate! x = newstate[fromCup] y = newstate[toCup] Y = capacity[toCup] if x > 0 and y < Y: if x+y <= Y: x,y = 0,x+y else: x,y = x+y-Y,Y newstate[fromCup] = x newstate[toCup] = y return newstate def explore(pathHistory, curstate): # Judge whether reach the target state if curstate[0] == A/2: return 1 # Add curstate to pathHistory pathHistory[tuple(curstate)] = "" nums = 0 # A --> B newstate = pourWater(curstate, 0,1) if tuple(newstate) not in pathHistory: nums += explore(pathHistory,newstate) # A --> C newstate = pourWater(curstate, 0,2) if tuple(newstate) not in pathHistory: nums += explore(pathHistory,newstate) # B --> C newstate = pourWater(curstate, 1,2) if tuple(newstate) not in pathHistory: nums += explore(pathHistory,newstate) # B --> A newstate = pourWater(curstate, 1,0) if tuple(newstate) not in pathHistory: nums += explore(pathHistory,newstate) # C --> A newstate = pourWater(curstate, 2,0) if tuple(newstate) not in pathHistory: nums += explore(pathHistory,newstate) # C --> B newstate = pourWater(curstate, 2,1) if tuple(newstate) not in pathHistory: nums += explore(pathHistory,newstate) pathHistory.pop(tuple(curstate)) return nums return explore(pathHistory,initState)
if __name__ == "__main__": sln = Solution() numCombination = 0 for A in range(10,101,2): for C in range(1,A//2): # Because it is assumed that B>C B = A - C if math.gcd(B,C) == 1: tStart = time.time() ans = sln.pourWaterGame([A,B,C]) if ans > 0: numCombination += 1 tCost = time.time() - tStart print("[A,B,C]=[{0},{1},{2}], ans={3}, tCost = {4:6.3f}(sec)".format(A,B,C,ans,tCost)) print("numCombination={0}".format(numCombination))
......
[A,B,C]=[100,57,43], ans=199, tCost = 0.104(sec)
[A,B,C]=[100,53,47], ans=199, tCost = 0.097(sec)
[A,B,C]=[100,51,49], ans=199, tCost = 0.086(sec)
numCombination=514
如前所述,原题其实只要求求出有多少{A,B,C}组合能够使得“倒水操作后A杯水量减半”称为可能,因此对于每一种组合只要找出一条可行的路径即可。但是以上题解针对每一种{A,B,C}组合找出了所有可能的操作步骤(的种类数)。当然只要对以上程序稍作修改就可以变成针对每个{A,B,C}组合找到一种可行路径就退出。
另外,如果需要找出针对每种{A,B,C}组合所需要的最少步数,问题就转变成了图搜索之最短路径问题,这就需要用广度优先搜索(BFS)来解决了。后面有时间再回头来追加对应的题解,目前暂时留给各位小伙伴们做思考题。
另外,原书题解中提示了对于每种{A,B,C}组合所需要的最少操作次数为(A-1)。而另一方面,以上题解运行结果表明,对于每种{A,B,C}组合,可能的操作步骤数为(2*A-1)。这两者之间存在什么关联吗?留给各位小伙伴们一起思考。
上一篇:Q42: 将牌洗为逆序
下一篇:Q52: 糖果恶作剧
本系列总目录参见:程序员的算法趣题:详细分析和Python全解
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/118818.html
摘要:假设有几个小朋友以相同间隔围成圆周,要结对用纸杯电话相互通话。如果绳子交叉,很有可能会缠绕起来,所以结对的原则是不能让绳子交叉。如下所示运行结果上一篇异或杨辉三角形下一篇禁止右转本系列总目录参见程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问...
摘要:所幸,满足平方根前十位数字正好让的数字全部出现的数是存在的。上一篇斐波那契数列下一篇满足字母算式的解法本系列总目录参见程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问题描述 求在计算平方根的时候,最早让0~9的数字全部出现的最...
摘要:且听下回分解基于动态规划策略的优化解法参见程序员的算法趣题偷懒的算盘上一篇程序员的算法趣题同数包夹程序员的算法趣题同数包夹本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 ...
摘要:可以在遍历所有矩阵时,对各种出现的次数进行计数,最后计数值为的个数即为所求结果。上一篇排序交换次数的最少化排序交换次数的最少化本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 ...
阅读 2806·2021-09-10 10:51
阅读 2176·2021-09-02 15:21
阅读 3153·2019-08-30 15:44
阅读 797·2019-08-29 18:34
阅读 1619·2019-08-29 13:15
阅读 3260·2019-08-26 11:37
阅读 2656·2019-08-26 10:46
阅读 1054·2019-08-26 10:26