首页 > 专题系列 > Java解POJ > POJ 3092 Non-divisible 2-3 Power Sums [解题报告] Java
2013
11-12

POJ 3092 Non-divisible 2-3 Power Sums [解题报告] Java

Non-divisible 2-3 Power Sums

问题描述 :

Every positive integer N can be written in at least one way as a sum of terms of the form (2a)(3b) where no term in the sum exactly divides any other term in the sum. For example:

1 = (20)(30)
7 = (22)(30) + (20)(31)
31 = (24)(30) + (20)(32) + (21)(31) = (22) + (33)

Note from the example of 31 that the representation is not unique.

Write a program which takes as input a positive integer N and outputs a representation of N as a sum of terms of the form (2a)(3b).

输入:

The first line of input contains a single integer C (1 ≤ C ≤ 1000) which is the number of datasets that follow.

Each dataset consists of a single line of input containing a single integer N (1 ≤ N < 231), which is the number to be represented as a sum of terms of the form (2a)(3b).

输出:

For each dataset, the output will be a single line consisting of: The dataset number, a single space, the number of terms in your sum as a decimal integer followed by a single space followed by representations of the terms in the form [<2 exponent>,<3 exponent>] with terms separated by a single space. <2 exponent> is the power of 2 in the term and <3 exponent> is the power of 3 in the term.

样例输入:

6
1
7
31
7776
531441
123456789

样例输出:

1 1 [0,0]
2 2 [2,0] [0,1]
3 3 [4,0] [0,2] [1,1]
4 1 [5,5]
5 1 [0,12]
6 8 [3,13] [4,12] [2,15] [7,8] [9,6] [0,16] [10,5] [15,2]

解题代码:

/* @author: */
import java.util.Scanner;
public class Main {
   public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
	int n, i, k, t, tt, p, count = 0;
       tt=sc.nextInt();
	while(( tt-- )!=0) {
         n=sc.nextInt();
         int a[]=new int[100];
         int b[]=new int[100];
         k = 0;
	  p = 0;
	  while( n!=0 ) {
	   for( ; (n&1)==0; p++, n>>=1 )
		;
	    for( t=1, i=0; t*3<=n; t*=3,i++ )
		;
	    a[k] = p;
	    b[k] = i;
	    n -= t;
	    k++;
	  }
	  System.out.printf( "%d %d", ++count, k );
	  while(( k--)!=0 )
		System.out.printf( " [%d,%d]", a[k], b[k] );
	  System.out.printf( "\n" );
	}
   }
}

  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  4. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?