青蛙换位java_青蛙换位
問題描述：
在7塊石頭上，有綠、紅青蛙各3只，?綠青蛙在左邊面向右，紅青蛙在右邊面向左，中間是個空位。每次移動一只青蛙，青蛙只能往前跳一步，或隔著一只青蛙跳一步，將左邊的綠青蛙移動到右邊，將右邊的紅青蛙移動到左邊。
解法一迭代回溯法：
#include
#include
typedef int BOOL;
#define TRUE1
#define FALSE0
void iterative_backtrack();// 迭代回溯法求解問題
void recursive_backtrack(int n);// 遞歸回溯法求問題解
BOOL can_shift(int i);// 判斷在第i個石頭上青蛙是否能移位
void frog_shift(int i);// 在第i個石頭上青蛙是否能移位
int where_empty();// 計算空位的位置
BOOL is_success();// 判斷是否已經(jīng)完成所有移位
void print_result();// 打印結(jié)果
#define EMPTY0// 表示空位
#define GREEN1// 表示綠青蛙
#define RED2// 表示紅青蛙
#define NUM7// 表示石頭數(shù)
#define MAXSTEP24// 完成移位可能需要的步數(shù)
/* stone[i]表示第i塊石頭上的物體 */
static int stone[NUM] = {GREEN, GREEN, GREEN, EMPTY, RED, RED, RED};
/* step[i]表示第i步驟時，哪塊石頭上的青蛙進行了移位 */
static int step[MAXSTEP];
int main() {
int i;
/* 遇到step[i]的值為-1時，表示該步驟未被執(zhí)行 */
for (i = 0; i < MAXSTEP; i++)
step[i] = -1;
iterative_backtrack();
return EXIT_SUCCESS;
}
/*
** 迭代回溯法求解
*/
void iterative_backtrack() {
int n = 0;// 迭代的深度，即執(zhí)行的步驟數(shù)
int i = 0;// 當前將進行移位的青蛙的位置
int frog_pos[MAXSTEP];// 保存每一步驟將進行移位的青蛙的位置
int empty_pos[MAXSTEP];// 保存沒一步驟空位的位置
while(TRUE) {
/* 尋找第一只能夠移位的青蛙 */
while (i < NUM && !can_shift(i))
i++;
/* 如果存在能夠移位的青蛙 */
if (i < NUM) {
/* 保存當前將進行移位的青蛙的位置 */
frog_pos[n] = i;
/* 保存當前空位的位置 */
empty_pos[n] = where_empty();
/* 記錄第n步驟時，第i塊石頭上的青蛙進行移位 */
step[n] = i;
/* 第i塊石頭上的青蛙進行移 */
frog_shift(i);
/* 如果已經(jīng)完成所有青蛙的正確移位 */
if (is_success()) {
print_result();// 打印結(jié)果
n++;// 進行下一步驟
}
/* 如果還未完成所有青蛙的正確移位 */
else {
n++;// 進行下一步驟
i = 0;// 從第0塊石頭上的青蛙開始迭代
}
}
/* 如果每一塊石頭上的青蛙都不能進行移位 */
else {
/* 回溯至上一步驟，如果是回溯至第-1步驟時，結(jié)束迭代 */
if (--n < 0)
break;
frog_shift(empty_pos[n]);// 將上一步驟進行移位的青蛙移回原處
i = frog_pos[n] + 1;// 從下一塊石頭的青蛙開始迭代
}
}
}
/*
** 判斷在第i個石頭上青蛙是否能移位
*/
BOOL can_shift(int i) {
int empty_pos = where_empty();
switch(stone[i]) {
/*
** 綠青蛙從左往右跳，如果前面兩塊石頭中有個空位，那么該青蛙能夠移位
** 紅青蛙從右往左跳，如果前面兩塊石頭中有個空位，那么該青蛙能夠移位
*/
case GREEN:
if (empty_pos > i && empty_pos <= i + 2)
return TRUE;
break;
case RED:
if (empty_pos < i && empty_pos >= i - 2)
return TRUE;
break;
case EMPTY:
default:
return FALSE;
break;
}
return FALSE;
}
/*
** 在第i塊石頭上的青蛙進行移位
*/
void frog_shift(int i) {
int empty_pos = where_empty();
stone[empty_pos] = stone[i];
stone[i] = EMPTY;
}
/*
** 計算空位的位置
*/
int where_empty() {
int i;
for (i = 0; i < NUM; i++)
if (stone[i] == EMPTY) break;
return i;
}
/*
** 判斷是否已經(jīng)完成所有移位
*/
BOOL is_success() {
if (stone[0] == RED &&
stone[1] == RED &&
stone[2] == RED &&
stone[3] == EMPTY &&
stone[4] == GREEN &&
stone[5] == GREEN &&
stone[6] == GREEN)
return TRUE;
return FALSE;
}
/*
** 打印結(jié)果
*/
void print_result() {
int i;
for (i = 0; i < MAXSTEP; i++) {
if (step[i] == -1)
break;
printf("%d ", step[i]);
}
putchar('\n');
}
解法二遞歸回溯法：
#include
#include
typedef int BOOL;
#define TRUE1
#define FALSE0
void iterative_backtrack();// 迭代回溯法求解問題
void recursive_backtrack(int n);// 遞歸回溯法求問題解
BOOL can_shift(int i);// 判斷在第i個石頭上青蛙是否能移位
void frog_shift(int i);// 在第i個石頭上青蛙是否能移位
int where_empty();// 計算空位的位置
BOOL is_success();// 判斷是否已經(jīng)完成所有移位
void print_result();// 打印結(jié)果
#define EMPTY0// 表示空位
#define GREEN1// 表示綠青蛙
#define RED2// 表示紅青蛙
#define NUM7// 表示石頭數(shù)
#define MAXSTEP24// 完成移位可能需要的步數(shù)
/* stone[i]表示第i塊石頭上的物體 */
static int stone[NUM] = {GREEN, GREEN, GREEN, EMPTY, RED, RED, RED};
/* step[i]表示第i步驟時，哪塊石頭上的青蛙進行了移位 */
static int step[MAXSTEP];
int main() {
int i;
/* 遇到step[i]的值為-1時，表示該步驟未被執(zhí)行 */
for (i = 0; i < MAXSTEP; i++)
step[i] = -1;
recursive_backtrack(0);
return EXIT_SUCCESS;
}
/*
** 遞歸回溯法求解
** n表示遞歸的深度數(shù)，即執(zhí)行的步驟
*/
void recursive_backtrack(int n) {
int i;
int original_empty_pos;
if (is_success()) {
print_result();
} else {
/* 從第0塊石頭上的青蛙逐一嘗試 */
for (i = 0; i < NUM; i++) {
/* 如果第i塊石頭上的青蛙能夠進行移位 */
if (can_shift(i)) {
/* 記錄青蛙移位前，空位的位置 */
original_empty_pos = where_empty();
/* 記錄第n步驟時，第i塊石頭上的青蛙進行移位 */
step[n] = i;
/* 第i塊石頭上的青蛙進行移位 */
frog_shift(i);
/* 執(zhí)行下一步驟，第n+1步驟 */
recursive_backtrack(n+1);
/* 回溯，將青蛙移回原來的位置 */
frog_shift(original_empty_pos);
}
}
}
}
/*
** 判斷在第i個石頭上青蛙是否能移位
*/
BOOL can_shift(int i) {
int empty_pos = where_empty();
switch(stone[i]) {
/*
** 綠青蛙從左往右跳，如果前面兩塊石頭中有個空位，那么該青蛙能夠移位
** 紅青蛙從右往左跳，如果前面兩塊石頭中有個空位，那么該青蛙能夠移位
*/
case GREEN:
if (empty_pos > i && empty_pos <= i + 2)
return TRUE;
break;
case RED:
if (empty_pos < i && empty_pos >= i - 2)
return TRUE;
break;
case EMPTY:
default:
return FALSE;
break;
}
return FALSE;
}
/*
** 在第i塊石頭上的青蛙進行移位
*/
void frog_shift(int i) {
int empty_pos = where_empty();
stone[empty_pos] = stone[i];
stone[i] = EMPTY;
}
/*
** 計算空位的位置
*/
int where_empty() {
int i;
for (i = 0; i < NUM; i++)
if (stone[i] == EMPTY) break;
return i;
}
/*
** 判斷是否已經(jīng)完成所有移位
*/
BOOL is_success() {
if (stone[0] == RED &&
stone[1] == RED &&
stone[2] == RED &&
stone[3] == EMPTY &&
stone[4] == GREEN &&
stone[5] == GREEN &&
stone[6] == GREEN)
return TRUE;
return FALSE;
}
/*
** 打印結(jié)果
*/
void print_result() {
int i;
for (i = 0; i < MAXSTEP; i++) {
if (step[i] == -1)
break;
printf("%d ", step[i]);
}
putchar('\n');
}
結(jié)果輸出：
2 4 5 3 1 0 2 4 6 5 3 1 2 4 3
4 2 1 3 5 6 4 2 0 1 3 5 4 2 3
總結(jié)
以上是生活随笔為你收集整理的青蛙换位java_青蛙换位的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 百度百科去水印
- 下一篇： mysql建库需要权限吗_mysql 建