欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

c++遞歸實(shí)現(xiàn)n皇后問題代碼(八皇后問題)

 更新時(shí)間:2013年12月25日 10:29:49   作者:  
c++遞歸實(shí)現(xiàn)n皇后問題代碼分享,大家參考使用吧

還是先來看看最基礎(chǔ)的8皇后問題:

在8X8格的國際象棋上擺放八個(gè)皇后,使其不能互相攻擊,即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上,問有多少種擺法。

擴(kuò)展到N皇后問題是一樣的。
一看,似乎要用到二維數(shù)組。其實(shí)不需要。一維數(shù)組就能判斷,比如Arr[i],就可以表示一個(gè)元素位于第i行第Arr[i]列——應(yīng)用廣泛的小技巧。而且在這里我們不用考慮去存儲(chǔ)整個(gè)矩陣,如果Arr[i]存在,那么我們?cè)诖蛴〉臅r(shí)候,打印到皇后位置的時(shí)候輸出1,非皇后位輸出0即可。

這種思路的實(shí)現(xiàn)方式網(wǎng)上大把,包括前面提到的那位同學(xué),所以也就不要糾結(jié)有沒有改善有沒有提高之類的了,權(quán)當(dāng)一次練習(xí)即可。

直接上代碼好了,覺得遞歸方法沒什么好說的,空間想想能力好一點(diǎn)兒很容易理解。明天有空再寫寫非遞歸實(shí)現(xiàn)吧。

復(fù)制代碼 代碼如下:

/*
 * NQueen.cpp
 *
 *  Created on: 2013年12月23日
 *      Author: nerohwang
 */
//形參rowCurrent表示當(dāng)前所到的行數(shù)
#include<iostream>
#include<fstream>
#include<iomanip>
#include<stdlib.h>
using namespace std;
bool Check(int rowCurrent,int *&NQueen);                         //判斷函數(shù)
void Print(ofstream &os,int n,int *&NQueen);                                  //打印函數(shù)
void Solve(int rowCurrent,int *&NQueen,int n,int &count, ofstream &os);           //N皇后問題處理函數(shù),index一般初值為0


//判斷函數(shù),凡是橫豎有沖突,或是斜線上有沖突,返回FALSE
bool Check(int rowCurrent,int *&NQueen)
{
    int i = 0;
    while(i < rowCurrent)
    {
        if(NQueen[i] == NQueen[rowCurrent] || (abs(NQueen[i]-NQueen[rowCurrent]) == abs(i-rowCurrent)) )
        {
            return false;
        }
        i++;
    }
    return true;
}

//將所有可能出現(xiàn)的結(jié)果輸出文本文檔
void Print(ofstream &os,int n,int *&NQueen)
{
    os<<"一次調(diào)用\n";
    for (int i = 0;i < n;i++) {
        for(int j = 0 ; j < n; j++)
        {
            os<<(NQueen[i]==j?1:0);
            os<<setw(2);
        }
        os<<"\n";
    }
    os<<"\n";
}

//核心函數(shù)。遞歸解決N皇后問題,觸底則進(jìn)行打印
void Solve(int rowCurrent,int *&NQueen,int n,int &count, ofstream &os)
{
    if(rowCurrent == n)  //當(dāng)前行數(shù)觸底,即完成了一個(gè)矩陣,將它輸出
    {
        Print(os,n,NQueen);
        count++;
    }
    for(int i = 0;  i < n; i++)
    {
        NQueen[rowCurrent] = i;                     //row行i列試一試
        if(Check(rowCurrent,NQueen))
        {
            Solve(rowCurrent+1,NQueen,n,count,os);  //移向下一行
        }
    }
}

int main()
{
    int n;           //問題規(guī)模
    int count = 0;   //解的計(jì)數(shù)
    cout<<"請(qǐng)輸入問題的規(guī)模N"<<endl;
    cin>>n;
    if(n<4)
    {
        cerr<<"問題規(guī)模必須大于4"<<endl;
        return 0;
    }
    int *NQueen = new int[n];
    ofstream os;
    os.open("result.txt");
    Solve(0,NQueen,n,count,os);
    cout<<"問題的解有"<<count<<"種方法"<<endl;
    os.close();
    return 0;
}

相關(guān)文章

  • C++和java設(shè)計(jì)模式之單例模式

    C++和java設(shè)計(jì)模式之單例模式

    這篇文章主要為大家詳細(xì)介紹了C++和java設(shè)計(jì)模式之單例模式的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2016-12-12
  • C語言實(shí)現(xiàn)飛機(jī)售票系統(tǒng)

    C語言實(shí)現(xiàn)飛機(jī)售票系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)飛機(jī)售票系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-05-05
  • C++語言實(shí)現(xiàn)hash表詳解及實(shí)例代碼

    C++語言實(shí)現(xiàn)hash表詳解及實(shí)例代碼

    這篇文章主要介紹了C++語言實(shí)現(xiàn)hash表詳解及實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下
    2017-01-01
  • C/C++實(shí)現(xiàn)跨文件共享全局變量詳解

    C/C++實(shí)現(xiàn)跨文件共享全局變量詳解

    這篇文章主要為大家詳細(xì)介紹了C/C++如何實(shí)現(xiàn)跨文件共享全局變量,文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2024-01-01
  • Cocos2d-x UI開發(fā)之文本類使用實(shí)例

    Cocos2d-x UI開發(fā)之文本類使用實(shí)例

    這篇文章主要介紹了Cocos2d-x學(xué)習(xí)筆記之文本類,文本類是UI開發(fā)中經(jīng)常使用的,本文用詳細(xì)的代碼注釋講解了文本類的使用,需要的朋友可以參考下
    2014-09-09
  • C++中protobuf?的交叉編譯使用詳解

    C++中protobuf?的交叉編譯使用詳解

    為了提高通信效率,可以采用?protobuf?替代?XML?和?Json?數(shù)據(jù)交互格式,protobuf?相對(duì)來說數(shù)據(jù)量小,在進(jìn)程間通信或者設(shè)備之間通信能夠提高通信速率。下面介紹?protobuf?在?ARM?平臺(tái)上的使用,需要的朋友可以參考下
    2022-07-07
  • 淺談C++/C關(guān)于#define的那些奇奇怪怪的用法

    淺談C++/C關(guān)于#define的那些奇奇怪怪的用法

    本文主要介紹了C++/C關(guān)于#define的那些奇奇怪怪的用法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-07-07
  • QT使用SQLite數(shù)據(jù)庫超詳細(xì)教程(增刪改查、對(duì)大量數(shù)據(jù)快速存儲(chǔ)和更新)

    QT使用SQLite數(shù)據(jù)庫超詳細(xì)教程(增刪改查、對(duì)大量數(shù)據(jù)快速存儲(chǔ)和更新)

    這篇文章主要給大家介紹了關(guān)于QT使用SQLite數(shù)據(jù)庫的相關(guān)資料,其中包括增刪改查以及對(duì)大量數(shù)據(jù)快速存儲(chǔ)和更新,SQLite是一種嵌入式關(guān)系型數(shù)據(jù)庫管理系統(tǒng),它是一個(gè)軟件庫,提供了一個(gè)自包含、無服務(wù)器、零配置的、事務(wù)性的SQL數(shù)據(jù)庫引擎,需要的朋友可以參考下
    2024-01-01
  • 基于C++ Lambda表達(dá)式的程序優(yōu)化

    基于C++ Lambda表達(dá)式的程序優(yōu)化

    這篇文章主要介紹了基于C++ Lambda表達(dá)式的程序優(yōu)化的相關(guān)資料,非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友可以參考下
    2017-02-02
  • 對(duì)比C語言中g(shù)etc()函數(shù)和ungetc()函數(shù)的使用

    對(duì)比C語言中g(shù)etc()函數(shù)和ungetc()函數(shù)的使用

    這篇文章主要介紹了對(duì)比C語言中g(shù)etc()函數(shù)和ungetc()函數(shù)的使用,是C語言入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下
    2015-08-08

最新評(píng)論