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;
    }

}

           

測試結果

• 我感覺挺快的了