一.问题描述与实验要求
给你两瓶装满了油的油瓶 A 和 B，其容量分别是 5 升和 3 升，再给你一个容
量很大（至少 8 升）的空油瓶 C，三个油瓶均没有刻度。现在想量出 x 升的油
（x=1,2,3,4,5,6,7,8），该怎么倒油？试用回溯策略求解，给出一个合适的倒
油操作序列。
二.符号说明与语法约定
为了不失一般性，代码能够对给定的三个瓶子容量上限（A、B、C）和一个
倒出的油目标值 target，以及初始油量 A0,B0,C0，即可求得结果。
三.算法自然语言描述
回溯法求解
对于每个状态（三个瓶子目前油量）均有 6 种倒法，为了得到回溯的条件，我
们记录之前已经存在的所有状态，那么回溯的条件是之前存在当前的状态或者
目前的状态中存在一个油量为 target 的瓶子。
对于每个状态我们均用 6 种倒法进行操作，直到和之前状态相同或者得到结
果。
四. 算法伪代码描述
输入：空
输出：得到目标油量的步骤
主要算法
getAns(index) //index 为目前的状态为第 index 步
1. for i<- 1 to 6
2. step[index][3]=i; //step[i][j]代表第 i 个状态
j=0/1/2 代表瓶子油量 j=4 代表下一步的操作
3. move(index+1) //进行倒油
4. if index+1 状态存在 target then
5. ++cnt; //cnt 为目前求得的有多少结果
6. 打印输出并记录 //记录是为了找到最少步骤的解
7. else if 之前不存在当前状态 then
8. getAns(index+1) //进行下一步 否则回溯
9. end if
10. end for
评论0