回溯算法的實驗報告

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

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

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

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

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

6、j+1;count -= i; /減去第一行第t個位置的減號數(shù)int puter(int n) /友元函數(shù) 調用Triangle類的成員函數(shù)Triangle *;*.n = n;*.count = 0;*.sum = 0;*.half = n*(n+1)/2;if (*.half%2 = 1)return 0; /如果是一個三角形符號的總數(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; /第一行的符號數(shù)c