人狼羊草问题
2019-03-30 本文已影响0人
EBcoco
1.题目：
一农夫带着一头狼，一只羊和一担草过河，小船只能一次装载农夫和一样货物，狼会吃羊，羊会吃草，只有农夫在时才安全。现欲让所有物品包括农夫都安全过道河对岸，使用程序实现求解。
2.设计思路：
使用布尔列表来设置人狼羊草的状态, false代表不过河,true 代表渡河
那么人狼羊草的初始状态就是 status = [ false , false , false , false ]
最后状态应该是 status = [ true , true , true , true ]
渡河规则:
1.每次渡河农夫的状态都必须改变
2.每次渡河, 狼 羊 草的状态最多改变一位
3.狼 羊 草 存在食物链克制情况下必须有农夫存在
根据规则以初始状态为根节点,生成后续状态,再做枚举,生成状态树
如果子节点出现与根节点相同的状态,则不再生成子树
编码流程:
1,创建状态历史列表
2.生成所有方案
3.遍历判断所生成方案,判断是否是最终状态,是则输出
4.不是则判断改状态是否存在于状态历史列表
5.是则回到 3 ,继续遍历,不是则存入状态历史列表,回到 2 继续执行
(ps.算法流程图就不画了,凑活看,有人画可以发给我)
代码:
status = [False, False, False, False]
# 人 狼 羊 草
判断状态是否合规
def judge_status(status):
if status[1] == status[2]:
if status[0] != status[1]:
# 狼和羊同侧，没有人在场
return False
if status[2] == status[3]:
if status[0] != status[2]:
# 羊和草同侧，没有人在场
return False
return True
创建子树所有状态,也就是下一步农夫行为
def create_all_next_status(status):
next_status_list = []
for i in range(0, 4):
if status[0] != status[i]: # 和农夫不同一侧？
continue
next_status = [status[0],status[1],status[2],status[3]]
# 农夫和其中一个过河，i 为 0 时候，农夫自己过河。
next_status[0] = not next_status[0]
next_status[i] = next_status[0] # 和农夫一起过河
if judge_status(next_status):
next_status_list.append(next_status)
return next_status_list
树形递归遍历
def search(history_status):
global scheme_count
current_status = history_status[len(history_status) - 1]
next_status_list = create_all_next_status(current_status)
for next_status in next_status_list:
if next_status in history_status:
# 出现重复的情况了
continue
history_status.append(next_status)
if is_done(next_status):
scheme_count += 1
print("scheme " + str(scheme_count) + ":")
print_history_status(history_status)
else:
search(history_status)
history_status.pop()
# 这里是找到满足方案后,将其弹出历史状态列表,继续查找下一个方案
判断是否达到最终状态,都过河,则返回Ture
def well_done(status):
return status[0] and status[1] and status[2] and status[3]
最后可以写个方法处理一下列表,打印出过程
