回溯算法的實(shí)驗(yàn)報(bào)告

1、-. z.南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院實(shí) 驗(yàn) 報(bào) 告 2016 2017 學(xué)年度 第 二 學(xué)期 課程名稱程序設(shè)計(jì)語言與編譯實(shí)驗(yàn)名稱回溯算法分析*何星佑*專業(yè)樹媒班級(jí)2地點(diǎn)教師羅江琴實(shí)驗(yàn)?zāi)康模?通過分析求符號(hào)三角形問題的回溯法并編程實(shí)現(xiàn)，掌握回溯法的算法框架。實(shí)驗(yàn)任務(wù)： 分析求符號(hào)三角形問題的回溯算法，編程實(shí)現(xiàn)，調(diào)試運(yùn)行程序并對運(yùn)行結(jié)果進(jìn)展分析，分析算法的時(shí)空復(fù)雜度。實(shí)驗(yàn)內(nèi)容：1、實(shí)現(xiàn)回溯法求符號(hào)三角形問題描述2、算法描述3、程序設(shè)計(jì)實(shí)驗(yàn)結(jié)果與分析：問題描述: 一般情況下，符號(hào)三角形的第一行有n個(gè)符號(hào)，三角形中任意位置都為+或-，且滿足以下兩個(gè)規(guī)則： 1三角形中任意行的下一行的符號(hào)由以下規(guī)則確定

2、：2個(gè)同號(hào)下面是+，2個(gè)異號(hào)下面是-； 2三角形中+或-數(shù)目一樣。對于給定的n，計(jì)算有多少個(gè)不同的符號(hào)三角形。問題分析：對于符號(hào)三角形問題，用n元組*1：n表示符號(hào)三角形的第一行的n個(gè)符號(hào)。當(dāng)*i=1時(shí)，表示符號(hào)三角形的第一行的第i個(gè)符號(hào)為+號(hào)；當(dāng)*i=0時(shí)，表示符號(hào)三角形的第一行的第i個(gè)符號(hào)為-號(hào)；1 i n。由于*i是二值的，所以在用回溯法解符號(hào)三角形問題時(shí)，可以用一棵完全二叉樹來表示其解空間。在符號(hào)三角形的第一行的前i個(gè)符號(hào)*1：i 確定后，就確定了一個(gè)由i*i+1/2個(gè)符號(hào)組成的符號(hào)三角形。下一步確定了*i+1的值后，只要在前面已確定的符號(hào)三角形的右邊加一條邊，就可以擴(kuò)展為*1：i+1

3、所相應(yīng)的符號(hào)三角形。最終由*1：n所確定的符號(hào)三角形中包含的+號(hào)個(gè)數(shù)與-號(hào)個(gè)數(shù)同為n*n+1/4。因此在回溯搜索過程中可用當(dāng)前符號(hào)三角形所包含的+號(hào)個(gè)數(shù)與-號(hào)個(gè)數(shù)均不超過n*n+1/4作為可行性約束，用于剪去不滿足約束的子樹。對于給定的n，當(dāng)n*n+1/2為奇數(shù)時(shí)，顯然不存在所包含的+號(hào)個(gè)數(shù)與-號(hào)個(gè)數(shù)一樣的符號(hào)三角形。 程序代碼：#include class Trianglefriend int puter(int n);public:void Backtrack(int t);int n, /第一行的符號(hào)個(gè)數(shù)half, /每個(gè)三角形總符號(hào)數(shù)的一半count, /統(tǒng)減號(hào)的個(gè)數(shù)*p; /指向三角

4、形的二維指針long sum; /統(tǒng)計(jì)符合條件的的三角形的個(gè)數(shù);void Triangle:Backtrack(int t)if (counthalf)|(t*(t-1)/2-counthalf) return; / 如果加號(hào)或減號(hào)的個(gè)數(shù)大于符號(hào)三角形中總符號(hào)數(shù)的一半則退出函數(shù)if (tn) /符號(hào)填充完畢 nsum+; /打印符號(hào)for (int i = 1;i=0;k-) /先輸出必要的空格 cout ;for (int j = 1;j=n-i+1;j+) /輸出符號(hào)三角形第i行第i-1+k個(gè)位置if (pij = 0) /如果該位為0,輸出+cout+ ; else if (pij =

5、1) /如果該位為1,輸出- cout- ;coutendl;elsefor (int i = 0;i2;i+)p1t = i; /確定該位置的符號(hào)count += i; /假設(shè)該位置為減號(hào)，則減號(hào)數(shù)增1,否則，減號(hào)數(shù)不變for (int j = 2;j=t;j+) /因第t個(gè)位置確定，對應(yīng)三角形的該斜行可以確定pjt-j+1 = pj-1t-j+1pj-1t-j+2; /通過異或運(yùn)算下行符號(hào)count += pjt-j+1; /減號(hào)數(shù)Backtrack(t+1); /對第一行的第t+1個(gè)位置進(jìn)展回溯算法for (j = 2;j=t;j+) /回溯，減去該斜行的減號(hào)數(shù)count -= pjt-

6、j+1;count -= i; /減去第一行第t個(gè)位置的減號(hào)數(shù)int puter(int n) /友元函數(shù) 調(diào)用Triangle類的成員函數(shù)Triangle *;*.n = n;*.count = 0;*.sum = 0;*.half = n*(n+1)/2;if (*.half%2 = 1)return 0; /如果是一個(gè)三角形符號(hào)的總數(shù)是奇數(shù)則不符合條件，返回0*.half = *.half/2;int *p = new int*n+1; /分配新行for(int i = 0;i=n;i+) pi = new int n+1; /分配新列for(i = 0;i=n;i+)for(int j = 0;j=n;j+)pij = 0; /給p所指向的二維數(shù)組賦值為0*.p = p;*.Backtrack(1);return *.sum;void main()int n; /第一行的符號(hào)數(shù)c