USACO - 2.3.3 - Zero Sum

 

原创文章转载请注明出处

摘要：dfs ， 枚举

一. 题目翻译

1. 描述：

请考虑一个由1到N（N=3, 4, 5 ... 9）的数字组成的递增数列：1 2 3 ... N。 现在请在数列中插入“+”表示加，或者“-”表示减，“ ”表示空白(例如1-2 3就等于1-23)，来将每一对数字组合在一起（请不要在第一个数字前插入符号）。 计算该表达式的结果并判断其值是否为0。 请你写一个程序找出所有产生和为零的长度为N的数列。

2. 格式：

          INPUT FORMAT:

          单独的一行表示整数N (3 <= N <= 9)。

          OUTPUT FORMAT:

          按照ASCII码的顺序，输出所有在每对数字间插入“+”, “-”, 或 “ ”后能得到结果为零的数列。

3. SAMPLE：

          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

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

          这道题目使用DFS来做，题目中输入数据比较少。每层只有三个状态（"+" "-" " "），有八层。最终判断和是否为0，如果是0则输出。

 

2. 具体实现（具体实现过程中出现的问题）：

          请参考代码注释。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:zerosum
*/
package session_2_3_3;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Scanner;

public class zerosum {
	
	static int num;
	static int[] nums = new int[]{1,2,3,4,5,6,7,8,9};
	static char[] operator = new char[]{' ','+','-'};
//	static Scanner in;
	static PrintWriter pw ;
	static Scanner in;
	
	static LinkedList<Character> operators;
	
	public static void main(String[] args) throws Exception {
		in = new Scanner(new BufferedReader(new FileReader(
				"zerosum.in")));
		pw = new PrintWriter(new BufferedWriter(new FileWriter(
				"zerosum.out")));
//		in = new Scanner(System.in);
//		pw = new PrintWriter(System.out);
		num = in.nextInt();
		operators = new LinkedList<Character>();//用一个linedlist记录每层添加操作数
		dfs(1);//dfs从第一层开始
		pw.close();
	}
	
	public static void dfs (int depth){
		LinkedList<Character> temp = operators;
		if (depth == num){
			if (judge()){//如果到达第八层，则判断和是否为0
				StringBuilder sb = new StringBuilder();
				for (int i=0;i<num-1;i++){
					sb.append(nums[i]+""+operators.get(i));
				}
				sb.append(nums[num-1]);
//				System.out.println(sb);
				pw.println(sb);
			}
		} else {
			for (int i=0;i<=2;i++){//如果没有到达终止条件，则继续dfs
				operators.addLast(operator[i]);
				dfs(depth+1);
				operators.removeLast();
			}
		}
	}
	
	public static boolean judge(){
		LinkedList<Character> temp = operators;
		LinkedList<Character> ops = new LinkedList<Character>(operators);//记录操作符
		LinkedList<Integer> ots = new LinkedList<Integer>();//记录操作数
		for (int i=0;i<9;i++){
			ots.add(i+1);
		}
		for (int i=0;i<ops.size();){
			char op = ops.get(i);
			if (op == ' '){//如果操作符是“ ”，则更新操作数
				ops.remove(i);
				int a = ots.remove(i);
				int b = ots.remove(i);
				ots.add(i, a*10+b);
			}else{
				i++;
			}
		}
		int a = ots.get(0);//计算总和
		for (int i=0;i<ops.size();i++){
			char op = ops.get(i);
			if (op == '+'){
				a = a + ots.get(i+1);
			} else {
				a = a - ots.get(i+1);
			}
		}
		if (a == 0){
			return true; //总和为0，返回true
		} else {
			return false;
		}
	}

}