青蛙过河问题

青蛙过河问题

科技前沿 • 2025-01-05 17:04 • 阅读 69

大家好，我是讯享网，很高兴认识大家。

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

先来分析一下青蛙过河问题。可以采用如下的方案来移动青蛙，

(1)左侧的青蛙向右跳过右侧的一只青蛙，落入空位，执行第

(2)右侧的青蛙向左跳过左侧的一只青蛙，落入空位，执行第

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

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

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

我们可以按照这个思路来编写相应的青蛙过河问题的求解算法

C++示例代码如下：

#include<iostream>
#include<iomanip>
using namespace std;

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

void show(int *flog) {
for (int i = 0; i < 7; i++) {
cout <<setw(3)<< flog[i] ;
}
cout << endl;
}

void caculate(int *flog) {
while (flog[0] + flog[1] + flog[2] != -3 || flog[4] + flog[5] + flog[6] != 3) {
bool ok = true;
for (int i = 0; ok && i < 6; i++) {
if (flog[i] == 1 && flog[i + 1] == -1 && flog[i + 2] == 0) {
swap(&flog[i], &flog[i + 2]);
ok = false;
}
}
for (int i = 0; ok && i < 6; i++) {
if (flog[i] == 0 && flog[i + 1] == 1 && flog[i + 2] == -1) {
swap(&flog[i], &flog[i + 2]);
ok = false;
}
}

for (int i = 0; ok && i < 6; i++) {
if (flog[i] == 1 && flog[i + 1] == 0 && (i == 0 || flog[i - 1] != flog[i + 2])) {
swap(&flog[i], &flog[i + 1]);
ok = false;
}
}
for (int i = 0; ok && i < 6; i++) {
if (flog[i] == 0 && flog[i + 1] == -1 && (i == 5 || flog[i - 1] != flog[i + 2])) {
swap(&flog[i], &flog[i + 1]);
ok = false;
}
}
show(flog);
}
}

void main() {
int flog[7] = { 1,1,1,0,-1,-1,-1 };
caculate(flog);
system("pause");
}

运行结果如下：

相关推荐