回溯算法的实验报告.doc

实 验 报 告一、 实验目的： 通过分析求符号三角形问题的回溯法并编程实现，掌握回溯法的算法框架。二、 实验任务： 分析求符号三角形问题的回溯算法，编程实现，调试运行程序并对运行结果进行分析，分析算法的时空复杂度。三、 实验内容：1、实现回溯法求符号三角形问题描述2、算法描述3、程序设计四、 实验结果与分析：问题描述: 一般情况下，符号三角形的第一行有n个符号，三角形中任意位置都为“+”或“-”，且满足以下两个规则： 1）三角形中任意行的下一行的符号由以下规则确定：2个同号下面是“+”，2个异号下面是“-”； 2）三角形中“+”或“-”数目相同。对于给定的n，计算有多少个不同的符号三角形。问题分析：对于符号三角形问题，用n元组x1：n表示符号三角形的第一行的n个符号。当xi=1时，表示符号三角形的第一行的第i个符号为“+”号；当xi=0时，表示符号三角形的第一行的第i个符号为“-”号；1 i n。由于xi是二值的，所以在用回溯法解符号三角形问题时，可以用一棵完全二叉树来表示其解空间。在符号三角形的第一行的前i个符号x1：i 确定后，就确定了一个由i*（i+1）/2个符号组成的符号三角形。下一步确定了xi+1的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为x1：i+1所相应的符号三角形。最终由x1：n所确定的符号三角形中包含的“+”号个数与“-”号个数同为n*（n+1）/4。因此在回溯搜索过程中可用当前符号三角形所包含的“+”号个数与“-”号个数均不超过n*（n+1）/4作为可行性约束，用于剪去不满足约束的子树。对于给定的n，当n*（n+1）/2为奇数时，显然不存在所包含的“+”号个数与“-”号个数相同的符号三角形。 程序代码：#include class Trianglefriend int Computer(int n);public:void Backtrack(int t);int n, /第一行的符号个数half, /每个三角形总符号数的一半count, /统减号的个数*p; /指向三角形的二维指针long sum; /统计符合条件的的三角形的个数;void Triangle:Backtrack(int t)if (counthalf)|(t*(t-1)/2-counthalf) return; / 如果加号或减号的个数大于符号三角形中总符号数的一半则退出函数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 = 1) /如果该位为1,输出“-” cout- ;coutendl;elsefor (int i = 0;i2;i+)p1t = i; /确定该位置的符号count += i; /若该位置为减号，则减号数增1,否则，减号数不变for (int j = 2;j=t;j+) /因第t个位置确定，对应三角形的该斜行可以确定pjt-j+1 = pj-1t-j+1pj-1t-j+2; /通过异或运算下行符号count += pjt-j+1; /减号数Backtrack(t+1); /对第一行的第t+1个位置进行回溯算法for (j = 2;j=t;j+) /回溯，减去该斜行的减号数count -= pjt-j+1;count -= i; /减去第一行第t个位置的减号数int Computer(int n) /友元函数 调用Triangle类的成员函数Triangle X;X.n = n;X.count = 0;X.sum = 0;X.half = n*(n+1)/2;if (X.half%2 = 1)return 0; /如果是一个三角形符号的总数是奇数则不符合条件，返回0X.half = X.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所指向的二维数组赋值为0X.p = p;X.Backtrack(1);return X.sum;void main()int n; /第一行的符号数cout请