推 unfun:謝謝y大回覆 對我有很大幫助 05/09 08:57
※ 引述《unfun (不好玩)》之銘言：
: 小弟蓋出了世界奇觀但不想要這樣，請問有啥方法可以改進
: 主要想問的是程式編寫習慣及排版問題，我不想砍掉重練阿 = =
: 原程式:
: http://paste.plurk.com/show/247320/
: 小弟前天與友人玩一個遊戲，如下圖表示那樣
: ○
: ●●
: ●●●
: ●●●●
: ●●●●●
如何避開世界奇觀,大概就是用適合的資料表達方式來減少程式複雜程度.
我的做法是:
我先把這個圖表達為15個點,與18個三點連線
bool states[15] = {
false, true, true, true, true,
true, true, true, true, true,
true, true, true, true, true
};
// 0
// 1 2
// 3 4 5
// 6 7 8 9
// 10 11 12 13 14
int links[18][3] = {
{0, 1, 3}, {0, 2, 5},
{1, 3, 6}, {1, 4, 8},
{2, 4, 7}, {2, 5, 9},
{3, 4, 5}, {3, 6, 10}, {3, 7, 12},
{4, 7, 11}, {4, 8, 13},
{5, 8, 12}, {5, 9, 14},
{6, 7, 8},
{7, 8, 9},
{10, 11, 12},
{11, 12, 13},
{12, 13, 14}
};
相對有以下幾個程式,處理這個圖的一些屬性
// Count how many trues in a list.
int count(bool[], int);
// Check if a link is movable.
int movable(bool states[], int link[3]);
// Print pegged chessboard beautifully.
void printp(bool[], int);
int count(bool states[], int length) {
int i, r = 0;
for (i=0; i<length; i++)
if (states[i] == true)
r++;
return r;
}
int movable(bool states[], int link[3]) {
if (states[link[0]]&&states[link[1]]&&!states[link[2]])
return -1;
if (!states[link[0]]&&states[link[1]]&&states[link[2]])
return 1;
return 0;
}
void printp(bool states[], int length) {
int r = 1, w = 1, i;
for (i=0; i<length; i++, i<w?true:(r++,w=w+r,cout<<endl) ) {
if (states[i] == true)
cout << 'x';
else
cout << 'o';
}
}
找答案的過程是遞迴,
先找任何一個{true,true,false}把它變成{false,false,true}, (1->3)
或是{false,true,true}把它變成{true,false,false}, (1<-3)
然後用同樣的辦法檢查下一個盤面. 並且找不到答案時要backtracking.
尋找的程式結構是個tree,找出的解答(包含找對的和找錯的)也是個tree,
所以要定解答集 SetOfAnswers 資料結構為 multi-tree
// SetOfAnswers is a multi-tree.
struct SetOfAnswers {
int moved;
int pegged;
struct ListOfAnswers *successors;
};
struct ListOfAnswers {
struct SetOfAnswers *soa;
struct ListOfAnswers *next;
};
主要程式是稱為 kongming 的遞迴程式,程式沒寫得很好.
程式最好能整理出 multi-tree 的資料組織並傳回,但這方面程式繁雜先省略.
在以下 kongming 程式中,我加入一些印出各階層步驟的解答,可以看出程式做對事情.
struct SetOfAnswers* kongming
(bool states[], int stlen, int links[][3], int lklen)
{
static int level = 0;
level++;
printp(states,stlen);
int i, j, k, m;
struct SetOfAnswers *r;
// Base case
if (count(states, stlen) <= 1) {
cout << "END" << endl;
level--;
return NULL;
}
// Recursive case
r = new struct SetOfAnswers;
r->moved = -1;
r->successors = NULL;
for (i=0; i<stlen; i++) {
bool no_solution = false;
if (states[i] == false) continue;
for (j=0; j<lklen; j++) {
bool states1[stlen];
struct SetOfAnswers *p, *q;
if (links[j][0] != i && links[j][2] != i) continue;
k = movable(states, links[j]);
if (k == 0) continue;
no_solution = true;
// Make a copy of states and apply move
for (m=0; m<stlen; m++)
states1[m] = states[m];
p = new struct SetOfAnswers;
if (k < 0) {
states1[links[j][0]] = false;
states1[links[j][1]] = false;
states1[links[j][2]] = true;
p->moved = links[j][0];
p->pegged = links[j][2];
} else {
states1[links[j][0]] = true;
states1[links[j][1]] = false;
states1[links[j][2]] = false;
p->moved = links[j][2];
p->pegged = links[j][0];
}
cout << level << ". " << p->moved << " -> " << p->pegged << endl;
// Fetch parts of answers from recursive call and
// add effective ones into struct SetOfAnswers *p.
q = kongming(states1, stlen, links, lklen);
if (q == NULL)
p->successors = NULL;
else if (q->moved < 0) {
struct ListOfAnswers
*r = p->successors,
*r1 = q->successors;
while (r1 != NULL) {
r = r1;
r = r->next;
r1 = r1->next;
}
} else {
p->successors = new struct ListOfAnswers;
p->successors->soa = q;
p->successors->next = NULL;
}
// Update global state, struct SetOfAnswers *r.
if (r->successors == NULL) {
r->successors = new struct ListOfAnswers;
r->successors->soa = p;
r->successors->next = NULL;
} else {
struct ListOfAnswers *r1 = r->successors;
while (r1->next != NULL)
r1 = r1->next;
r1->next = new struct ListOfAnswers;
r1->next->soa = p;
r1->next->next = NULL;
}
}
if (no_solution) {
cout << "No solution found. Backtracking." << endl;
}
}
level--;
return r;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.209.141