算法-遞歸與分治

1、實(shí)驗(yàn) 遞歸與分治策略應(yīng)用基礎(chǔ)一、實(shí)驗(yàn)?zāi)康? 、理解遞歸的概念和分治法的基本思想2、了解適用遞歸與分治策略的問題類型，并能設(shè)計(jì)相應(yīng)的分治策略算法3、掌握遞歸與分治算法時(shí)間空間復(fù)雜度分析，以及問題復(fù)雜性分析方法二、實(shí)驗(yàn)內(nèi)容任務(wù)：以下題目要求應(yīng)用遞歸與分治策略設(shè)計(jì)解決方案，1、求n 個(gè)元素的全排。2、解決一個(gè)2k*2 k的特殊棋牌上的L型骨牌覆蓋問題。提交結(jié)果：算法設(shè)計(jì)分析思路、源代碼及其分析說明和測(cè)試運(yùn)行報(bào)告。三、設(shè)計(jì)分析設(shè) R=r1,r2,.,rn是要進(jìn)行排列的 n 個(gè)元素， Ri=R-ri 。集合 X 中元素的全排列記為Perm(X)。(ri)Perm(X)表示在全排列Perm(X)的每一個(gè)排

2、列前加上前綴 ri 得到的排列。 R 的全排列可以歸納定義如下:當(dāng) n=1 時(shí)， Perm(R)=(r), 其中 r 是集合 R 中唯一的元素；當(dāng) n1 時(shí)，Perm(R)由(U)Perm(R1),(r2)Perm(R2),(rn)Perm(Rn)構(gòu)成。依次遞歸定義，可設(shè)計(jì)產(chǎn)生Perm(R)的遞歸算法?？梢杂靡粋€(gè)L 型骨牌覆蓋3 個(gè)無(wú)特殊方格的較小棋盤的會(huì)合處，從而將原問題轉(zhuǎn)化為 4 個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡(jiǎn)化為 1*1 棋盤。四、算法描述及程序 題目一：/ 排列問題 .cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/#include stdafx.h#include

3、 iostream using namespace std;templatevoid Perm(T list,int k,int m)if(k=m)for(int i=0;i=m;i+) coutlistit;coutendl;elsefor(int i=k;i=m;i+)Swap(listk,listi);Perm(list,k+1,m);Swap(listk,listi);templateinline void Swap(T&a,T&b)T temp=a;a=b;b=temp;int main()int a4;printf( 請(qǐng)輸入 4 個(gè)整數(shù) :);for(int i=0;i4;i+)

4、scanf_s(%d,&ai);Perm(a,0,3);double b3;printf( 請(qǐng)輸入 3 個(gè)小數(shù) :);for(int i=0;i3;i+)scanf_s(%lf,&bi);Perm(b,0,2);return 0;題目二：/ 棋盤覆蓋 .cpp :定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/#include stdafx.h#include iostream#define N 4using namespace std;int BoardNN;static int tem = 0;void ChessBoard(int tr, int tc, int dr, int dc, int size)

5、if (size = 1)return;tem+;int t = tem;int s = size / 2;if (drtr + s&dctc + s) ChessBoard(tr, tc, dr, dc, s);elsecout 第 tr + s - 1 行第 tc + s - 1 列被 t 號(hào) L 型 骨牌左上角覆蓋 endl endl;Boardtr + s - 1tc + s - 1 = t;ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);if (dr= tc + s)ChessBoard(tr, tc + s, dr, dc, s);els

6、ecout 第 tr + s - 1 行第 tc + s 列被 t 號(hào) L 型骨牌右上角覆蓋 endl = tr + s&dctc + s)ChessBoard(tr + s, tc, dr, dc, s);elsecout 第 tr + s 行第 tc + s - 1 列被 t 號(hào) L 型骨 牌左下角覆蓋 endl = tr + s&dc = tc + s)ChessBoard(tr + s, tc + s, dr, dc, s);elsecout 第 tr + s 行第 tc + s 列被vv t ”號(hào) L 型骨牌 右下角覆蓋 endl endl;Boardtr + stc + s = t;ChessBoard(tr + s, tc + s, tr + s, tc + s, s);)int main()int i, j;cout N * N 棋盤 endl;cout 請(qǐng)輸入特殊方塊所在的行和列 (0=i vv N ,0v=jv vv N i j;cout vv endl vv endl;ChessBoard(0, 0, i, j, N);for (int i = 0; ivN; i+)for (int j = 0; jvN; j+)cout vv Boardij vv t;)cout vv endl vv endl;)r