博客

问题描述

给你两个容器A和B，A的容量是3，B的容量是5。现在拿一个水壶可以向任意容器倒水，两个容器相互间也可以倒水，问经过多少步骤，可以使得B中盛有4升水？

解题思路

Initial State :

(0,0)


Oprations(算符)：

1. 将杯子A的水倒空
2. 将杯子B的水倒空
3. 将杯子A装满水
4. 将杯子B装满水
5. 将杯子A的水倒入B，直至A的水被倒空
6. 将杯子A的水倒入B，直至B被倒满
7. 将杯子B的水倒入A，直至B的水被倒空
8. 将杯子B的水倒入A，直至A被倒满

Goal State:

(*,4)

代码演示

class State:
    def __init__(self,a,b,prev,step,operation):
        self.a=a   #A现有水量
        self.b=b   #B现`在这里插入代码片`有水量
        self.prev=prev   #父节点指针
        self.step=step   #已扩充的节点数
        self.operation=operation
#存储已访问的节点，防止重复。首先默认各个位置均为False，访问后置为T        
visited=[[False for i in range(100)]for j in range(100)]  
def bfs(capativy_a,capativy_b,left_c):
    queue=[]
    s=State(a=0,b=0,prev=None,step=0,operation=None)
    queue.append(s)
    visited[0][0]=True
    while queue:
        state=queue.pop(0)
        for i in range(6):
            a ,b ,operation =None,None,None
            if i==0:
                operation =" 将杯子A的水倒空"
                a=0
                b=state.b
            elif i==1:
                operation = " 将杯子B的水倒空"
                a=state.a
                b=0
            elif i==2:
                operation = " 将杯子A的水倒满"
                a=capativy_a
                b=state.b
            elif i==3:
                operation = " 将杯子B的水倒满"
                b=capativy_b
                a=state.a
            elif i==4:
                #将杯子A的水倒入杯子B中
                if capativy_b-state.b>state.a:
                    operation="将杯子A的水倒入杯子B，直至杯子A被倒空"
                    a=0
                    b=state.a+state.b
                else :
                    operation="将杯子A的水倒入杯子B，直至杯子B被倒满"
                    b=capativy_b
                    a=state.a-(capativy_b-state.b)
            elif i==5:
                #将杯子B的水倒入杯子A中
                if capativy_a-state.a>state.b:
                    operation=" 杯子B中的水倒入杯子A中，直至杯子B被倒空"
                    b=0
                    a=state.a+state.b
                else:
                    operation="杯子B中的水倒入杯子A中，直至杯子A被倒满"
                    a=capativy_a
                    b=state.b-(capativy_a-state.a)
            if  not visited[a][b]:
                new_state=State(a=a,b=b,prev=state,step=state.step+1,operation=operation)
                visited[a][b]=True
                queue.append(new_state)
                if left_c==a or left_c==b:
                    print("yes！我可以找到解决办法")
                    print("需要步数是：",new_state.step)
                    return new_state
    return None
'''
    [ 1 2 3 4 5 ]
     
    print(a[-1]) ###取最后一个元素
    [5]
     
    print(a[:-1])  ### 除了最后一个取全部
    [ 1 2 3 4 ]
     
    print(a[::-1]) ### 取从后向前（相反）的元素
    [ 5 4 3 2 1 ]
     
    print(a[2::-1]) ### 取从下标为2的元素翻转读取
    [ 3 2 1 ]
'''
def get_path(state):
    path=[]
    while state.prev:
        path.append(state.operation)
        state  = state.prev
    return path[::-1]

def main():
    capativy_a= int(input("please input the  A:"))
    capativy_b= int(input("pleasr input the  B:"))
    left_c    = int(input("please input the left_c:"))
    result    = bfs(capativy_a,capativy_b,left_c)
    if not  result:
        print("error")
    else :
        p=get_path(result)
        print(p)
main()