首页 > 专题系列 > Java解POJ > POJ 1362 Skew Binary [解题报告] Java
2013
11-09

POJ 1362 Skew Binary [解题报告] Java

Skew Binary

问题描述 :

It had been a year since Swamp County Computing established a functional programming group. Your (non-functional programming) group is going to throw a surprise party for the anniversary. Now the functional folks really like skew binary numbers for some reason. “Easy to increment and decrement!” they say. Your task is to write a program to convert decimal integers to skew binary in the format they like. This will help in making banners and other party material.

Number representations are made up of a list of digits. Call the lowest order digit the rank 0 digit, the next, rank 1, etc. For example, in decimal representation, digits are 0-9, the rank 0 digit has weight 1, the rank 1 digit has weight 10, and the rank i digit has weight 10i. In binary representation, the digits are 0 and 1, and the rank i digit has weight 2i. In skew binary representation, the digits are 0, 1, and 2, and the rank i digit has weight 2i+1 -1.


Rank Weight
0 1
1 3
2 7
3 15
4 31
5 63
6 127
7 255
. .
: :

Allowing the digit 2 in the skew binary means there may be several ways to represent a given number. However the convention is that the digit 2 may only appear as the lowest rank non-zero digit. This makes the representation unique.

In this problem, you should use a special way to write skew binary numbers as a list of ranks of non-zero digits in the number. The digit 2 is represented by the rank of the digit appearing twice in the list. Note that this means that only the first two ranks in the list may be equal.

Each rank is a decimal integer, and is separated from the next rank by a comma (‘,’). A list is started by a ‘[' and ended by a ']‘. For example, the decimal number 5, which has the skew representation 12, should be written as [0,0,1]. Decimal 0 is an empty list: [].

输入:

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by t lines, each containing a single decimal number with no leading or trailing white space. Each number will be in the range 0...100663270 (inclusive).

输出:

There should be one line per test case containing the input decimal number, with no leading zeros or spaces, a single space, and the skew binary equivalent in list format with no leading or trailing spaces. Within the list each rank should have no extra leading zeros or leading or trailing spaces.

样例输入:

5 
0 
1 
2 
3 
4  

样例输出:

0 [] 
1 [0] 
2 [0,0] 
3 [1] 
4 [0,1] 

解题代码:

//* @author: Yeming Hu"[email protected]"
import java.util.*;

public class Main
{
    public static final int max = 30;
    public static void main(String[] args)
    {
        int[] weights = new int[max];
	int p = 2;
	for(int i = 0; i < max; i++)
	{
	    weights[i] = p - 1;
	    p *= 2;
	    //System.out.println(weights[i]);
	}
	
	Scanner sc = new Scanner(System.in);
	int tc = sc.nextInt();
	for(int i = 0; i < tc; i++)
	{
	    int[] digits = new int[max];
	    int num = sc.nextInt();
	    int out = num;
	    for(int j = max - 1; j >= 0; j--)
	    {
	        if(num == 0)
		{
		    break;
		}

	        if(num < weights[j])
		{
		    continue;
		}else if(num == 2 * weights[j])
		{
		    digits[j] = 2;
		    num -= 2*weights[j];
		}else
		{
		    digits[j] = 1;
		    num -= weights[j];
		}
	    }
	    boolean bg = true;
	    System.out.print(out + " [");
	    for(int j = 0; j < max; j++)
	    {
	        if(digits[j] != 0)
		{
		    if(!bg)
		    {
		        System.out.print(",");
		    }else
		    {
		        bg = false;
		    }
		    if(digits[j] == 1)
		    {
		        System.out.print(j);
		    }else
		    {
		        System.out.print(j + "," +j);
		    }
		}
	    }
	    System.out.println("]");
	}
    }
}

  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

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