符号三角形实验报告.doc

符号三角形_实验报告1、 设计分析l 问题描述：在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。例如下图：由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。+ + - + - + + + - - - - + - + + + - - + + - - + - - - +l 设计思路： 解向量：用n元组x1:n表示符号三角形的第一行。Xi=1表示第一行第i个符号为“+”， Xi=0表示第一行第i个符号为“-”。 可行性约束函数：当前符号三角形所包含的“+”个数与“-”个数均不超过n*(n+1)/4 。无解的判断：n*(n+1)/2为奇数 。n=3时的符号三角形用完全二叉树表示的解空间。l 复杂度分析： 计算可行性约束需要O(n)时间，在最坏情况下有 O(2n)个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为 O(n2n)。#includeiostream using namespace std; typedef unsigned char uchar; char cc2=+,-; /便于输出 int n, /第一行符号总数 half, /全部符号总数一半 counter; /1计数，即“-”号计数 uchar *p; /符号存储空间 long sum; /符合条件的三角形计数 /t，第一行第t个符号 void Backtrace(int t) int i, j; if( t n ) /符号填充完毕 sum+; /打印符号 cout 第 sum 个:n; for(i=1; i=n; +i) for(j=1; ji; +j) cout ; for(j=1; j=n-i+1; +j) cout cc pij ; cout n; else for(i=0; i2; +i) p1t = i; /第一行第t个符号 counter += i; /“-”号统计 for(j=2; j=2时，可以运算出下面行的某些符号 pjt-j+1 = pj-1t-j+1pj-1t-j+2;/通过异或运算下行符号 counter += pjt-j+1; 2、 程序代码 if( (counter = half) & ( t*(t+1)/2 - counter = half) ) /若符号统计未超过半数，并且另一种符号也未超过半数 Backtrace(t+1); /在第一行增加下一个符号 /回溯，判断另一种符号情况 for(j=2; j=t; +j) counter -= pjt-j+1; counter -= i; int main() cout n; counter = 0; sum = 0; half = n*(n+1)/2; int i=0; if( half%2 = 0 ) /总数须为偶数，若为奇数则无解 half /= 2; p = new uchar *n+1; for(i=0; i=n; +i) pi = new ucharn+1; memset(pi, 0, sizeof(uchar)*(n+1); Backtrace(1); for(i=0; i=n; +i) delete pi; delete p; cout n总共 sum 个 endl; return 0; 三、测试用例4、 实验总结1、 基本上理解了回溯算法。回溯法的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包