8升满壶5升3升空壶倒出4升水

面试经典 Finley Fu 2020-02-15 3评论 409
给一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶,想个办法,使得其中一个水壶恰好装 4 升水,每一步的操作只能是倒空或倒满。

   思路  

        1、使用广度遍历,把三个水壶里的水量标为数字,例如初始状态为800

        2、在每个状态下枚举下一步操作可能出现的状态,例如一次操作可能出现350、503,并且不可做上一次操作,即不可还原为父状态

        3、当某个状态在之前出现过,则该状态不可用,后续不需要再操作

   过程图  

解题过程图

   结果  

由图可得到两种方案

        方案一(最优):800-350-323-620-602-152-143

        方案二(略差):800-503-530-233-251-701-710-412