首页 > 专题系列 > Java解POJ > POJ 1702 Eva’s Balance [解题报告] Java
2013
11-10

POJ 1702 Eva’s Balance [解题报告] Java

Eva’s Balance

问题描述 :

Eva has a balance with 20 poises. The weights of the poises are 1, 3, 9, 27,…,3^19. Eva asserts that she has a way to measure any object whose weight is an integer from 1 to (3^20-1)/2. Assuming that Eva has placed an object with the weight in this range on the left tray of the balance, your task is to place the proper poises on the proper trays so as to weigh the object out.

输入:

The first line is an integer T (1 <= T <= 20), which shows the number of the test cases. Each of the following T lines contains an integer W (1 <= W <= (3^20-1)/2), expressing the weight of an object.

输出:

For each test case print a line, showing the weights of the poises on the left tray and the right tray. Use a space to separate the left tray and the right tray. The poises on the same tray are arranged in the increasing order, and a comma separates every two of them. If there is no poise on the tray, output “empty”.

样例输入:

3
9
5
20

样例输出:

empty 9
1,3 9
1,9 3,27

解题代码:

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 static long ans[]={ 1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,
                     1594323,4782969,14348907,43046721,129140163,387420489,1162261467 };
 public static void  main(String args[]){
  int n;
  Scanner sc=new Scanner(System.in);
  n=sc.nextInt();
  int p[]=new int[25];
  while((n--)!=0){
    Arrays.fill(p,0);
    int  a;
    a=sc.nextInt();
    int len=0,i;
    while(a!=0)
    {
	int u=a%3;
	p[len++]=u;
	a/=3;
     }
    for(i=0;i< len;i++)
    {
	if(p[i]==2)
	{
	  p[i]=-1;
	  p[i+1]++;
	}
	if(p[i]==3)
	{
	  p[i]=0;
	  p[i+1]++;
	}
     }
     boolean bb=false;
     for(i=0;i<=len;i++)
     {
	if(p[i]==-1)
	{
	  if(bb) System.out.printf(",");
	  System.out.printf("%d",ans[i]);
	  bb=true;
	}
      }
      if(!bb) System.out.printf("empty");
      System.out.printf(" ");
      bb=false;
      for(i=0;i<=len;i++)
       {
	  if(p[i]==1)
	  {
	   if(bb) System.out.printf(",");
	   System.out.printf("%d",ans[i]);
	   bb=true;
	   }
	 }
	 System.out.println();
    }
  }
}

  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n