首页 > 专题系列 > Java解POJ > POJ 3100 Root of the Problem [解题报告] Java
2013
11-12

POJ 3100 Root of the Problem [解题报告] Java

Root of the Problem

问题描述 :

Given positive integers B and N, find an integer A such that AN is as close as possible to B. (The result A is an approximation to the Nth root of B.) Note that AN may be less than, equal to, or greater than B.

输入:

The input consists of one or more pairs of values for B and N. Each pair appears on a single line, delimited by a single space. A line specifying the value zero for both B and N marks the end of the input. The value of B will be in the range 1 to 1,000,000 (inclusive), and the value of N will be in the range 1 to 9 (inclusive).

输出:

For each pair B and N in the input, output A as defined above on a line by itself.

样例输入:

4 3
5 3
27 3
750 5
1000 5
2000 5
3000 5
1000000 5
0 0

样例输出:

1
2
3
4
4
4
5
16

解题代码:

方法一:
	import java.util.*;
import java.io.*;
import java.lang.reflect.Array;

public class Main {
  static public void main( String [] string ) throws Exception{
    Scanner cin = new Scanner( System.in );
    int b, n;
    while( true ) {
      b = cin.nextInt();
      n = cin.nextInt();
      if( b == 0 && n == 0 )
	 break;
      int x = (int)Math.pow( b, 1.0/n );
      if( Math.abs(Math.pow( x, n )-b)>Math.abs(Math.pow( x+1, n )-b) )
	 x = x+1;
      System.out.println( x );
    }
    return;
  }
}

方法二:
				
 import java.util.*;  
   
 public class Main {  
   
     public static void main(String[] args) {  
         Scanner cin = new Scanner(System.in);  
         String str[];  
           
         while(true)  
         {  
             str = cin.nextLine().split(" ");  
             if(str[0].equals("0") && str[1].equals("0"))  
                 break;  
               
             int b = Integer.valueOf(str[0]).intValue();  
             int n = Integer.valueOf(str[1]).intValue();  
               
             int a = findA(b, n);  
             System.out.println(a);  
         }  
     }  
       
     private static int findA(int b, int n)  
     {  
         int value1, value2 = 0;  
         int raw1 = 1;  
         int raw2 = 0;  
           
         while(true)  
         {  
             raw2 = raw1 + 1;  
             value1 = (int)(Math.pow(raw1, n));  
             value2 = (int)(Math.pow(raw2, n));  
             if(value2 == b)  
                 return raw2;  
             else if(value2 > b)  
                 break;  
             else  
                 raw1++;  
         }  
           
         if(Math.abs(value1-b) <= Math.abs(value2-b))  
             return raw1;  
         else  
             return raw2;  
           
     }  
}

  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

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