杯子倒水问题 -python

àì夳堔傛蜴生んèń 2022-03-08 04:22 247阅读 0赞

题目：假设有两个杯子A ,B，用户只需要输入两个杯子的容量值和需要获取的杯子数值left\_c。问两个杯子通过何种操作能获取到left\_c 的数值。

分析：此题目是求解优化的问题。采用bfs算法.

class State:
         def __init__(self,a,b,prev,step,operation):
              self.a=a
              self.b=b
              self.prev=prev
              self.step=step
              self.operation=operation
    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")
                            return new_state
        return None
    
    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()