首页 > 专题系列 > Java解POJ > POJ 1950 Dessert [解题报告] Java
2013
11-10

POJ 1950 Dessert [解题报告] Java

Dessert

问题描述 :

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.)

输入:

One line with a single integer, N

输出:

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.

样例输入:

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 - 2 . 3 - 4 . 5 + 6 . 7
6

解题代码:

//* @author:alpc12
import java.io.*;
import java.util.*;
import java.math.*;


public class Main {
	
 char[] opa = { '+', '-', '.' };
 char[] op;
 int cnt;
 int n;
 int rec[] = {88, 162, 197, 437, 1350 };
	
 void print() {
  cnt++;
  if(cnt > 20) return;
  int i;
  for(i = 1; i <= n; ++i) {
    System.out.print(i);
    if(i != n){
	System.out.print(" " + op[i] + " ");
    }
  }
  System.out.println("");
 }
	
  void search(int depth, long lastnum, char lastop, long tot) {
    if(cnt > 20) return;
    if(depth == n) {
	if(lastop == '+')
	tot += lastnum;
	else tot -= lastnum;
			
	if(tot == 0)
	  print();
	return;
     }
    for(char c : opa) {
	char curop = lastop;
	long curtot = tot;
	if(c == '+') {
	   op[depth] = c;
	   if(lastop == '+') tot += lastnum;
	   else tot -= lastnum;
	lastop = c;
	search(depth+1, depth+1, lastop, tot);
	} else if(c == '-') {
	  op[depth] = c;
	  if(lastop == '+') tot += lastnum;
	  else tot -= lastnum;
	  lastop = c;
	  search(depth+1, depth+1, lastop, tot);
	} else if(c == '.') {
	  op[depth] = c;
	  String s = "" + lastnum;
	  s += (depth+1);
	  if(s.length() > 9) continue;
	  long x = Long.parseLong(s);
	  search(depth+1, x, lastop, tot);
	}
	tot = curtot;
	lastop = curop;
   }
 }
	
void run() {
  Scanner cin = new Scanner(System.in);
  n = cin.nextInt();
  op = new char[n];
  cnt = 0;
  search(1, 1, '+', 0);
  if(n < 11)
	System.out.println(cnt);
  else 
	System.out.println(rec[n-10-1]);
 }

 public static void main(String[] args) {
   new Main().run();

 }

}

  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。