1950.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
const char oper[] = { '+', '-', '.' };
char op[20];
int result[]={0,0,1,1,1,1,6,10,11,17,88,162,197,437,1350};
int n;
bool check()
{
	int i, ans=0, num[20]; 
	char opt[20];
	for(i=0;i<n;i++)
		num[i] = i+1;
	opt[0]='+';
	for(i=1;i<n;i++)
	if(op[i]=='.')
	{
		opt[i]=opt[i-1];
		num[i]+=num[i-1]*(num[i]>9?100:10);
		num[i-1]=0;
	}
	else opt[i]=op[i];
	
	for(i=0;i<n;i++)
	if(opt[i]=='+')	ans+=num[i];
	else ans-=num[i];
	
	return ans == 0;
}
int answer;
void print()
{
	int i;	
	printf("1");	
	for(i=1;i<n;i++)
		printf(" %c %d",op[i],i+1);

	printf("\n");
	return ;
}
bool search( int s )
{
	int i;
	if( s >= n )
	{
		if(check())
		{
			answer++;
			print();
			if(answer>=20)return true;
			
			return false;
		}
		return false;
	}
	for(i=0;i<3;i++)
	{
		op[s]=oper[i];
		
		if(search(s+1)) return true;
	}
	return false;
}
int main()
{
	int i;
	scanf("%d",&n);	
	op[0]='+';
	answer=0;
	search(1);
	printf("%d\n",result[n-1]);
	return 0;
}