小孩分油問(wèn)題

題目：

兩個(gè)小孩去打油齿尽，一個(gè)人帶了一個(gè)一斤的空瓶沽损，另一個(gè)帶了一個(gè)七兩、一個(gè)三兩的空瓶循头。原計(jì)劃各打一斤油绵估，可是由于所帶的錢(qián)不夠，只好兩人合打了一斤油卡骂，在回家的路上国裳，兩人想平分這一斤油，可是又沒(méi)有其它工具全跨，試僅用三個(gè)瓶子（一斤缝左、七兩、三兩）精確地分成兩個(gè)半斤油來(lái)浓若。

算法設(shè)計(jì)：

設(shè)置三個(gè)油瓶分別為A, B, C渺杉，初始化三個(gè)油瓶的初始狀態(tài)(10,0,0)，滿(mǎn)油狀態(tài)(10,7,3)挪钓，目標(biāo)狀態(tài)(5,5,0)是越。使用廣度優(yōu)先的搜索方法，對(duì)每一種可能情況進(jìn)行遍歷碌上，最終取得結(jié)果倚评。其中浦徊，對(duì)于每一種情況對(duì)應(yīng)每一步操作，操作需要滿(mǎn)足一定的約束條件：把A瓶中的油全部倒入B瓶或者把A瓶中的油部分倒入B瓶使B瓶滿(mǎn)油天梧。具體的約束條件見(jiàn)程序流程盔性。本算法由python實(shí)現(xiàn)。

程序流程：

1.png

1.png

核心偽代碼：

Def 下一步：
下一個(gè)操作 = [
        (倒出瓶標(biāo)簽, 倒入瓶標(biāo)簽)
        for 倒出瓶標(biāo)簽 range(3) for 倒入瓶標(biāo)簽 in range(3)
if 倒入/出瓶標(biāo)簽不能相同 and 倒出的瓶不為空 and 已經(jīng)滿(mǎn)了的瓶不能再倒入    ]

    for 倒出瓶標(biāo)簽, 倒入瓶標(biāo)簽 in 下一步操作:
        if 倒出倒入瓶由量之后不超過(guò)倒入瓶最大容量
            倒出瓶油量 -= (倒入瓶最大容量-倒入瓶現(xiàn)有油量)
            倒入瓶油量 = 倒入瓶最大容量
        else:
            倒出瓶油量 = 0
            倒入瓶油量 = 倒入瓶現(xiàn)有油量 + 倒出瓶現(xiàn)有油量
        yield 下一步

Def 搜索結(jié)果:
for 操作in 下一步:
        if 沒(méi)有試過(guò)該操作:
            將該操作加入隊(duì)列
            if 當(dāng)前結(jié)果== 目標(biāo)結(jié)果:
              輸出結(jié)果
            else:
                遞歸本函數(shù)‘搜索結(jié)果’
            刪除隊(duì)列最后一個(gè)

代碼運(yùn)行及測(cè)試：

·.png

結(jié)論：

由代碼運(yùn)行結(jié)果可知：整棵樹(shù)一共有20種方法能夠達(dá)到要求腿倚，其中最佳即路徑最短的方法為第9種方法纯出。

第9種方法:[10, 0, 0]->[3, 7, 0]->[3, 4, 3]->[6, 4, 0]->[6, 1, 3]->[9, 1, 0]->[9, 0, 1]->[2, 7, 1]->[2, 5, 3]->[5, 5, 0]

具體做法為：

? 0) 初始化-->[10, 0, 0]
? 1) A瓶倒?jié)MB瓶-->[3, 7, 0]
? 2) B瓶倒?jié)MC瓶-->[3, 4, 3]
? 3) C瓶倒?jié)MA瓶-->[6, 4, 0]
? 4) B瓶倒?jié)MC瓶-->[6, 1, 3]
? 5) C瓶倒?jié)MA瓶-->[9, 1, 0]
? 6) B瓶倒?jié)MC瓶-->[9, 0, 1]
? 7) A瓶倒?jié)MB瓶-->[2, 7, 1]
? 8) B瓶倒?jié)MC瓶-->[2, 5, 3]
? 9) C瓶倒?jié)MA瓶-->[5, 5, 0]

源代碼：

'''
@author: 嘿芝麻

@software: garner
@file: main_oil.py
@time: 2018/10/5
'''
from collections import deque

def nextStep(current_state, oil_volume):
    next_action = [
        (from_, to_)
        for from_ in range(3) for to_ in range(3)
        if from_ != to_ and current_state[from_] > 0 and current_state[to_] < oil_volume[to_]
    ]

    for from_, to_ in next_action:
        next_state = list(current_state)
        if current_state[from_] + current_state[to_] > oil_volume[to_]:
            next_state[from_] -= (oil_volume[to_] - current_state[to_])
            next_state[to_] = oil_volume[to_]
        else:
            next_state[from_] = 0
            next_state[to_] = current_state[to_] + current_state[from_]
        yield next_state


def searchResult(record, oil_volume=[10, 7, 3], final_state=[5, 5, 0]):
    global num, record_list
    current_state = record[-1]
    next_stage = nextStep(current_state, oil_volume)

    for stage in next_stage:
        if stage not in record:
            record.append(stage)
            if stage == final_state:
                numm = num + 1
                s_numm = str(numm)
                str_record = ''
                for i in record:
                    str_record += str(i)
                    if i != [5, 5, 0]:
                        str_record += '->'
                print("方法{}:{}".format(s_numm, str_record))
                record_list.append(deque(record))
                num += 1
            else:
                searchResult(record, oil_volume, final_state)
            record.pop()


if __name__ == '__main__':
    initial_oil_state = [10, 0, 0]
    oil_volume = [10, 7, 3]
    num = 0
    record_list = []
    record = deque()
    record.append(initial_oil_state)
    searchResult(record)
    number = "廣度優(yōu)先搜索共有{}種方法".format(num)
    shortest = "路徑最短的方法中操作步總數(shù)為{}".format(min([len(i) for i in record_list]))

    print(number)
    print(shortest)