首页 > 代码库 > 趣味算法——青蛙过河(JAVA)
趣味算法——青蛙过河(JAVA)
青蛙过河是一个非常有趣的智力游戏，其大意如下： 一条河之间有若干个石块间隔，有两队青蛙在过河，每队有3只青蛙，这些青蛙只能向前移动，不能向后移动，且一次只能有一只青蛙向前移动。在移动过程中，青蛙可以向前面的空位中移动，不可以一次跳过两个位置，但是可以跳过对方一只青蛙进入到前面的一个空位。问两队青蛙该如何移动才能用最少的步数分别走向对岸？（ → → → □ ← ← ← ）可能3只青蛙太少了，心算也不难。如果有100只青蛙呢？
/** * 青蛙过河 * @author rubekid * */public class RiverFrog { public static final int LEFT_FROG = -1; public static final int RIGHT_FROG = 1; public static final int STONE = 0; private int[] frogs; private int zeroIndex; private int length; private int step = 0; public RiverFrog(int number) { frogs = new int[number * 2 +1]; length = frogs.length; zeroIndex = length /2; for(int i=0; i< number; i++){ frogs[i] = LEFT_FROG; } frogs[zeroIndex] = STONE; for(int i=0; i< number; i++){ frogs[i+ zeroIndex + 1] = RIGHT_FROG; } } public void run(){ while(!isMoveEnd(LEFT_FROG) || !isMoveEnd(RIGHT_FROG)){ int left = zeroIndex - 1; int right = zeroIndex+1; if(left>-1 && right <length){ if(frogs[left] != frogs[right]){ if(frogs[left] == LEFT_FROG){ if(left > 0 && frogs[left-1] == RIGHT_FROG){//若移动right，则在中间有两只RIGHT并排 this.move(right); } else{ this.move(left); } } else if(left > 0 && frogs[left-1]==LEFT_FROG ){ this.move(left-1); } else if(right <= length && frogs[right+1] == RIGHT_FROG){ this.move(right+1); } } else{ if(frogs[left] == RIGHT_FROG){ if(left > 0 && frogs[left-1] == LEFT_FROG){ this.move(left - 1); } else if(right+1 < length && frogs[right+1] == RIGHT_FROG){ this.move(right+1); } else if(frogs[right] == RIGHT_FROG){ this.move(right); } } else if(frogs[right] == LEFT_FROG){ if(right+1 < length && frogs[right+1] == RIGHT_FROG){ this.move(right + 1); } else if(left >0 && frogs[left-1] == LEFT_FROG){ this.move(left-1); } else if(frogs[left] == LEFT_FROG){ this.move(left); } } } } else if(left == -1){ if(frogs[right] == LEFT_FROG && right<length-1){ this.move(right+1); } else{ this.move(right); } } else if(right == length){ if(frogs[left] == RIGHT_FROG && left > 0){ this.move(left-1); } else{ this.move(left); } } } System.out.println("step:" + step); } private void move(int i){ int temp = frogs[i]; frogs[i] = frogs[zeroIndex]; frogs[zeroIndex] = temp; zeroIndex = i; step++; print(); } private boolean isMoveEnd(int value){ int i=0; int max= zeroIndex; if(value =http://www.mamicode.com/= LEFT_FROG){ i = zeroIndex+1; max = length; } for(int j=i; j<max; j++){ if(frogs[j]!=value){ return false; } } return true; } private void print(){ StringBuffer stringBuffer = new StringBuffer(); for(int frog : frogs){ if(frog>-1){ stringBuffer.append(" " +frog + " "); } else{ stringBuffer.append(frog + " "); } } System.out.println(stringBuffer.toString()); }}
趣味算法——青蛙过河(JAVA)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。