程序員面試例題

程序員面試例題

　　面試例題：八皇后問(wèn)題是一個(gè)古老而著(zhù)名的問(wèn)題，是回溯算法的典型例題。該問(wèn)題是 19 世紀著(zhù)名的數學(xué)家高斯 1850 年提出：在 8×8 格的國際象棋盤(pán)上擺放 8 個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線(xiàn)上，問(wèn)有多少種擺法。[英國某著(zhù)名計算機圖形圖像公司面試題]

　　解析：遞歸實(shí)現 n 皇后問(wèn)題。

　　算法分析：

　　數組 a、b、c 分別用來(lái)標記沖突，a 數組代表列沖突，從 a[0]~a[7]代表第 0 列到第 7 列。如果某列上已經(jīng)有皇后，則為 1，否則為 0。

　　數組 b 代表主對角線(xiàn)沖突，為 b[i-j+7]，即從 b[0]~b[14]。如果某條主對角線(xiàn)上已經(jīng)有皇后，則為 1，否則為 0。

　　數組 c 代表從對角線(xiàn)沖突，為 c[i+j]，即從 c[0]~c[14]。如果某條從對角線(xiàn)上已經(jīng)有皇后，則為 1，否則為 0。

　　代碼如下：

　　#include

　　static char Queen[8][8];

　　static int a[8];

　　static int b[15];

　　static int c[15];

　　static int iQueenNum=0; //記錄總的棋盤(pán)狀態(tài)數

　　void qu(int i);

　　//參數i 代表行

　　int main()

　　{

　　int iLine,iColumn;

　　//棋盤(pán)初始化，空格為*，放置皇后的地方為@

　　for(iLine=0;iLine<8;iLine++)

　　{

　　a[iLine]=0; //列標記初始化，表示無(wú)列沖突

　　for(iColumn=0;iColumn<8;iColumn++)

　　Queen[iLine][iColumn]='*';

　　}

　　//主、從對角線(xiàn)標記初始化，表示沒(méi)有沖突

　　for(iLine=0;iLine<15;iLine++)

　　b[iLine]=c[iLine]=0;

　　qu(0);

　　return 0;

　　}

　　void qu(int i)

　　{

　　int iColumn;

　　for(iColumn=0;iColumn<8;iColumn++)

　　{

　　if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0)

　　//如果無(wú)沖突

　　{

　　Queen[i][iColumn]='@';

　　//放皇后

　　a[iColumn]=1;

　　//標記，下一次該列上不能放皇后

　　b[i-iColumn+7]=1;

　　//標記，下一次該主對角線(xiàn)上不能放皇后

　　c[i+iColumn]=1;

　　//標記，下一次該從對角線(xiàn)上不能放皇后

　　if(i<7) qu(i+1);

　　//如果行還沒(méi)有遍歷完，進(jìn)入下一行

　　else //否則輸出

　　{

　　//輸出棋盤(pán)狀態(tài)

　　int iLine,iColumn;

　　printf("第%d 種狀態(tài)為： ",++iQueenNum);

　　for(iLine=0;iLine<8;iLine++)

　　{

　　for(iColumn=0;iColumn<8;iColumn++)

　　printf("%c ",Queen[iLine][iColumn]);

　　printf(" ");

　　}

　　printf(" ");

　　}

　　//如果前次的皇后放置導致后面的放置無(wú)論如何都不能滿(mǎn)足要求，則回溯，重置

　　Queen[i][iColumn]='*';

　　a[iColumn]=0;

　　b[i-iColumn+7]=0;

　　c[i+iColumn]=0;

　　}

　　}

　　}

【程序員面試例題】相關(guān)文章：

程序員軟件水平考試筆試例題和答案06-21

筆試題例題06-21

程序員面試技巧07-13

程序員面試經(jīng)驗07-13

程序員面試寶典07-09

高考典型例題分析06-24

程序員面試項目經(jīng)驗06-30

程序員面試技巧總結07-13

程序員筆試面試寶典07-13

程序員面試題精選07-12