• <nav id="cwumo"><code id="cwumo"></code></nav>
  • <menu id="cwumo"><strong id="cwumo"></strong></menu>

    程序員遞歸面試問題及解析

    時間:2020-11-07 17:42:50 面試問題 我要投稿

    程序員遞歸面試問題及解析

    面試例題 2:八皇后問題是一個古老而著名的`問題,是回溯算法的典型例題。該問題是 19 世紀著名的數學家高斯 1850 年提出:在 8×8 格的國際象棋盤上擺放 8 個皇后,使其不能互相攻擊,即任意兩個皇后都不能處于同一行、同一列或同一斜線上,問有多少種擺法。[英國某著名計算機圖形圖像公司面試題]
    解析:遞歸實現 n 皇后問題。
    算法分析:
    數組 a、b、c 分別用來標記沖突,a 數組代表列沖突,從 a[0]~a[7]代表第 0 列到第 7 列。如果某列上已經有皇后,則為 1,否則為 0。
    數組 b 代表主對角線沖突,為 b[i-j+7],即從 b[0]~b[14]。如果某條主對角線上已經有皇后,則為 1,否則為 0。
    數組 c 代表從對角線沖突,為 c[i+j],即從 c[0]~c[14]。如果某條從對角線上已經有皇后,則為 1,否則為 0。
    代碼如下:
    #include <stdio.h>
    static char Queen[8][8];
    static int a[8];
    static int b[15];
    static int c[15];
    static int iQueenNum=0; //記錄總的棋盤狀態數
    void qu(int i);
    //參數i 代表行
    int main()
    {
    int iLine,iColumn;
    //棋盤初始化,空格為*,放置皇后的地方為@
    for(iLine=0;iLine<8;iLine++)
    {
    a[iLine]=0; //列標記初始化,表示無列沖突
    for(iColumn=0;iColumn<8;iColumn++)
    Queen[iLine][iColumn]='*';
    }
    //主、從對角線標記初始化,表示沒有沖突
    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)
    //如果無沖突
    {
    Queen[i][iColumn]='@';
    //放皇后
    a[iColumn]=1;
    //標記,下一次該列上不能放皇后
    b[i-iColumn+7]=1;
    //標記,下一次該主對角線上不能放皇后
    c[i+iColumn]=1;
    //標記,下一次該從對角線上不能放皇后
    if(i<7) qu(i+1);
    //如果行還沒有遍歷完,進入下一行
    else //否則輸出
    {
    //輸出棋盤狀態
    int iLine,iColumn;
    printf("第%d 種狀態為:\n",++iQueenNum);
    for(iLine=0;iLine<8;iLine++)
    {
    for(iColumn=0;iColumn<8;iColumn++)
    printf("%c ",Queen[iLine][iColumn]);
    printf("\n");
    }
    printf("\n\n");
    }
    //如果前次的皇后放置導致后面的放置無論如何都不能滿足要求,則回溯,重置
    Queen[i][iColumn]='*';
    a[iColumn]=0;
    b[i-iColumn+7]=0;
    c[i+iColumn]=0;
    }
    }
    }

    【程序員遞歸面試問題及解析】相關文章:

    程序員面試問題及答案10-08

    面試常見問題及回答技巧解析12-15

    常見的面試問題及答案解析11-06

    MBA提前批面試高頻問題及思路解析09-04

    英語面試問題大解析及情景對話09-13

    程序員面試常見問題12-09

    it程序員面試常見問題10-16

    關于機械類專業面試常見問題及解析面試11-05

    銀行招聘考試面試問題匯總及思路解析12-12

    經典面試問題解析01-02

    日韩激情