You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
75 lines
2.1 KiB
75 lines
2.1 KiB
# 等分液体
|
|
# 在一个瓶子中装有8(一般情形下为偶数N)升汽油,要平均分成两份,
|
|
# 但只有一个装3(一般情形下为N/2-1)升和装5(一般情形下为N/2+1)升的量杯(都没有刻度)。
|
|
# 若有解,则打印出所有把汽油分成两等分的操作过程。若无解,则打印“No”。
|
|
|
|
from collections import deque
|
|
|
|
|
|
def pour(source, target, target_capacity):
|
|
amount = min(source, target_capacity - target)
|
|
return source - amount, target + amount
|
|
|
|
|
|
def get_next_states(state, capacities):
|
|
next_states = []
|
|
bottle, cup3, cup5 = state
|
|
max_bottle, max_cup3, max_cup5 = capacities
|
|
|
|
# bottle -> cup3
|
|
next_states.append(pour(bottle, cup3, max_cup3) + (cup5,))
|
|
# bottle -> cup5
|
|
next_states.append(pour(bottle, cup5, max_cup5) + (cup3,))
|
|
# cup3 -> bottle
|
|
next_states.append(
|
|
(pour(cup3, bottle, max_bottle)[1],) + pour(cup3, bottle, max_bottle)
|
|
)
|
|
# cup5 -> bottle
|
|
next_states.append(
|
|
(pour(cup5, bottle, max_bottle)[1], cup3, pour(cup5, bottle, max_bottle)[0])
|
|
)
|
|
# cup3 -> cup5
|
|
next_states.append((bottle,) + pour(cup3, cup5, max_cup5))
|
|
# cup5 -> cup3
|
|
next_states.append((bottle,) + pour(cup5, cup3, max_cup3)[::-1])
|
|
|
|
return next_states
|
|
|
|
|
|
def bfs(initial_state, capacities, target):
|
|
queue = deque([(initial_state, [])])
|
|
visited = set()
|
|
|
|
while queue:
|
|
(state, path) = queue.popleft()
|
|
|
|
if (state[0] == target and state[1] == target) or (
|
|
state[0] == target and state[2] == target
|
|
):
|
|
return path
|
|
|
|
if state in visited:
|
|
continue
|
|
|
|
visited.add(state)
|
|
|
|
for next_state in get_next_states(state, capacities):
|
|
if next_state not in visited:
|
|
queue.append((next_state, path + [next_state]))
|
|
|
|
return "No"
|
|
|
|
|
|
N = 8
|
|
capacities = (N, N // 2 - 1, N // 2 + 1)
|
|
initial_state = (N, 0, 0)
|
|
target = N // 2
|
|
|
|
result = bfs(initial_state, capacities, target)
|
|
|
|
if result == "No":
|
|
print("No")
|
|
else:
|
|
print("状态步骤:(汽油瓶, 5L杯, 3L杯)")
|
|
for step in result:
|
|
print(step)
|
|
|