USACO 2.3.3 Zero Sum 深搜
Zero SumConsider the sequence of digits from 1 through N (where N=9) in increasing order: 1 2 3 ... N.
Now insert either a `+' for addition or a `-' for subtraction or a ` ' [blank] to run the digits together between each pair of digits (not in front of the first digit). Calculate the result that of the expression and see if you get zero.
Write a program that will find all sequences of length N that produce a zero sum.
PROGRAM NAME: zerosum
INPUT FORMAT
A single line with the integer N (3 <= N <= 9).
SAMPLE INPUT (file zerosum.in)
7
OUTPUT FORMAT
In ASCII order, show each sequence that can create 0 sum with a `+', `-', or ` ' between each pair of numbers.
SAMPLE OUTPUT (file zerosum.out)
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
/*---------------------------------------------------------------*/
再一次说明了USACO会帮着你复习，这一道题终于不是动态归划了，而是简单的深搜。单纯地遍历所有情况即可，由于最多9个数，8个符号，最多3的8次方种。
程序：
[cpp]
/*
ID:zhaorui3
PROG:zerosum
LANG:C++
*/
# include <iostream>
# include <fstream>
using namespace std;
int operations[9] = {0}; //0:nothing , 1:+, 2:-
int templeft = 0 , tempRight = 0;
int main()
{
operations[0] = 1;
ifstream fin("zerosum.in");
ofstream fout("zerosum.out");
int end;
fin >> end;
while(true) //这层循环是用来遍历所有符号的
{
templeft = 0;
tempRight = 0;
for(int j = 1 ; j <= end ; j++ ) //这层循环是用来计算当前符号下的结果的
{
if(operations[j-1] == 1) // +
{
int k = j;
tempRight = j;
while(k <= end-1 && operations[k] == 0)
{
tempRight = tempRight*10 + k+1;
k++;
j++;
}
templeft = templeft + tempRight;
tempRight = 0;
continue;
}
if(operations[j-1] == 2) // -
{
int k = j;
tempRight = j;
while(k <= end-1 && operations[k] == 0)
{
tempRight = tempRight*10 + k+1;
k++;
j++;
}
templeft = templeft - tempRight;
tempRight = 0;
continue;
}
}
if(templeft == 0)
{
fout << 1;
for(int m = 0 ; m <= end-2 ; m++ )
{
switch(operations[m+1])
{
case 1:
fout << '+';
break;
case 2:
fout << '-';
break;
case 0:
fout << ' ';
break;
}
fout << m+2;
}
fout << endl;
}
operations[end-1]++;
for(int m = end-1 ; m > 1 ; m-- )
{
if(operations[m] > 2)
{
operations[m] = 0;
operations[m-1]++;
}
}
if(operations[1] > 2)
break;
}
}
补充：软件开发 , C++ ,
