首页 > 专题系列 > Java解POJ > POJ 2984 A New Joseph Problem [解题报告] Java
2013
11-12

POJ 2984 A New Joseph Problem [解题报告] Java

A New Joseph Problem

问题描述 :

Newman and Bamboo are good friends. One day, Newman taught Bamboo the famous Joseph Problem: there are N persons numbered 1 to N standing round a circle. They stand clockwise according to their numbers (namely 1, 2, 3, 4, …, N). Then, starting from 1, the killer kills every 2nd person he counts until there is only one person left whose number is J(N). We can easily infer that J(1) = 1, J(5) = 3 and J(6) = 5. Bamboo finds this problem intriguing and starts thinking. Suddenly, he finds that if he continually uses J(N) to be the term in J, he can finally get a fixed number. For example, J(2) = 1, so J(J(2)) = 1, J(J(…J(2)…)) = 1. Newman agrees with Bamboo but Bamboo is not satisfied. Furthermore, Bamboo wants to know what the fixed number will be for a specific N. Can you help us?

输入:

Only one line containing n (1 ≤ n ≤ 1010000).

输出:

Only one line containing K such that J(J(J(JJ(N)…))) = K and J(K)=K.

样例输入:

10

样例输出:

3

温馨提示:

J(10) = 5, J(5) = 3, J(3) = 3.

解题代码:

//* @author 
import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{
    public static int a[];
    public static int luckpeople(int n)
    {
        if(n==1)
            return 1;
        if(n%2==1)
            return luckpeople((n-1)/2)*2+1;
        else
            return luckpeople(n/2)*2-1;
    }
    public static int fun(int n)
    {
        int b;
        while(true)
        {
            b=a[n];
            if(b==n)
                return b;
            n=b;
        }
    }
    public static void main(String[] args) 
    {
        int i,count;
        //a = new int[110];
        //for(i=1;i<=100;i++)
            //System.out.println(luckpeople(i));
            //a[i]=luckpeople(i);
        //for(i=1;i<=100;i++)
        //System.out.println(fun(i));
        BigInteger n,ans;
        String s;
        Scanner cin = new Scanner (System.in);
        while(cin.hasNext())
        {
            n = cin.nextBigInteger();
            s = n.toString(2);
            count = 0;
            for(i=0;i< s.length();i++)
                if(s.charAt(i)=='1')
                    count++;
            ans=BigInteger.valueOf(2);
            ans = ans.pow(count);
            ans = ans.subtract(BigInteger.ONE);
            System.out.println(ans);
        }
         
    }

}

  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])