首页 > 专题系列 > Java解POJ > POJ 1023 The Fun Number System [解题报告] Java
2013
11-08

POJ 1023 The Fun Number System [解题报告] Java

The Fun Number System

问题描述 :

In a k bit 2′s complement number, where the bits are indexed from 0 to k-1, the weight of the most significant bit (i.e., in position k-1), is -2^(k-1), and the weight of a bit in any position i (0 ≤ i < k-1) is 2^i. For example, a 3 bit number 101 is -2^2 + 0 + 2^0 = -3. A negatively weighted bit is called a negabit (such as the most significant bit in a 2's complement number), and a positively weighted bit is called a posibit.

A Fun number system is a positional binary number system, where each bit can be either a negabit, or a posibit. For example consider a 3-bit fun number system Fun3, where bits in positions 0, and 2 are posibits, and the bit in position 1 is a negabit. (110)Fun3 is evaluated as 2^2-2^1 + 0 = 3. Now you are going to have fun with the Fun number systems! You are given the description of a k-bit Fun number system Funk, and an integer N (possibly negative. You should determine the k bits of a representation of N in Funk, or report that it is not possible to represent the given N in the given Funk. For example, a representation of -1 in the Fun3 number system (defined above), is 011 (evaluated as 0 – 2^1 + 2^0), and

representing 6 in Fun3 is impossible.

输入:

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case is given in three consecutive lines. In the first line there is a positive integer k (1 ≤ k ≤ 64). In the second line of a test data there is a string of length k, composed only of letters n, and p, describing the Fun number system for that test data, where each n (p) indicates that the bit in that position is a negabit (posibit).

The third line of each test data contains an integer N (-2^63 ≤ N < 2^63), the number to be represented in the Funk number

system by your program.

输出:

For each test data, you should print one line containing either a k-bit string representing the given number N in the Funk number system, or the word Impossible, when it is impossible to represent the given number.

样例输入:

2
3
pnp
6
4
ppnn
10

样例输出:

Impossible
1110

解题代码:

/* @author: */
import java.util.Scanner;
public class Main{
  public static void main(String args[]){
   long  n;
   int k,t;
   int ans[]=new int[65];
   char a[]=new char[66];
   Scanner sc=new Scanner(System.in);
   t=sc.nextInt();
   while((t--)!=0){
     k=sc.nextInt();
     a=sc.next().toCharArray();
    n=sc.nextLong();
   
    for(int i=0;i< k;i++){
     if((n&0x1)!=0){
      ans[k-1-i]=1;
      if(a[k-i-1]=='p')
       n=n-1;
      else n=n+1;
     }else
      ans[k-1-i]=0;
      n/=2;
     }
     if(n==0){
      for(int i=0;i< k;i++)
        System.out.printf("%d",ans[i]);
      System.out.printf("\n");
    }else System.out.printf("Impossible\n");
   }
  }
 }

  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。