PAT练习题(甲级) 1010 Radix (25分)(Java实现)

PAT练习题 1010 Radix（25分）

• • 题干
  • 题意
  • 陷阱
  • 解题思路
• 代码
• • 三目表达式
  • 转化十进制模板
  • 本题代码
  • 测试结果

题干

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers N1and N2, your task is to find the radix of one number while that of the other is given.

Input Specification:

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:

N1 N2 tag radix

Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.

Output Specification:

For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.

Sample Input 1:

6 110 1 10
           

Sample Output 1:

2
           

Sample Input 2:

1 ab 1 2
           

Sample Output 2:

Impossible
           

题意

• 两个数字，给出一个数字的进制，然后找出另一个数字是否存在一个进制令两个数相等。
• 如果存在这样的进制，那么输出，如果不存在，则输出impossible。
• N1、N2是输入的两个数，tag代表是哪一个数是已知进制的，radix是进制数。

陷阱

• 首先这道题给出a-z，所以有可能会认为进制最高还是36（我一开始也是这么觉得），但仔细看题，a-z只适用于N1和N2的表示，如果radix=100也是可以的。
• 寻找合适的查询方法，这道题如果使用顺序查找，一个进制一个进制的往上加太慢了，会超时，因为这个radix可能会很大。（总共有七种查找方法，过两天我会把我自己知道的写一下）

解题思路

• 如果你会BigInteger类的话，那就用吧，听说是内存多大，它能表示的数就有多大，当然这是Java里的，如果你用的是C那就用long long。
• 在查找的算法中，二分查找是适用于数据量很大的查找方法。（因为我之前试的顺序和分块，后来发现还是二分最快）
• 转化成十进制数有固定的模板，代码在下面，大家可以自己练，很简单。
• 然后加上判断条件就行了，我是用的是三目，简洁一点，要不然if语句里面写一堆也不好看。

代码

三目表达式

//如果满足a条件，则输出b,否则输出c
a ? b : c
           

转化十进制模板

//将给出进制的数字转换成十进制数
    static long tonum(String str,long radix)
    {
        long num = 0;//转化的结果
        int temp = 0;//将字符串转化成数字，因为存在a-z
        int j = 0;//这个是进行按位转化成十进制的指数，从右到左每次加一
        for(int i = str.length()-1;i>=0;i--)
        {
            //利用三目进行赋值更简洁，str.charAt(i)-'a'+10是将该位调整为整数
            temp = str.charAt(i)>='a' ? str.charAt(i)-'a'+10 : str.charAt(i)-'0';
            //将该位转化为十进制数
            num += temp*Math.pow(radix,j++);
        }
        return num;
    }
           

本题代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Author: 胡奇夫
 * @QQ: 1579328766
 * @CreateTime: 2020-05-16-09-46
 * @Descirption: Pat甲级1010
 */
public class Testten {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strlist = br.readLine().split(" ");
        String n1 = strlist[0];
        String n2 = strlist[1];
        int tag = Integer.parseInt(strlist[2]);
        long radix = Long.parseLong(strlist[3]);
        long result = tag==1 ? findradix(n2,tonum(n1,radix)) : findradix(n1,tonum(n2,radix));
        if(result == -1)
            System.out.println("Impossible");
        else
            System.out.println(result);
    }

    //将给出进制的数字转换成十进制数
    static long tonum(String str,long radix)
    {
        long num = 0;//转化的结果
        int temp = 0;//将字符串转化成数字，因为存在a-z
        int j = 0;//这个是进行按位转化成十进制的指数，从右到左每次加一
        for(int i = str.length()-1;i>=0;i--)
        {
            //利用三目进行赋值更简洁，str.charAt(i)-'a'+10是将该位调整为整数
            temp = str.charAt(i)>='a' ? str.charAt(i)-'a'+10 : str.charAt(i)-'0';
            //将该位转化为十进制数
            num += temp*Math.pow(radix,j++);
        }
        return num;
    }

    /*寻找合适的进制,num是已知字符串的十进制表示
    使用二分查找，因为普通的查找算法会根据上限的上升，复杂度也会提高很多
    2进制，3进制...线性查找太慢了，而其他的查找算法也不适用于这道题，因为这道题里没有用到数据结构
    递归实现二分查找*/
    static long findradix(String str,long num)
    {
        long low = '0';
        for (int i = 0; i < str.length(); i++) {
            if (low < str.charAt(i)) {
                low = str.charAt(i);
            }
        }
        low = ((low>='0' && low<='9') ?  low - '0' : low - 'a' + 10) + 1;
        long high = Math.max(low, num);
        while (low <= high) {
            long mid = (low + high) / 2;
            long t = tonum(str, mid);
            if (t < 0 || t > num)
                high = mid - 1;
            else if (t == num)
                return mid;
            else
                low = mid + 1;
        }
        return -1;
    }

}

           

测试结果

• 我感觉挺快的了