今天我們繼續(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è)方向增長(如:高地址 --> 低地址);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 的國際棋盤上,有 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ù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案,具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì),專為企業(yè)上云打造定制,能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
分享題目:遞歸思想及應(yīng)用續(xù)(二十九)-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于:http://bm7419.com/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)
猜你還喜歡下面的內(nèi)容