「青蛙過河」之我見

「青蛙過河」是一個有趣的遊戲：河中有7個石墩橫向排放（圖中的方形格子），有3隻紅色小青蛙面朝右呆在左邊的3石墩上，有3隻藍色小青蛙面朝左呆在右邊的3石墩上。

遊戲的目標是讓兩隊青蛙互換位置，而臉的朝向不變。

遊戲的規則是：每隻小青蛙只能向前走1步到相鄰的空石墩上（下圖上），或者跳過前方1個異色的青蛙到異色青蛙背後的空石墩上（下圖下）；青蛙不能向後退，不能隔兩個或者更多跳躍。

（以下圖中實線表示移動，虛線表示跳躍，方格上方箭頭表示左方紅色小青蛙動作，方格下方箭頭表示右方藍色小青蛙動作）

先來分析總的移動步數：

根據規則易知同色青蛙不能彼此超越，因此紅色小青蛙到右端後先後次序不改，藍色小青蛙亦然（如圖左所示）。每隻小青蛙都要向前移動4格（紅色3號小青蛙情況參看圖右）。

因此所有6隻小青蛙的總的移動格數是 ，其中每次移動前進一格、跳躍前進兩格。用 表示移動的總次數、 表示跳躍的總次數，則有 。

注意到每一次跳躍都導致1隻紅色小青蛙和1隻藍色小青蛙之間左右次序的對換（圖4(a)到(b)）。而3隻紅色小青蛙和3隻藍色小青蛙交換位置一共需要9次左右次序的對換，因此 ，及 。

推廣到左右各有 只小青蛙的情況：總的移動格數是 ， ， 。

下面給出求解左右各有 只小青蛙的「青蛙過河」問題的具體方法：

考慮如下圖的 行，每行字元交錯使用「R」和「B」，即得到一個解決方案。（事實上，每一個時刻指定顏色後可以行動的青蛙只有一隻，因此在圖5中不必特意區分是移動前進一格還是跳躍前進兩格。）

例如： 的情況——

的情況，序列是R/BB/RR/BB/R，具體過程為——

的情況，序列是R/BB/RRR/BBB/RRR/BB/R，具體過程為——

最後，給出 情況下各序列中是移動前進一格還是跳躍前進兩格的區分如下圖所示，其中大寫字元表示跳躍，小寫字元表示移動。

可以總結規律性——此部分內容留給讀者（可以參考下圖）。

並可以給出遞推的構造演算法——此部分內容留給讀者（可以參考下圖）。

最後的備註：

本文的規則和原來的遊戲相比，增加了一個要求——「不能跳過前方1個同色的青蛙到同色青蛙背後的空石墩上」。增加這個要求主要是為了論述的簡潔，而事實上，這種情況在一個解法中是不可能出現的：

1. 如果跳躍後「前方」還有異色的青蛙（不一定緊挨著），那麼它將之後再也無法「翻越」這兩隻同色青蛙（如下圖左）。
2. 如果跳躍後「前方」沒有異色的青蛙（如下圖右），那麼事實上根本不可能出現這種情況——只要考慮同色青蛙前面的空格如何產生即可。