本文为joshua317原创文章,转载请注明：转载自joshua317博客 算法-经典趣题-青蛙过河 - joshua317的博客

一、问题

青蛙过河是一个非常有趣的智力游戏，其大意如下：

一条河之间有若干石块间隔，有两队青蛙在过河，每队有3只青蛙，如图所示。这些青蛙只能向前移动，不能向后移动，且一次只能有一只青蛙向前移动。在移动过程中，青蛙可以向前面的空位中移动，不可一次跳过两个位置，但是可以跳过对方一只青蛙进入前面的一个空位。问两队青蛙该如何移动才能够用最少的步数分别走向对岸？

讯享网

二、分析

我们来分析一下青蛙过河问题。可以采用如下方案来移动青蛙，操作步骤如下：

（1）左侧的青蛙向右跳过右侧的一只青蛙，落入空位，执行第（5）步。

（2）右侧的青蛙向左跳过左侧的一只青蛙，落入空位，执行第（5）步。

（3）左侧的青蛙向右移动一格，落入空位，执行第（5）步。

（4）右侧的青蛙向左移动一格，落入空位，执行第（5）步。

（5）判断是否已将两队青蛙移到对岸，如果没有则继续从第（1）步执行，否则结束程序。

三、编程

package com.joshua317; import jdk.nashorn.internal.ir.LiteralNode; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Main { public static void main(String[] args) { FrogCrossRiver frogCrossRiver = new FrogCrossRiver(); List frogQueue = frogCrossRiver.initFrogQueue(); String frogJumpInfo = (frogCrossRiver.frogJump(frogQueue, 3)); System.out.println("青蛙跳跃的顺序为：\r\n " + frogJumpInfo); } } class Frog { static enum frogDirection {向左, 向右}; public String frogName;//青蛙名称 public int position;//青蛙位置 public frogDirection direction;//青蛙跳动的方向 public boolean canJump;//是否可以跳 public boolean isEmpty = false;//是否是空格 //构造函数 public Frog (int position, String frogName, frogDirection direction, boolean canJump) { this.position = position; this.frogName = frogName; this.direction = direction; this.canJump = canJump; } public Frog (int position) { this.frogName = "空"; this.position = position; this.canJump = false; this.isEmpty = true; } public Frog (Frog frog) { this.position = frog.position; this.frogName = frog.frogName; this.direction = frog.direction; this.canJump = frog.canJump; this.isEmpty = frog.isEmpty; } } class FrogCrossRiver { //初始化青蛙队列 public List<Frog> initFrogQueue() { List<Frog> frogQueue = new ArrayList<Frog>(); frogQueue.add(new Frog(0, "左1", Frog.frogDirection.向右, false)); frogQueue.add(new Frog(1, "左2", Frog.frogDirection.向右, true)); frogQueue.add(new Frog(2, "左3", Frog.frogDirection.向右, true)); frogQueue.add(new Frog(3)); frogQueue.add(new Frog(4, "右1", Frog.frogDirection.向左, true)); frogQueue.add(new Frog(5, "右2", Frog.frogDirection.向左, true)); frogQueue.add(new Frog(6, "右3", Frog.frogDirection.向左, false)); return frogQueue; } //当一个青蛙跳动后，形成一个新的队列 private List<Frog> editFrogQueue(List<Frog> frogQueue, String frogName, int oldEmptyPostionId, int newEmptyPostionId) { List<Frog> newFrogQueue = new ArrayList<Frog>(); for (int i=0; i<frogQueue.size(); i++) { Frog frog = (Frog)frogQueue.get(i); Frog newFrog = new Frog(frog); if (newFrog.isEmpty) { newFrog.position = newEmptyPostionId; } if (newFrog.frogName == frogName) { newFrog.position = oldEmptyPostionId; } newFrog.canJump = false; if ((newEmptyPostionId - newFrog.position) > 0 && (newEmptyPostionId - newFrog.position) < 3 && newFrog.direction == Frog.frogDirection.向右) { newFrog.canJump = true; } if ((newFrog.position - newEmptyPostionId) > 0 && (newFrog.position - newEmptyPostionId) < 3 && newFrog.direction == Frog.frogDirection.向左) { newFrog.canJump = true; } newFrogQueue.add(newFrog); } return newFrogQueue; } //是否已经完成位置对换，即前三个青蛙的位置都大于3 private boolean isComplete(List<Frog> frogQueue) { return (frogQueue.get(0).position > 3 && frogQueue.get(1).position > 3 && frogQueue.get(2).position > 3); } //是否还有可以跳动的青蛙，只有可以跳动的，就没有达到最后的状态， //但都不可以跳动了也不一定对换完了，这里只是控制递归 private boolean canFrogJump(List<Frog> frogQueue) { for (int i=0; i<frogQueue.size(); i++) { Frog frog = (Frog)frogQueue.get(i); if (frog.canJump) { return true; } } return false; } //获取青蛙跳动的步骤 public String frogJump(List<Frog> frogQueue, int emptyPositionId) { String frogJumpInfo = ""; for (int i=0; i<frogQueue.size(); i++) { Frog frog = (Frog)frogQueue.get(i); //是空位置 if (frog.isEmpty) { continue; } //不能跳 if (!frog.canJump) { continue; } frogJumpInfo = "青蛙" + frog.frogName + " " + frog.direction + "跳到第" + (emptyPositionId + 1) + "个位置" + "\r\n"; int newPositionId = frog.position; List<Frog> newFrogQueue = this.editFrogQueue(frogQueue, frog.frogName, emptyPositionId,newPositionId); //只要能继续跳就递归 if (this.canFrogJump(newFrogQueue)) { frogJumpInfo += this.frogJump(newFrogQueue, newPositionId); } else { if (this.isComplete(newFrogQueue)) { frogJumpInfo += "成功"; break; } } if (frogJumpInfo.contains("成功")) { break; } } return frogJumpInfo; } }

四、练习

大家可以想一想如果是4只青蛙，5只青蛙，6只青蛙呢？

附一个小游戏的链接：http://www.4399.com/flash/204168_4.htm

本文为joshua317原创文章,转载请注明：转载自joshua317博客 算法-经典趣题-青蛙过河 - joshua317的博客