欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PTA1010 Radix (25 分) 进制转化

程序员文章站 2024-03-17 14:34:16
...

本题考察进制的转化问题。

首先要先了解一下本题解法:

如果不限制未知数的进制,直接暴力会超时,所以采用二分查找。

那就必然要找出最小的进制和最大的进制了。

最小进制 ,最大的那位+1

eg: 1231435346 这个数他的最小进制就是最大的那位 6+1=7;所以二分查找的左边界为7

最大进制,已知数的十进制

eg:已知数是100,未知数是 1231435346 ,那么二分查找的右边界就是100;

convert() 把radix进制的num1转换成10进制的数

public static int convert(String num1,int radix) { 
    	int sum=0;
    	int length=num1.length();
    	for(int i=0;i<length;i++) {
    		char ch=num1.charAt(i);
    		sum+=(ch>='0'&&ch<='9')?(Math.pow(radix,length-1-i)*(ch-'0')):(Math.pow(radix,length-1-i)*(ch-'a'+10));
    	}
    	return sum;
    }

comparsion()进行二分查找

public static int comparsion(int sum,String num2) {
    	int length=num2.length();
    	int low=0;
    	for (int i=0;i<length;i++) {
    		char ch=num2.charAt(i);
    		low=Math.max(low, (ch>='0'&&ch<='9')?(ch-'0'):(ch-'a'+10));
    	}
    	int high=sum;
    	while(low<=high) {
    		int mid=low+(high-low)/2;
    		int res=convert(num2,mid);
    		if(res==sum)
    			return mid;
    		else if(res>sum)
    			high=mid-1;
    		else
    			low=mid+1;
    	}
    	return -1;
    	}

package pta;
import java.util.*;

public class P_1010 {
	
	public static int convert(String num1,int radix) { 
    	int sum=0;
    	int length=num1.length();
    	for(int i=0;i<length;i++) {
    		char ch=num1.charAt(i);
    		sum+=(ch>='0'&&ch<='9')?(Math.pow(radix,length-1-i)*(ch-'0')):(Math.pow(radix,length-1-i)*(ch-'a'+10));
    	}
    	return sum;
    }
    public static int comparsion(int sum,String num2) {
    	int length=num2.length();
    	int low=0;
    	for (int i=0;i<length;i++) {
    		char ch=num2.charAt(i);
    		low=Math.max(low, (ch>='0'&&ch<='9')?(ch-'0'):(ch-'a'+10));
    	}
    	int high=sum;
    	while(low<=high) {
    		int mid=low+(high-low)/2;
    		int res=convert(num2,mid);
    		if(res==sum)
    			return mid;
    		else if(res>sum)
    			high=mid-1;
    		else
    			low=mid+1;
    	}
    	return -1;
    	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner reader=new Scanner(System.in);
		String num1=reader.next();
		String num2=reader.next();
		int cout=reader.nextInt();
		int radix=reader.nextInt();
		if(cout==1) {
			int ans=comparsion(convert(num1,radix),num2);
			if(ans==-1)
				System.out.print("Impossible");
			else
			System.out.print(ans);
		}
		else{
			int ans=comparsion(convert(num2,radix),num1);
			if(ans==-1)
			   System.out.print("Impossible");
			else
			System.out.print(ans);
	}
		reader.close();
	}

}

上一篇: pat 甲级 A1010 Radix (25分)

下一篇: