523066680

记得《算法谜题》里面有这两道。
最近看到题目就绕道，学得太少，加上脑袋也僵化了，空想太耗时（逃

523066680

回复 6# 老刘1号


    上一道我一看就蒙，人是一定要在船上的吗？光这个就开始纠结了，算了还是不去纠结了 —— 放弃。

523066680

回复 10# 老刘1号
《算法谜题》英文版
http://booksdescr.org/item/index ... E970CD2C9C83A605B6E
第42道，有些相似的地方，不过这个更像是单纯的排列，不考虑两岸的问题。
42. The Other Wolf-Goat-Cabbage Puzzle
You have 4n counters of four types: n wolfs, n goats, n cabbages, and
n hunters. The object is to place the counters in a row such that no one is in
danger; that is, no hunter is next to a wolf, no wolf is next to a goat, and no
goat is next to a cabbage. In addition, no two counters of the same kind may
be next to each other either. How many ways are there to solve the puzzle?

解位于 116 页
Solution Let W, G, C, and H represent a wolf, a goat, a cabbage, and a hunter,
respectively. Then the puzzle has two symmetric solutions:
WCWC. . . WCHGHG . . . HG and GHGH . . . GHCWCW . . . CW.

令狼羊菜猎人分别为 W G C H，他们的数量一样（n），则该问题有两种对称解
WCWC. . . WC+HGHG . . . HG  和 GHGH . . . GH+CWCW . . . CW

当 n = 1 的时候，元素较少，很容易推算出两种结果： WCHG 和 GHCW，当N=2的时候，在1的基础上叠加：
WCWCHGHG 和 GHGHCWCW，以此类推。
（中间还有一段证明请看原PDF）

Comments: The solution to the puzzle can be considered based on decrease-andconquer
applied bottom up: the solution is obtained by solving smaller instances of
the same puzzle first and then extending their solutions to form the same patterns.
注：此问题可以采用减而治之的方案，将问题简化为最简版本（n=1），然后数量更多的问题的解可以从基础版本的答案中扩展得到。

523066680

回复 12# 老刘1号

评论摘选：
     农夫山泉有点甜！