回溯算法的实验报告

南华大学

计算机科学与技术学院

实 验 报 告

（ 2016 ~2017 学年度 第 二 学期 ）

课程名称 程序设计语言与编译

实验名称 回溯算法分析

姓名 何星佑

学号 20154340220

专业 树媒

班级 2

地点

教师 罗江琴

一、 实验目的：

通过分析求符号三角形问题的回溯法并编程实现，掌握回溯法的算法框架。 二、 实验任务：

分析求符号三角形问题的回溯算法，编程实现，调试运行程序并对运行结果进行分析，分析算法的时空复杂度。 三、 实验内容：

1、实现回溯法求符号三角形问题描述 2、算法描述 3、程序设计

四、 实验结果与分析：

问题描述:

一般情况下，符号三角形的第一行有n个符号，三角形中任意位置都为“+”或“-”，且满足以下两个规则： 1）三角形中任意行的下一行的符号由以下规则确定：2个同号下面是“+”，2个异号下面是“-”；

2）三角形中“+”或“-”数目相同。

对于给定的n，计算有多少个不同的符号三角形。

问题分析：

对于符号三角形问题，用n元组x[1：n]表示符号三角形的第一行的n个符号。当x[i]=1时，表示符号三角形的第一行的第i个符号为“+”号；当x[i]=0时，表示符号三角形的第一行的第i个符号为“-”号；1 ≤ i≤ n。由于x[i]是二值的，所以在用回溯法解符号三角形问题时，可以用一棵完全二叉树来表示其解空间。在符号三角形的第一行的前i个符号x[1：i ]确定后，就确定了一个由i*（i+1）/2个符号组成的符号三角形。下一步确定了x[i+1]的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为x[1：i+1]所相应的符号三角形。最终由x[1：n]所确定的符号三角形中包含的“+”号个数与“-”号个数同为n*（n+1）/4。因此在回溯搜索过程中可用当前符号三角形所包含的“+”号个数与“-”号个数均不超过n*（n+1）/4作为可行性约束，用于剪去不满足约束的子树。对于给定的n，当n*（n+1）/2为奇数时，显然不存在所包含的“+”号个数与“-”

号个数相同的符号三角形。

程序代码：

#include class Triangle {

friend int Computer(int n); public:

void Backtrack(int t);

int n, //第一行的符号个数

half, //每个三角形总符号数的一半 count, //统减号的个数

**p; //指向三角形的二维指针 long sum; //统计符合条件的的三角形的个数 };

void Triangle::Backtrack(int t) {

if ((count>half)||(t*(t-1)/2-count>half))

{ return; // 如果加号或减号的个数大于符号三角形中总符号数的一半则退出函数 }

if (t>n) //符号填充完毕 { nsum++; //打印符号

for (int i = 1;i<=n;i++) //第i行

{ for (int k = i;k>=0;k--) //先输出必要的空格 {

cout<<' '; } for (int j = 1;j<=n-i+1;j++) //输出符号三角形第i行第i-1+k个位置

{

if (p[i][j] == 0) //如果该位为0,输出“+” {

cout<<\"+ \";

} else

{ if (p[i][j] == 1) //如果该位为1,输出“-”

}

{ cout<<\"- \";

} else

} } }

cout<for (int i = 0;i<2;i++) {

p[1][t] = i; //确定该位置的符号

count += i; //若该位置为减号，则减号数增1,否则，减号数不变 for (int j = 2;j<=t;j++) //因第t个位置确定，对应三角形的该斜行可以确定 {

p[j][t-j+1] = p[j-1][t-j+1]^p[j-1][t-j+2]; //通过异或运算下行符号

count += p[j][t-j+1]; //减号数 }

Backtrack(t+1); //对第一行的第t+1个位置进行回溯算法 for (j = 2;j<=t;j++) //回溯，减去该斜行的减号数 {

count -= p[j][t-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; //如果是一个三角形符号的总数是奇数则不符合条件，返回0

}

}

X.half = X.half/2;

int **p = new int*[n+1]; //分配新行

for(int i = 0;i<=n;i++) p[i] = new int [n+1]; //分配新列 for(i = 0;i<=n;i++)

for(int j = 0;j<=n;j++)

p[i][j] = 0; //给p所指向的二维数组赋值为0 X.p = p;

X.Backtrack(1); return X.sum;

void main() {

int n; //第一行的符号数

cout<<\"请输入第一行符号个数\"<>n;

int sum = Computer(n); cout<if (sum == 0)//符合条件的的三角形的个数=0 { }

cout<<\"不存在！\"<cout<