【文章內(nèi)容簡(jiǎn)介】 lse { for(j = 1。 j = N。 j++) { if(column[j] == 1 amp。amp。 rup[i+j] == 1 amp。amp。 lup[ij+N] == 1) { queen[i] = j。 // 設(shè)定為占用 column[j] = rup[i+j] = lup[ij+N] = 0。 backtrack(i+1)。 column[j] = rup[i+j] = lup[ij+N] = 1。 } } } }  Gossip: 八枚銀幣說(shuō)明現(xiàn)有八枚銀幣a b c d e f g h，已知其中一枚是假幣，其重量不同于真幣，但不知是較輕或較重，如何使用天平以最少的比較次數(shù)，決定出哪枚是假幣，并得知假幣比真幣較輕或較重。解法單就求假幣的問(wèn)題是不難，但問(wèn)題限制使用最少的比較次數(shù)，所以我們不能以單純的回圈比較來(lái)求解，我們可以使用決策樹（decision tree），使用分析與樹狀圖來(lái)協(xié)助求解。一個(gè)簡(jiǎn)單的狀況是這樣的，我們比較a+b+c與d+e+f ，如果相等，則假幣必是g或h，我們先比較g或h哪個(gè)較重，如果g較重，再與a比較（a是真幣），如果g等于a，則g為真幣，則h為假幣，由于h比g輕而 g是真幣，則h假幣的重量比真幣輕。include include include void pare(int[], int, int, int)。 void eightcoins(int[])。 int main(void) { int coins[8] = {0}。 int i。 srand(time(NULL))。 for(i = 0。 i 8。 i++) coins[i] = 10。 printf(\n輸入假幣重量(比10大或小)：)。 scanf(%d, amp。i)。 coins[rand() % 8] = i。 eightcoins(coins)。 printf(\n\n列出所有錢幣重量：)。 for(i = 0。 i 8。 i++) printf(%d , coins[i])。 printf(\n)。 return 0。 } void pare(int coins[], int i, int j, int k) { if(coins[i] coins[k]) printf(\n假幣 %d 較重, i+1)。 else printf(\n假幣 %d 較輕, j+1)。 } void eightcoins(int coins[]) { if(coins[0]+coins[1]+coins[2] == coins[3]+coins[4]+coins[5]) { if(coins[6] coins[7]) pare(coins, 6, 7, 0)。 else pare(coins, 7, 6, 0)。 } else if(coins[0]+coins[1]+coins[2] coins[3]+coins[4]+coins[5]) { if(coins[0]+coins[3] == coins[1]+coins[4]) pare(coins, 2, 5, 0)。 else if(coins[0]+coins[3] coins[1]+coins[4]) pare(coins, 0, 4, 1)。 if(coins[0]+coins[3] coins[1]+coins[4]) pare(coins, 1, 3, 0)。 } else if(coins[0]+coins[1]+coins[2] coins[3]+coins[4]+coins[5]) { if(coins[0]+coins[3] == coins[1]+coins[4]) pare(coins, 5, 2, 0)。 else if(coins[0]+coins[3] coins[1]+coins[4]) pare(coins, 3, 1, 0)。 if(coins[0]+coins[3] coins[1]+coins[4]) pare(coins, 4, 0, 1)。 } }  Gossip: 生命游戲說(shuō)明生命游戲（game of life）為1970年由英國(guó)數(shù)學(xué)家J. H. Conway所提出，某一細(xì)胞的鄰居包括上、下、左、右、左上、左下、右上與右下相鄰之細(xì)胞，游戲規(guī)則如下：孤單死亡：如果細(xì)胞的鄰居小于一個(gè)，則該細(xì)胞在下一次狀態(tài)將死亡。 擁擠死亡：如果細(xì)胞的鄰居在四個(gè)以上，則該細(xì)胞在下一次狀態(tài)將死亡。 穩(wěn)定：如果細(xì)胞的鄰居為二個(gè)或三個(gè)，則下一次狀態(tài)為穩(wěn)定存活。 復(fù)活：如果某位置原無(wú)細(xì)胞存活，而該位置的鄰居為三個(gè)，則該位置將復(fù)活一細(xì)胞。解法生命游戲的規(guī)則可簡(jiǎn)化為以下，并使用CASE比對(duì)即可使用程式實(shí)作：鄰居個(gè)數(shù)為0、8時(shí)，則該細(xì)胞下次狀態(tài)為死亡。 鄰居個(gè)數(shù)為2時(shí)，則該細(xì)胞下次狀態(tài)為復(fù)活。 鄰居個(gè)數(shù)為3時(shí)，則該細(xì)胞下次狀態(tài)為穩(wěn)定。 include include include define MAXROW 10 define MAXCOL 25 define DEAD 0 define ALIVE 1 int map[MAXROW][MAXCOL], newmap[MAXROW][MAXCOL]。 void init()。 int neighbors(int, int)。void outputMap()。void copyMap()。int main() { int row, col。 char ans。 init()。 while(1) { outputMap()。 for(row = 0。 row MAXROW。 row++) { for(col = 0。 col MAXCOL。 col++) { switch (neighbors(row, col)) { case 0: case 1: case 4: case 5: case 6: case 7: case 8: newmap[row][col] = DEAD。 break。 case 2: newmap[row][col] = map[row][col]。 break。 case 3: newmap[row][col] = ALIVE。 break。 } } } copyMap()。 printf(\nContinue next Generation ? )。 getchar()。 ans = toupper(getchar())。 if(ans != 39。Y39。) break。 } return 0。 } void init() { int row, col。 for(row = 0。 row MAXROW。 row++) for(col = 0。 col MAXCOL。 col++) map[row][col] = DEAD。 puts(Game of life Program)。 puts(Enter x, y where x, y is living cell)。 printf(0 = x = %d, 0 = y = %d\n, MAXROW1, MAXCOL1)。 puts(Terminate with x, y = 1, 1)。 while(1) { scanf(%d %d, amp。row, amp。col)。 if(0 = row amp。amp。 row MAXROW amp。amp。 0 = col amp。amp。 col MAXCOL) map[row][col] = ALIVE。 else if(row == 1 || col == 1) break。 else printf((x, y) exceeds map ranage!)。 }}int neighbors(int row, int col) { int count = 0, c, r。 for(r = row1。 r = row+1。 r++) for(c = col1。 c = col+1。 c++) { if(r 0 || r = MAXROW || c 0 || c = MAXCOL) continue。 if(map[r][c] == ALIVE) count++。 } if(map[row][col] == ALIVE) count。 return count。 } void outputMap() { int row, col。 printf(\n\n%20cGame of life cell status\n)。 for(row = 0。 row MAXROW。 row++) { printf(\n%20c, 39。 39。)。 for(col = 0。 col MAXCOL。 col++) if(map[row][col] == ALIVE) putchar(39。39。)。 else putchar(39。39。)。 } } void copyMap() { int row, col。 for(row = 0。 row MAXROW。 row++) for(col = 0。 col MAXCOL。 col++) map[row][col] = newmap[row][col]。 }  Gossip: 字串核對(duì)說(shuō)明今日的一些高階程式語(yǔ)言對(duì)于字串的處理支援越來(lái)越強(qiáng)大（例如Java、Perl等），不過(guò)字串搜尋本身仍是個(gè)值得探討的課題，在這邊以Boyer Moore法來(lái)說(shuō)明如何進(jìn)行字串說(shuō)明，這個(gè)方法快且原理簡(jiǎn)潔易懂。解法字串搜尋本身不難，使用暴力法也可以求解，但如何快速搜尋字串就不簡(jiǎn)單了，傳統(tǒng)的字串搜尋是從關(guān)鍵字與字串的開頭開始比對(duì)，例如 KnuthMorrisPratt 演算法 字串搜尋，這個(gè)方法也不錯(cuò)，不過(guò)要花時(shí)間在公式計(jì)算上；BoyerMoore字串核對(duì)改由關(guān)鍵字的后面開始核對(duì)字串，并制作前進(jìn)表，如果比對(duì)不符合則依前進(jìn)表中的值前進(jìn)至下一個(gè)核對(duì)處，假設(shè)是p好了，然后比對(duì)字串中pn+1至p的值是否與關(guān)鍵字相同。 如果關(guān)鍵字中有重復(fù)出現(xiàn)的字元，則前進(jìn)值就會(huì)有兩個(gè)以上的值，此時(shí)則取前進(jìn)值較小的值，如此就不會(huì)跳過(guò)可能的位置，例如texture這個(gè)關(guān)鍵字，t的前進(jìn)值應(yīng)該取后面的3而不是取前面的7。include include include void table(char*)。 // 建立前進(jìn)表 int search(int, char*, char*)。 // 搜尋關(guān)鍵字 void substring(char*, char*, int, int)。 // 取出子字串 int skip[256]。 int main(void) { char s