算法设计——符号三角形(回溯)
程序员文章站
2022-04-01 11:22:05
...
问题
给定第一行的符号(只有+,-)数目n,每行比上一行数目少一(形成一个倒三角),2个相同符号下面为“+”号,2个不同符号下面为“-”号,要求有多少种情况使得两种符号数目相同。
第一行为7的符号三角形之一:
分析
我们发现
由于只有两种符号,所以我们可简化为0、1形式
①总符号数为n(n+1)/2,如果总数为奇数,那么一定不可能符号数相等
②当某一符号数大于总数的一半时,那么此情况不存在解
代码实现
#include<stdio.h>
#define N 100
int n;
int cnt=0,sum=0;
int half;
int p[N][N]={0};
void backtrack(int t){
int j,i;
if(cnt>half||t*(t-1)/2-cnt>half) //符号大于一半时退出
return;
if(t>n){//到达叶结点
sum++;
return ;
}
for(i=0;i<2;i++){
p[1][t]=i;
cnt+=i;
for(j=2;j<=t;j++){//j层
p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];
cnt+=p[j][t-j+1];
}
backtrack(t+1);
for(j=2;j<=t;j++){
cnt-=p[j][t-j+1];
}
cnt-=i;
}
}
int main()
{
printf("请输入第一行符号个数:");
scanf("%d",&n);
half=n*(n+1)/2;//总的符号数
if(half%2==1) printf("结果为0个\n");
else {
half/=2;//最开始忘记除2 ,除以2才是真正的一半;
backtrack(1);
printf("结果为%d个\n",sum);
}
return 0;
}