文档介绍：实验报告
实验目的:
通过分析求符号三角形问题的回溯法并编程实现,掌握回溯法的算法框架。
实验任务:
分析求符号三角形问题的回溯算法,编程实现,调试运行程序并对运行结果进行分析,分析算法的时空复杂度。
实验内容:
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 puter(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