[問題] knight漫遊 用遞迴解
( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
( 未必需要依照此格式，文章條理清楚即可 )
遇到的問題： (題意請描述清楚)
不知道想要問什麼了
堆疊解還OK
遞迴就很難弄-.-
而且偏偏一堆書都扯什麼遞迴不值得用啦 用其他方法解安定
SO只好來這貼CODE了
希望得到的正確結果：
輸出會跑出5*5棋盤
從(1,1)這個起點開始
然後1234567...標到24一次走完 不用回到原點
程式跑出來的錯誤結果：
堆疊的話 是利用回朔法 就可以返回去重走
但遞迴也真的沒啥經驗(只有階乘和河內塔)
大概講一下我那程式怎麼用遞迴
1.我嘗試用遞迴 返回去
2.最後一次的遞迴 = 已經是確定常數的回傳值
3.大概是跑無限遞迴吧 最終是記憶體XXX錯誤 用pause測圖時是還可以畫
4.問題的癥結點 到跑第20個位子後 騎士已經無法可走 要逆回的時候
其實一開始想是 不要逆回了 找個方法讓這個遞迴暴掉 讓上一個遞迴可以去跑
但不知道該怎麼做-.- 如果真的有這個方法就先講這部分吧....
5.這是一個問題啦 遞迴是不是 只要執行到回傳固定的值
之前的一堆遞迴就暴掉了 是嗎?
開發平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux)
devc++
有問題的code： (請善用置底文標色功能)
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
#define SUCCESS 1
#define FAILURE 0
#define EMPTY -1
int board[MAXSIZE+1][MAXSIZE+1];
int n; //working board size
int offset_x[] = {2,1,-1,-2,-2,-1,1,2};
int offset_y[] = {1,2,2,1,-1,-2,-2,-1};
int count=0;
void initial(int);
void display();
int move(int,int,int,int);
void show();
int main()
{
n=5;
initial(n);
show();
system("pause");
}
void initial(int n)
{
int i,j;
/*棋盤初始化*/
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
board[i][j]=EMPTY;
printf("====在%d*%d的西洋棋盤上====\n",n,n);
}
void show()
{
if(move(1,1,-1,-1) == FAILURE) //起點從(1,1)開始
printf("NO SOLUTION\n");
else
display();
}
#define YES 1
#define NO 0
#define BOARD(x,y) (1<=x) && (x<=n) && (1<=y) && (y<=n)
#define CHECK(x,y) board[x][y] == EMPTY
int move(int x, int y,int visited,int ignore)
{
int new_x,new_y,i=0,j,found=NO;
//已設 board[1][1]=0;
while(count < n*n-1){
found = NO;
while (i < 8){ //八個方向都試
if(i==visited && ignore==YES) i++;
ignore = NO;
new_x = x + offset_x[i];
new_y = y + offset_y[i];
if(BOARD(new_x,new_y) && CHECK(new_x,new_y)){
board[new_x][new_y]=++count;
found = YES;
ignore = NO;
visited = i;
move(new_x,new_y,visited,ignore);
break;
}
else
i++;
}
/*八個方向都不能走*/
if(!found) // cout<<(!found) 輸出是0
if(count > 0){
board[x][y] = EMPTY ;
new_x = x - offset_x[visited];
new_y = y - offset_y[visited];
count--;
ignore=YES;
return move(new_x,new_y,visited,ignore);
}
else
return FAILURE;
}
return SUCCESS;
}
補充說明：
display()函式沒問題我就不寫了
精華區的看過了 那是用堆疊
先吃個飯
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.171.74.174
推
08/11 19:22, , 1F
08/11 19:22, 1F
→
08/11 19:22, , 2F
08/11 19:22, 2F
→
08/11 19:23, , 3F
08/11 19:23, 3F
→
08/11 19:23, , 4F
08/11 19:23, 4F
推
08/11 19:41, , 5F
08/11 19:41, 5F
推
08/11 19:43, , 6F
08/11 19:43, 6F
推
08/11 19:44, , 7F
08/11 19:44, 7F
推
08/11 19:48, , 8F
08/11 19:48, 8F
ture false不是相當於1 0嗎
不過先試試看好了..
另外堆疊解是指用top什麼的去指一個資料結構
推
08/11 19:50, , 9F
08/11 19:50, 9F
→
08/11 19:51, , 10F
08/11 19:51, 10F
→
08/11 19:51, , 11F
08/11 19:51, 11F
Y 目前這題目是類似的
※ 編輯: calqlus 來自: 118.171.74.174 (08/11 20:04)
意外的成功了= =
我取消ignore的引入值
把八個方向找不到的那個函式 回傳值 改 false
就瞬殺了.....
感謝PTT良解
※ 編輯: calqlus 來自: 118.171.74.174 (08/11 20:09)
剛剛又發現一件不幸的事
他移動的位子 11->12 出錯了..
不過改一下應該就好了
※ 編輯: calqlus 來自: 118.171.74.174 (08/11 20:11)
if(i==vi) i++那段下一行
補if(i>=8) break;
GG
※ 編輯: calqlus 來自: 118.171.74.174 (08/11 20:13)
→
08/11 20:28, , 12F
08/11 20:28, 12F
→
08/11 20:29, , 13F
08/11 20:29, 13F
→
08/11 21:08, , 14F
08/11 21:08, 14F
推
08/11 21:48, , 15F
08/11 21:48, 15F
→
08/11 21:49, , 16F
08/11 21:49, 16F
推
08/12 00:38, , 17F
08/12 00:38, 17F