POJ1950总结

Dessert

题目来源

Description

FJ has a new rule about the cows lining up for dinner. Not only must the N (3 <= N <= 15) cows line up for dinner in order, but they must place a napkin between each pair of cows with a “+”, “-“, or “.” on it. In order to earn their dessert, the cow numbers and the napkins must form a numerical expression that evaluates to 0. The napkin with a “.” enables the cows to build bigger numbers. Consider this equation for seven cows:

      1 - 2 . 3 - 4 . 5 + 6 . 7

This means 1-23-45+67, which evaluates to 0. You job is to assist the cows in getting dessert. (Note: “… 10 . 11 …”) will use the number 1011 in its calculation.)

Input

One line with a single integer, N

Output

One line of output for each of the first 20 possible expressions — then a line with a single integer that is the total number of possible answers. Each expression line has the general format of number, space, napkin, space, number, space, napkin, etc. etc. The output order is lexicographic, with “+” coming before “-” coming before “.”. If fewer than 20 expressions can be formed, print all of the expressions.

Sample Input

7

Sample Output

1 + 2 - 3 + 4 - 5 - 6 + 7
1 + 2 - 3 - 4 + 5 + 6 - 7
1 - 2 + 3 + 4 - 5 + 6 - 7
1 - 2 - 3 - 4 - 5 + 6 + 7
1 - 2 . 3 + 4 + 5 + 6 + 7
1 - 2 . 3 - 4 . 5 + 6 . 7
6

我的代码

暴力出所有符号的可能性很简单，需要处理的的是计算式子结果和剪枝。

我的计算方法是保留上一次的计算数和运算符，根据当前的运算符来选择计算行为：如果当前的运算符是加或者减，就将当前运算数和上一次的运算数进行运算，结果保留在上一次的运算数中，同时本次的运算符赋值给上一次的运算符；如果是’.’号，就将这一次的运算数和下一次的运算数进行运算，结果保留在这一次的运算数中，其余不变。描述起来很费劲，代码如下：

for (int i=0;i<3;i++){
			opes[step]=ope[i];
			if (i<2){
				dfs(caculate(preNum,nowNum,preOpe),step+2,step+1,ope[i]);
			}else{
				dfs(preNum,caculate(nowNum,step+2,ope[i]),step+1,preOpe);
			}
		}

这一题如果不剪枝的话有不小的概率会超时，剪枝的策略是如果有一个运算数已经大于10的9次方了，那么显然这种情况也凑不成0了。

另外我一开始是先找出所有运算符的可能，在一次性算出式子的值，最后发现超时了。后来才改成边搜索边计算，用时居然只有几十ms。

#include<stdio.h>

const char ope[3]={'+','-','.'};
int n,ans;
char opes[20];

int caculate(int a,int b,char o){
	switch(o){
		case '+':
			return a+b;
		case '-':
			return a-b;
		case '.':
			if(b>=10){
				return a*100+b;
			}else{
				return a*10+b;
			}
			
	}
}

//int caculateAll(){
//	long long int preNum=0,nowNum=1;
//	char preOpe='+';
//	for (int i=0;i<n-1;i++){
//		if (opes[i]=='+'||opes[i]=='-'){
//			preNum=caculate(preNum,nowNum,preOpe);
//			nowNum=i+2;
//			preOpe=opes[i];
//		}else{
//			nowNum=caculate(nowNum,i+2,'.');
//		}
//	}
//	return caculate(preNum,nowNum,preOpe);
//}

void print(){
	for (int i=1;i<=4*n-3;i++){
		if (i%2==0){
			printf(" ");
		}else{
			if (i%4==1){
				printf("%d",i/4+1);
			}else if (i%4==3){
				printf("%c",opes[i/4]);
			}
		}
	}
	printf("\n");
}

void dfs(int preNum,int nowNum,int step,char preOpe){
	if (step==n-1){
		if (caculate(preNum,nowNum,preOpe)==0){
			ans++;
			if (ans<=20){
				print();
			}
		}
	}else{
		if (preNum>100000000||nowNum>100000000) return;
		for (int i=0;i<3;i++){
			opes[step]=ope[i];
			if (i<2){
				dfs(caculate(preNum,nowNum,preOpe),step+2,step+1,ope[i]);
			}else{
				dfs(preNum,caculate(nowNum,step+2,ope[i]),step+1,preOpe);
			}
		}
	}
}

int main()
{
	ans=0;
	scanf("%d",&n);
	dfs(0,1,0,'+');
	printf("%d\n",ans);
	return 0;
}