深搜与回溯-符号三角形

问题描述

符号三角形的 第1行有n个由“+”和”-“组成的符号 ，以后每行符号比上行少1个，2个同号下面是”+“，2个异 号下面是”-“ 。计算有多少个不同的符号三角形，使其所含”+“ 和”-“ 的个数相同 ，并打印出所有的三角形。 n=7时的1个符号三角形如下:

+ + - + - + + 
+ - - - - + 
- + + + - 
- + + - 
- + - 
- -
+  

算法思考

1、用回溯法搜索二叉树并进行剪枝

对于符号三角形问题，用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作为可行性约束，用于剪去不满足约束的子树。

2、用压缩矩阵来存储符号三角形并进行输出

c[a][b]==p[(a*(2*n+1-a)/2+b)];

3、有效剪枝

王晓东书上133页的代码对每一次回溯都会将回溯到的符号三角形补全才进行剪枝，如下图：

但其实并不需要完全补全我们就可以进行剪枝（如果此时+或-的个数超过了n*（n+1）/4），此时需要对王晓东书上的回溯后的恢复那段代码也进行相应修改，因为王书上是直接删掉了新增的一行来进行恢复的，而如果我们并没有增加一到一行便对其回溯，会产生错误，需要对在第几行判断出不可行解进行记录。

代码实现

1、我的没有用到类的，可以记录个数并打印三角形的代码实现

#include <stdio.h>
#include <iostream>
using namespace std;
int n,m;
int sum=0;
int num=0;
inline int dingwei(int a,int b)
{
    //cout<<"ok:"<<(a*(2*n+1-a)/2+b)<<" ";
    return (a*(2*n+1-a)/2+b);
}
char fuhao(int a)
{
    if(a==0)
        return '+';
    else
        return '-';
}
bool ok(int a,int b,int *p,int &j)
{
    j=-1;
    sum+=b;
    p[dingwei(0,a)]=b;
    //cout<<"ok:"<<dingwei(0,a)<<fuhao(b)<<" "<<sum<<" ";
    if(sum>m || (a*(a+1)/2+1-sum)>m)
    {
        j=0;
        return false;
    }
    int i;
    for(i=1;i<=a;++i)
    {
        p[dingwei(i,a-i)]=p[dingwei(i-1,a-i)]^p[dingwei(i-1,a-i+1)];
        sum+=p[dingwei(i,a-i)];
        //cout<<"ok:"<<dingwei(i,a-i)<<fuhao(p[dingwei(i,a-i)])<<" "<<sum<<" ";
        if(sum>m || (a*(a+1)/2+i+1-sum)>m)
        {
            j=i;
            return false;
        }
    }
    return true;
}
void turnback(int a,int b,int *p,int j)
{
    int i;
    if(j==-1)
        j=a;
    for(i=0;i<=j;++i)
        sum-=p[dingwei(i,a-i)];
}
void out(int *p)
{
    int i,j,k;
    for(i=0;i<n;++i)
    {
        for(k=0;k<i;++k)
            cout<<" ";
        for(j=0;j<(n-i);++j)
        {
            if(p[dingwei(i,j)]==0)
                cout<<"+ ";
            else
                cout<<"- ";
        }
        cout<<endl;
    }
}
void work(int j,int *p)
{
    if(j==n)
    {
        num++;
        cout<<num<<":"<<endl;
        out(p);
    }
    else
    {
        int i,k;
        for(i=0;i<2;++i)
        {
            if(ok(j,i,p,k))
                work(j+1,p);
            turnback(j,i,p,k);
        }
    }
}
void init(int *p)
{
    int i;
    for(i=0;i<m;++i)
        p[i]=0;
}
int main()
{
 cout<<"please input the size of the problem: ";
    cin>>n;
    m=n*(n+1)/2;
    if(m%2)
        cout<<"0"<<endl;
    else
    {
        int *p=new int[m];
        init(p);
        m=m/2;
        work(0,p);
        delete [] p;
    }
    return 0;
}

2、来自网络的（本文来自来源于springxxc@163.com ，感谢Xiao Xiuchun的分享），注释很全的同样能打印三角形的一份代码（为了适应我的CODEBLOCK，个人做了一丁点的修改）

#include <iostream>
using namespace std;
class SymbolTriangle//定义符号三角形类
{
private:
    int n;//该三角形第一行符号总数
    int **p;//该三角形
    int half;//三角形符号总数的一半
    int numofMinus;//当前已确定位置中，减号的个数
    long sum;//符号三角形个数
    bool bExecuteThis;//是否已经执行回溯算法

public:
    SymbolTriangle(int refN=0);//构造函数

    int HalfofSymbol()//求解该三角形所有符号总数的一半
    {
        return n*(n+1)/4;
    }

    int isEvenSymbol()//判断三角形所有符号总数是否为偶数
    {
        return ~(n*(n+1)/2%2);
    }

    void PrintSymbolTriangle();//输出符号三角形

    void Backtrack(int t);//回溯算法

    void ShowNumofSymTri();//显示符号三角形的个数

    void ExecuteThisAlgorithm();//执行回溯算法
};

SymbolTriangle::SymbolTriangle(int refN)//构造函数
{
    n=refN;//设定该三角形第一行符号数目

    //为三角形分配内存空间
    p=new int*[n+1];
    int i;
    for(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;

    sum=0;//符号三角形个数初始化为0
    bExecuteThis=0;//标记位初始化为0，标记本算法尚未执行
    half=HalfofSymbol();//三角形符号总数的一半
    numofMinus=0;//当前已确定位置中，加号的个数初始化为0
}

void SymbolTriangle::PrintSymbolTriangle()//输出符号三角形
{
    for(int i=1;i<=n;i++)//第i行
    {
        for(int j=1;j<=i-1;j++)//先输出必要的空格
            cout<<" ";
        for(int k=1;k<=n-i+1;k++)//输出符号三角形第i行第i-1+k个位置
        {
            if(p[i][k]==0)//如果该位为0,输出“+”
                cout<<"+";
            else//如果该位为1,输出“-”
                cout<<"-";
            cout<<" ";
        }
        cout<<endl;
    }
}

void SymbolTriangle::ShowNumofSymTri()//显示符号三角形的个数
{
    if(bExecuteThis)
        cout<<"When n="<<n<<", the numble of symboltriangles is: "<<sum<<endl;
    else
        cout<<"You haven't execute our algorithm"<<endl;
}

void SymbolTriangle::Backtrack(int t)//回溯算法
{
    if((numofMinus>half)||(t*(t-1)/2-numofMinus>half))//加号或减号个数超过半数，则不可能存在符号三角形
        return;
    if(t>n)//确定第一行的第n个符号后，仍未出现加号或减号个数超过半数，则该次确定可形成符号三角形
    {
        sum++;//计数增1
        int temp=sum-sum/10*10;//序号值的个位数
        if(temp==1)
            cout<<"the "<<sum<<"st symboltriangle is:"<<endl;//
        else if(temp==2)
            cout<<"the "<<sum<<"nd symboltriangle is:"<<endl;//
        else if(temp==3)
            cout<<"the "<<sum<<"rd symboltriangle is:"<<endl;//
        else
            cout<<"the "<<sum<<"th symboltriangle is:"<<endl;//
        PrintSymbolTriangle();//输出所确定的符号三角形
    }
    else//尚未确定到最后一个位置的符号
        for(int i=0;i<2;i++)
        {
            p[1][t]=i;//确定该位置的符号
            numofMinus+=i;//若该位置为减号，则减号数增1,否则，减号数不变
            int j;
            for(j=2;j<=t;j++)//因第t个位置确定，对应三角形的该斜行可以确定
            {
                p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];//确定对应三角形的斜行
                numofMinus+=p[j][t-j+1];//减号数
            }
            Backtrack(t+1);//对第一行的第t+1个位置进行回溯算法
            for(j=2;j<=t;j++)//回溯，减去该斜行的减号数
            {
                numofMinus-=p[j][t-j+1];
            }
            numofMinus-=i;//减去第一行第t个位置的减号数
        }
}

void SymbolTriangle::ExecuteThisAlgorithm()//执行回溯算法
{
    bExecuteThis=1;//修改标记位，标记本算法已经执行过
    if(isEvenSymbol())//如果三角形的符号总数为奇数，则执行回溯法
        Backtrack(1);
}

int main()
{
    int size;//第一行的符号数
    cout<<"please input the size of the problem: ";
    cin>>size;
    SymbolTriangle ST1(size);//定义ST1为SymbolTriangle类对象
    ST1.ExecuteThisAlgorithm();//调用SymbolTriangle的函数执行回溯算法
    ST1.ShowNumofSymTri();//显示满足条件的符号三角形个数
    return 0;
}