欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法设计——符号三角形(回溯)

程序员文章站 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;
}
相关标签: 算法设计 回溯