h******o
发帖数: 200 | 1 借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，
n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意
一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输
出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左
岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回
去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。 | g****t
发帖数: 31659 | 2 去军版找高考状元，奥赛金牌，etc, 应能得到解决。
【在 h******o 的大作中提到】
: 借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，
: n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意
: 一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输
: 出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左
: 岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回
: 去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。
| w***g
发帖数: 5958 | 3 这是一个图搜索的问题。图节点(a,b,c)代表左岸有a只狼b只羊, c是现在船在左岸
还是右岸。起点是(m, n, 0)， 终点是(0, 0, 1)。要从图里面找出连接两点的
最短路径。找最短路径用的是宽度优先搜索。你需要在搜索的同时构造这个图。
我算是本版不要脸的了。因为你给出具体方案，就会出错。吹牛永远也不会出错，
还不用动脑子。
【在 h******o 的大作中提到】
: 借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，
: n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意
: 一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输
: 出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左
: 岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回
: 去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。
| f*******t
发帖数: 7549 | | l*******m
发帖数: 1096 | | g****t
发帖数: 31659 | 6 我原来叫股版股神公开与我建虚拟账户赌策略。
后来才明白过来，好多人都是弄粉丝群做生意的，就不去了。
【在 w***g 的大作中提到】
: 这是一个图搜索的问题。图节点(a,b,c)代表左岸有a只狼b只羊, c是现在船在左岸
: 还是右岸。起点是(m, n, 0)， 终点是(0, 0, 1)。要从图里面找出连接两点的
: 最短路径。找最短路径用的是宽度优先搜索。你需要在搜索的同时构造这个图。
: 我算是本版不要脸的了。因为你给出具体方案，就会出错。吹牛永远也不会出错，
: 还不用动脑子。
| l*******s
发帖数: 7316 | 7 n=m无解。
n=m+1 时,
1羊1狼去, 1狼回, (等价于送1只羊过去）
1羊1狼去, 1羊回, (等价于送1只狼过去）
重复直到完成。
n>m+1 时,
2羊去, 1羊回, (等价于送1只羊过去）
直到左岸的羊比狼多1只，然后按 n=m+1的方案解决。
【在 h******o 的大作中提到】
: 借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，
: n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意
: 一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输
: 出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左
: 岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回
: 去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。
| d***a
发帖数: 13752 | 8 楼主这个条件是不是给错了：在岸的任意一侧狼都不能多于羊。按这个条件，每个回合
送一羊一狼过去，空船回来，直到所有的狼送过去，然后再把剩下的羊两只一组送过去
。这样就太简单了。
【在 h******o 的大作中提到】
: 借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，
: n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意
: 一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输
: 出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左
: 岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回
: 去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。
| l*****c
发帖数: 1153 | 9 DP
【在 h******o 的大作中提到】
: 借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，
: n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意
: 一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输
: 出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左
: 岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回
: 去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。
| l*******s
发帖数: 7316 | 10 不能空船回来。
看我楼上的答案， 其实也很简单
【在 d***a 的大作中提到】
: 楼主这个条件是不是给错了：在岸的任意一侧狼都不能多于羊。按这个条件，每个回合
: 送一羊一狼过去，空船回来，直到所有的狼送过去，然后再把剩下的羊两只一组送过去
: 。这样就太简单了。
| k****i
发帖数: 101 | 11 # 每个来回运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
【在 h******o 的大作中提到】
: 借贵地请教一个弱智问题。上了一门课，有一个迷你项目要做。就是有n只羊，m只狼，
: n>=m。需要从河左岸运到右岸，每次船最多运两只，最少一只，来回都算。在岸的任意
: 一侧狼都不能多于羊。需要建一个函数，对于任意给的n和m，找出最优的运送方式，输
: 出一系列数对，给出每次船所运的羊和狼的数量。想了半天只想出第一次运送，即从左
: 岸运到右岸，根据所给出的初始值，有不同的方式。但接下去就头大了，船回来，再回
: 去...,用这种笨办法肯定没法做，但又不知道有什么好的算法。
| l*******s
发帖数: 7316 | 12 2(n+m)-1个单程。
【在 k****i 的大作中提到】
: # 每个来回运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
| d***a
发帖数: 13752 | 13 啊，谢谢。你的答案是对。
这道题是不是太简单了，限定了一个回合只能送一只动物，那送一只羊，送一只狼，如
此循环就可以了，就像你的解法说的。
【在 l*******s 的大作中提到】
: 不能空船回来。
: 看我楼上的答案， 其实也很简单
| n*********2
发帖数: 357 | 14 > n=m无解
当n=3, m=3的时候好像有解。 小孩给出了一个解，好像可行。
【在 l*******s 的大作中提到】
: n=m无解。
: n=m+1 时,
: 1羊1狼去, 1狼回, (等价于送1只羊过去）
: 1羊1狼去, 1羊回, (等价于送1只狼过去）
: 重复直到完成。
: n>m+1 时,
: 2羊去, 1羊回, (等价于送1只羊过去）
: 直到左岸的羊比狼多1只，然后按 n=m+1的方案解决。
| l*******s
发帖数: 7316 | 15 是的。m=n=3, 是很常见的智力题。
2狼去,1狼回,
2狼去,1狼回,
2羊去, 1羊1狼回,
2羊去, 1狼回,
2狼去,1狼回,
2狼去
【在 n*********2 的大作中提到】
: > n=m无解
: 当n=3, m=3的时候好像有解。 小孩给出了一个解，好像可行。
| d***a
发帖数: 13752 | 16 m=n时都有解吧，船上长时放一只狼就行了。
具体做法：
狼+羊去，狼回
狼+狼去，狼回
狼+羊去，狼回
狼+狼去，狼回
...
如此重复，最后一轮把两只动物都放下来。
【在 l*******s 的大作中提到】
: 是的。m=n=3, 是很常见的智力题。
: 2狼去,1狼回,
: 2狼去,1狼回,
: 2羊去, 1羊1狼回,
: 2羊去, 1狼回,
: 2狼去,1狼回,
: 2狼去
| l*******s
发帖数: 7316 | 17 这跟怎么理解船上的动物到岸时是否与岸上动物合计有关。
如果不合计, 可行。
否则m=n>3时, 无解
【在 d***a 的大作中提到】
: m=n时都有解吧，船上长时放一只狼就行了。
: 具体做法：
: 狼+羊去，狼回
: 狼+狼去，狼回
: 狼+羊去，狼回
: 狼+狼去，狼回
: ...
: 如此重复，最后一轮把两只动物都放下来。
|
|
