标题    
构造表达式

类别    
综合

时间限制    
1S

内存限制    
100Kb

问题描述    
给定一个表示序列长度的整数n（3<=n<=9)。在序列1 2 3…n中插入‘＋’，‘－’，‘ ’构造表达式，插入‘ ’表示前后两个数字构成一个整数，例如1 2 -3 -4 -5=0。
输出构造的所有表达式中，结果为0的表达式的数量，例如n=3时，只有表达式1+2-3=0，输出结果为1。

输入说明    
输入数据为一个整数n（n<10），表示序列长度，同时表示输入序列为“1 2 3…n”。

输出说明    
对于每一组数据，输出一个整数，表示构造的表达式中结果为0的表达式数量。

输入样例    
3

输出样例    
1

一开始看到这题完全无从下手，只能在CSDN上搜一波，确实看到了很多大佬的高端解法，学到了很多好的思路和想法。

针对这道题，个人认为三进制数的解法比较好，之前也有大佬打过这个思路，但身为菜鸟看了半天才弄明白，所以自己研究了一下最平民的打法。话不多说，剩下的看代码

#include<stdio.h>
//核心思想：手动生成三进制数，0代表空格，1代表'+',2代表'-'，穷举所有情况，统计解的个数 
int main(void)
{
	int n;
	scanf("%d",&n);//输入n 
	
	int a[n-1],b[20];//b数组为1到n这n个数，a数组用来存储生成的三进制数。 
	int i;
	
	for(i=0;i<n-1;i++){
		a[i]=0;
	} //给a数组赋初值 
	
	int max=1;
	for(i=0;i<n-1;i++){
		max=max*3;
	}//为生成三进制数做准备 
	
	int j,t,k,h,ans=0,temlong1,temlong2;
	for(i=0;i<max;i++){
		t=i;
		for(j=0;j<n-1;j++){
			a[j]=t%3;
			t=t/3;
		}//a数组中存入生成的三进制数 
		
		for(j=0;j<19;j++){
			b[j]=j+1;
		}//给b数组赋初值 
		
		temlong1=n;
		temlong2=n-1;
		for(k=0;k<temlong2;k++){
			if(a[k]==0){
				b[k]=b[k]*10+b[k+1];
				for(h=k+1;h<temlong1-1;h++){
				b[h]=b[h+1];
				}
				temlong1--;
				for(h=k;h<temlong2-1;h++){
					a[h]=a[h+1];
				}
				temlong2--;
				k--;
			}
		}//先处理所有空格，让a，b两个数组更“好起来”：a数组中删除所有0的同时b数组中做相应合并操作 
 
		for(k=0;k<temlong2;k++){
			a[0]=a[k];
			b[1]=b[k+1];
			if(a[0]==1){
				b[0]=b[0]+b[1];
			}else{
				b[0]=b[0]-b[1];
			}
		}//这一步就相对简单了，该加的时候加，该减的时候减 
		if(b[0]==0)ans++;//如果能成功，结果+1； 
	} 
	printf("%d",ans);//最后输出(Finished!!!) 
	return 0;
}