遞歸思想及應(yīng)用續(xù)（二十九）-創(chuàng)新互聯(lián)

    今天我們繼續(xù)來學(xué)習(xí)遞歸，下來我們先來回顧下函數(shù)的調(diào)用過程：在程序運(yùn)行后有一個(gè)特殊的內(nèi)存區(qū)供函數(shù)調(diào)用使用。那么這個(gè)內(nèi)存區(qū)有什么用呢？1、用于保存函數(shù)中的實(shí)參，局部變量，臨時(shí)變量等；2、從起始地址開始往一個(gè)方向增長(zhǎng)（如：高地址 --> 低地址）；3、有一個(gè)專用“指針”標(biāo)識(shí)當(dāng)前已使用內(nèi)存的“頂部”。

鳳縣網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián)公司,鳳縣網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為鳳縣上千家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站制作要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的鳳縣做網(wǎng)站的公司定做！

        那么程序中的棧區(qū)，就是一段特殊的專用內(nèi)存區(qū)。如下圖所示

        下來我們來看一個(gè)示例：逆序打印單鏈表中的偶數(shù)結(jié)點(diǎn)。如下所示

        下來我們來看看具體源碼是怎么實(shí)現(xiàn)的，如下

#include <iostream>#include <cstring>
#include "DTString.h"
#include "LinkList.h"

using namespace std;
using namespace DTLib;

struct Node
{
    int value;
    Node* next;
};

Node* create_list(int v, int len)
{
    Node* ret = NULL;
    Node* slider = NULL;

    for(int i=0; i<len; i++)
    {
        Node* n = new Node();

        n->value = v++;
        n->next = NULL;

        if( slider == NULL )
        {
            slider = n;
            ret = n;
        }
        else
        {
            slider->next = n;
            slider = n;
        }
    }

    return ret;
}

void destory_list(Node* list)
{
    while( list )
    {
        Node* del = list;

        list = list->next;

        delete del;
    }
}

void print_list(Node* list)
{
    while( list )
    {
        cout << list->value << "->";

        list = list->next;
    }

    cout << "NULL" << endl;
}

void r_print_even(Node* list)
{
    if( list != NULL )
    {
        r_print_even(list->next);

        if( (list->value % 2) == 0)
        {
            cout << list->value << endl;
        }
    }
}

int main()
{
    Node* list = create_list(2, 5);

    print_list(list);

    r_print_even(list);

    return 0;
}

        我們來看看運(yùn)行結(jié)果

        我們看到已經(jīng)實(shí)現(xiàn)了這個(gè)功能。

        下來我們來看看著名的“八皇后”問題，那么什么是八皇后問題呢？在一個(gè) 8×8 的國(guó)際棋盤上，有 8 個(gè)皇后，每個(gè)皇后占一格；要求皇后間不會(huì)出現(xiàn)相互“***”的現(xiàn)象（不能有兩個(gè)皇后處于同一行、同一列或同一對(duì)角線上）。

        那么實(shí)現(xiàn)的關(guān)鍵是什么呢？我們先來看看關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)定義：

        1、棋盤，它便是用一個(gè)二維數(shù)組（10*10），0表示位置為空，1表示皇后，2表示邊界；

        2、位置，struct Pos。

            struct Pos

            {

                int x；

                int y；

            }

        3、方向：

            水平：（-1，0），（1，0）

            垂直：（0，-1），（0，1）

            對(duì)角線：（-1，1），（-1，-1），（1，-1），（1，1）

       其中的算法思路：

            1、初始化：j = 1

            2、初始化：i = 1

            3、從第 j 行開始，恢復(fù) i 的有效值（通過函數(shù)調(diào)用棧進(jìn)行回溯），判斷第 i 個(gè)位置

                a. 位置 i 可放入皇后：標(biāo)記位置（i，j），j++，轉(zhuǎn)步驟 2

                b. 位置 i 不可放入皇后：i++，轉(zhuǎn)步驟 a

                c. 當(dāng) i > 8 時(shí)，j--，轉(zhuǎn)步驟 3

            -- 結(jié)束：第 8 行有位置可放入皇后。

       下來我們來看看具體的源碼實(shí)現(xiàn)，如下

#include <iostream>
#include <cstring>
#include "DTString.h"
#include "LinkList.h"

using namespace std;
using namespace DTLib;

template < int SIZE >
class QueueSolution : public Object
{
protected:
    enum { N = SIZE + 2 };

    struct Pos : public Object
    {
        Pos(int px = 0, int py = 0) : x(px), y(py) { }
        int x;
        int y;
    };

    int m_chessboard[N][N];
    Pos m_direction[3];
    LinkList<Pos> m_solution;
    int m_count;

    void init()
    {
        m_count = 0;

        for(int i=0; i<N; i+=(N-1))
        {
            for(int j=0; j<N; j++)
            {
                m_chessboard[i][j] = 2;
                m_chessboard[j][i] = 2;
            }
        }

        for(int i=1; i<=SIZE; i++)
        {
            for(int j=1; j<=SIZE; j++)
            {
                m_chessboard[i][j] = 0;
            }
        }

        m_direction[0].x = -1;
        m_direction[0].y = -1;
        m_direction[1].x = 0;
        m_direction[1].y = -1;
        m_direction[2].x = 1;
        m_direction[2].y = -1;
    }

    void print()
    {
        for(m_solution.move(0); !m_solution.end(); m_solution.next())
        {
            cout << "(" << m_solution.current().x << ", " << m_solution.current().y << ") ";
        }

        cout << endl;

        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                switch (m_chessboard[i][j])
                {
                    case 0: cout << " "; break;
                    case 1: cout << "#"; break;
                    case 2: cout << "*"; break;
                }
            }

            cout << endl;
        }

        cout << endl;
    }

    bool check(int x, int y, int d)
    {
        bool flag = true;

        do
        {
            x += m_direction[d].x;
            y += m_direction[d].y;
            flag = flag && (m_chessboard[x][y] == 0);
        }
        while( flag );

        return (m_chessboard[x][y] == 2);
    }

    void run(int j)
    {
        if( j <= SIZE )
        {
            for(int i=1; i<=SIZE; i++)
            {
                if( check(i, j, 0) && check(i, j, 1) && check(i, j, 2) )
                {
                    m_chessboard[i][j] = 1;

                    m_solution.insert(Pos(i, j));

                    run(j + 1);

                    m_chessboard[i][j] = 0;

                    m_solution.remove(m_solution.length() - 1);
                }
            }
        }
        else
        {
            m_count++;

            print();
        }
    }

public:
    QueueSolution()
    {
        init();
    }

    void run()
    {
        run(1);

        cout << "Total: " << m_count << endl;
    }
};

int main()
{
    QueueSolution<8> qs;

    qs.run();

    return 0;
}

        我們來看看運(yùn)行結(jié)果

        我們看到總共有 92 種解法。我們來看看四皇后，看看有多少種解法

        我們看到總共有 2 種解法，如上圖所示。通過今天對(duì)遞歸的學(xué)習(xí)，總結(jié)如下：1、程序運(yùn)行后的棧存儲(chǔ)區(qū)專供函數(shù)調(diào)用使用；2、棧存儲(chǔ)區(qū)用于保存實(shí)參，局部變量，臨時(shí)變量等；3、利用棧存儲(chǔ)區(qū)能夠方便的實(shí)現(xiàn)回溯算法；4、八皇后問題是?；厮莸慕?jīng)典應(yīng)用。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享題目：遞歸思想及應(yīng)用續(xù)（二十九）-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://muchs.cn/article46/dscpeg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、外貿(mào)網(wǎng)站建設(shè)、服務(wù)器托管、手機(jī)網(wǎng)站建設(shè)、域名注冊(cè)、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)