问个弱智的算法问题-狼和羊

借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。

去军版找高考状元，奥赛金牌，etc, 应能得到解决。
【 在 henrygao (henry) 的大作中提到: 】
: 借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，
: n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意
: 一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输
: 出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左
: 岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回
: 去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。

这是一个图搜索的问题。图节点(a,b,c)代表左岸有a只狼b只羊, c是现在船在左岸
还是右岸。起点是(m, n, 0)，　终点是(0, 0, 1)。要从图里面找出连接两点的
最短路径。找最短路径用的是宽度优先搜索。你需要在搜索的同时构造这个图。

我算是本版不要脸的了。因为你给出具体方案，就会出错。吹牛永远也不会出错，
还不用动脑子。

【 在 henrygao (henry) 的大作中提到: 】
: 借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，
: n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意
: 一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输
: 出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左
: 岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回
: 去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。

这个貌似是小学奥数题

https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem

【 在 fantasist (一) 的大作中提到: 】
: 这个貌似是小学奥数题

我原来叫股版股神公开与我建虚拟账户赌策略。
后来才明白过来，好多人都是弄粉丝群做生意的，就不去了。
【 在 wdong (万事休) 的大作中提到: 】
: 这是一个图搜索的问题。图节点(a,b,c)代表左岸有a只狼b只羊, c是现在船在左岸
: 还是右岸。起点是(m, n, 0)，　终点是(0, 0, 1)。要从图里面找出连接两点的
: 最短路径。找最短路径用的是宽度优先搜索。你需要在搜索的同时构造这个图。
: 我算是本版不要脸的了。因为你给出具体方案，就会出错。吹牛永远也不会出错，
: 还不用动脑子。

n=m>3无解。
n=m+1 时,
1羊1狼去, 1狼回, (等价于送1只羊过去）
1羊1狼去, 1羊回, (等价于送1只狼过去）
重复直到完成。
n>m+1 时,
2羊去, 1羊回, (等价于送1只羊过去）
直到左岸的羊比狼多1只，然后按 n=m+1的方案解决。

【 在 henrygao (henry) 的大作中提到: 】
: 借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，
: n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意
: 一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输
: 出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左
: 岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回
: 去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。

楼主这个条件是不是给错了：在岸的任意一侧狼都不能多于羊。按这个条件，每个回合送一羊一狼过去，空船回来，直到所有的狼送过去，然后再把剩下的羊两只一组送过去。这样就太简单了。

【 在 henrygao (henry) 的大作中提到: 】
: 借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，
: n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意
: 一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输
: 出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左
: 岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回
: 去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。

DP

【 在 henrygao (henry) 的大作中提到: 】
: 借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，
: n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意
: 一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输
: 出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左
: 岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回
: 去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。

不能空船回来。
看我楼上的答案， 其实也很简单
【 在 digua (姚之FAN) 的大作中提到: 】
: 楼主这个条件是不是给错了：在岸的任意一侧狼都不能多于羊。按这个条件，每个回合
: 送一羊一狼过去，空船回来，直到所有的狼送过去，然后再把剩下的羊两只一组送过去
: 。这样就太简单了。

# 每个来回运2返1，最骚运m加n次

def wolf_goat(m, n):
A = []
while n:
wo, go_ret = m > 0, m == n
A.append((wo, True, wo and not go_ret, go_ret))
m -= go_ret
n -= not go_ret
return A

【 在 henrygao (henry) 的大作中提到: 】
: 借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，
: n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意
: 一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输
: 出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左
: 岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回
: 去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。

2(n+m)-1个单程。
【 在 kkkuai (sknow) 的大作中提到: 】
: # 每个来回运2返1，最骚运m加n次
: def wolf_goat(m, n):
: A = []
: while n:
: wo, go_ret = m > 0, m == n
: A.append((wo, True, wo and not go_ret, go_ret))
: m -= go_ret
: n -= not go_ret
: return A

啊，谢谢。你的答案是对。

这道题是不是太简单了，限定了一个回合只能送一只动物，那送一只羊，送一只狼，如此循环就可以了，就像你的解法说的。

【 在 llaalways (熊大) 的大作中提到: 】
: 不能空船回来。
: 看我楼上的答案， 其实也很简单

> n=m无解

当n=3, m=3的时候好像有解。 小孩给出了一个解，好像可行。

【 在 llaalways (熊大) 的大作中提到: 】
: n=m无解。
: n=m+1 时,
: 1羊1狼去, 1狼回, (等价于送1只羊过去）
: 1羊1狼去, 1羊回, (等价于送1只狼过去）
: 重复直到完成。
: n>m+1 时,
: 2羊去, 1羊回, (等价于送1只羊过去）
: 直到左岸的羊比狼多1只，然后按 n=m+1的方案解决。

是的。m=n=3, 是很常见的智力题。
2狼去,1狼回,
2狼去,1狼回,
2羊去, 1羊1狼回,
2羊去, 1狼回,
2狼去,1狼回,
2狼去

【 在 nowwhat2012 (Judgment 燿ay) 的大作中提到: 】
: > n=m无解
:
: 当n=3, m=3的时候好像有解。 小孩给出了一个解，好像可行。
:
: 【 在 llaalways (熊大) 的大作中提到: 】
: : n=m无解。
: : n=m+1 时,
: : 1羊1狼去, 1狼回, (等价于送1只羊过去）
: : 1羊1狼去, 1羊回, (等价于送1只狼过去）
: : 重复直到完成。
: : n>m+1 时,
: : 2羊去, 1羊回, (等价于送1只羊过去）
: : 直到左岸的羊比狼多1只，然后按 n=m+1的方案解决。

m=n时都有解吧，船上长时放一只狼就行了。

具体做法：
狼+羊去，狼回
狼+狼去，狼回
狼+羊去，狼回
狼+狼去，狼回
...
如此重复，最后一轮把两只动物都放下来。

【 在 llaalways (熊大) 的大作中提到: 】
: 是的。m=n=3, 是很常见的智力题。
: 2狼去,1狼回,
: 2狼去,1狼回,
: 2羊去, 1羊1狼回,
: 2羊去, 1狼回,
: 2狼去,1狼回,
: 2狼去

这跟怎么理解船上的动物到岸时是否与岸上动物合计有关。
如果不合计, 可行。
否则m=n>3时, 无解

【 在 digua (姚之FAN) 的大作中提到: 】
: m=n时都有解吧，船上长时放一只狼就行了。
:
: 具体做法：
: 狼+羊去，狼回
: 狼+狼去，狼回
: 狼+羊去，狼回
: 狼+狼去，狼回
: ...
: 如此重复，最后一轮把两只动物都放下来。
:
: 【 在 llaalways (熊大) 的大作中提到: 】
: : 是的。m=n=3, 是很常见的智力题。
: : 2狼去,1狼回,
: : 2狼去,1狼回,
: : 2羊去, 1羊1狼回,
: : 2羊去, 1狼回,
: : 2狼去,1狼回,
: : 2狼去