【智力题】养羊人,养兔人,猎人渡河问题

tech2022-08-28  96

题目描述:一个养羊人养两只羊 ,一个养兔人养两只兔 ,一个猎人养一只猎狗 ,一条船,一条河,船一次可以载两个生物,必须有人划船。养羊人会在养兔人不在的情况下会杀兔子,养兔人会在养羊人不在的时候杀羊,猎狗会在猎人不在的时候杀所有生物。问渡河方式?

牵制关系: 猎人+猎狗必须在同一边 或者人狗不在同一处时狗所在处无其他生物 养兔人+羊在同一边时,养羊人也在此处 养羊人+兔在同一边时,养兔人也在此处

解题步骤: 1.猎人+猎狗渡河 猎人开船返回 猎狗留在对岸 此时已渡河有:猎狗 目的:让猎狗独处 2.猎人+羊1渡河 猎人+猎狗开船返回 羊1留在对岸 此时已渡河有:羊1 目的:运输羊1 3.养羊人+羊2渡河 养羊人开船返回 羊2留在对岸 此时已渡河有:羊1+羊2 目的:运输羊2 4.养羊人+养兔人渡河 养兔人开船返回 养羊人留在对岸 此时已渡河有:羊1+羊2+养羊人 此时剩下需要渡河的人的数目为2 目的:运输养羊人,并且为开船返回者提供更多选择 5.猎人+猎狗渡河 养羊人开船返回 猎人+猎狗留在对岸 此时已渡河有:羊1+羊2+猎人+猎狗 目的:约束猎狗+置换驾船人 6.养羊人+养兔人渡河 养兔人开船返回 养羊人留在对岸 此时已渡河有:羊1+羊2+猎人+猎狗+养羊人 目的:减少需要渡河的人数 需要渡河人数为1 7.养兔人+兔1渡河 猎人+猎狗开船返回 养兔人+兔1留在对岸 此时已渡河有:羊1+羊2+养羊人+养兔人+兔1 目的:渡兔1+渡船人置换+维持约束条件 8.猎人+兔2渡河 猎人开船返回 兔2留在对岸 此时已渡河有:羊1+羊2+养羊人+养兔人+兔1+兔2 目的:渡兔2+隔离猎狗 9.猎人+猎狗渡河 渡河完毕 猎人+猎狗留在对岸 此时已渡河有:羊1+羊2+养羊人+养兔人+兔1+兔2+猎人+猎狗 目的:完成运输

最新回复(0)