Re: [問題] 遞迴改非遞迴
以往我也是遞迴寫，突然要搞非遞迴有點遇到困難的感覺。
不過設定好該保留每個數選擇下一個數的陣列(pos)也是可以辦到。
另外要說明一下有些人覺得要怎麼跳出迴圈。
因為是一筆劃，輸出答案的長度是9位數，index 會從0到8。
如果不合會減1，那跳出迴圈就是index減到 < 0。看程式碼就很容易了解了。
UVa那裡只需要0開頭即可。有興趣也可以包一個外迴圈改成0到4所有開頭都跑。
以下程式已經測試通過，僅供參考。
Bleed
#include <iostream>
using namespace std;
unsigned int adj[5][5] = {{0, 1, 1, 0, 1},
{1, 0, 1, 0, 1},
{1, 1, 0, 1, 1},
{0, 0, 1, 0, 1},
{1, 1, 1, 1, 0}};
unsigned int pos[8][5];
int main()
{
unsigned int answer[9], now = 0;
int x = 0;
while (true)
{
answer[x] = now;
if (x == 8)
{
for (unsigned int i = 0; i != 9; ++i)
cout << answer[i] + 1;
cout << "\n";
if (x > 0)
{
++adj[answer[x - 1]][now];
++adj[now][answer[x - 1]];
}
--x;
now = answer[x];
}
unsigned int j;
for (j = pos[x][now]; j != 5; ++j)
if (adj[now][j] > 0)
{
--adj[now][j];
--adj[j][now];
pos[x][now] = j + 1;
now = j;
break;
}
if (j == 5)
{
if (x > 0)
{
++adj[answer[x - 1]][now];
++adj[now][answer[x - 1]];
}
pos[x][now] = 0;
--x;
if (x < 0)
break;
now = answer[x];
}
else
++x;
}
return(0);
}
※ 引述《remember11 (紀元)》之銘言：
: 如題
: 這是題目的網址
: http://uva.onlinejudge.org/external/2/291.html
: 這是ACM的競賽題目 (一筆劃問題)
: 下面的程式碼是老師給的 c語言code
: 老師要我們把它從"遞迴"改成"非遞迴"
: 因為小弟才疏學淺+遞迴很少用...
: 我大概改了兩個版本都失敗
: 我遇到了兩個問題
: ●找不到結束的條件式//要把所有的可能找出來
: ●無法將map陣列重新放回1
: /*
: map[now][a]=1;
: map[a][now]=1;
: */
: 不知道有沒有大大可以指點思考一下方向
: //----------------------------------------
: #include<stdio.h>
: #include<stdlib.h>
: int map[5][5]={
: 0,1,1,0,1,
: 1,0,1,0,1,
: 1,1,0,1,1,
: 0,0,1,0,1,
: 1,1,1,1,0};
: int tryway[9]={0};
: void make(int now,int go)
: {
: int a,b,sum=0;
: tryway[go]=now;
: for(a=0;a<5;a++)
: for(b=0;b<5;b++) sum=sum+map[a][b];
: if(sum==0)
: {
: for(a=0;a<9;a++) printf("%d",tryway[a]+1);
: printf("\n");
: }
: for(a=0;a<5;a++)
: if(map[now][a]==1&&a!=now)
: {
: map[now][a]=0;
: map[a][now]=0;
: make(a,go+1);
: map[now][a]=1;
: map[a][now]=1;
: }
: }
: main()
: {
: make(0,0);
: system("pause");
: return 0;
: }
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.177.97
討論串 (同標題文章)
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
