PAT A1010：Radix（二分查找）

本文作者：MowChan · 发布日期：2021/01/04 · 阅读时长：6 分钟

题目内容

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 $N_1$ and $N_2$, 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

题目要点

本题 25 分，测试点共 20 个，为防止超时必须使用二分查找法，且需要考虑边界情况，难度较大。

算法思路

tag的作用是指明N1或N2哪个数的进制已知，因此tag=1或tag=2是同一个问题，可以用条件语句分支讨论或者以tag=1为准，当tag=2时交换N1和N2。这里我们分析时认为tag=1。

由于这道题比较复杂，所以进制转换的功能要封装成函数便于复用。实现任意进制到10进制的转换不难，如果使用ASCII码转换字符对应的数值时，注意数字、字母在ASCII不是连续存储的，需要判断一下。本文在 Python 中是使用index方法，从0~z的字符串中找到字符对应的下标位置，即为对应的数值。再用map函数得到各位对应值的迭代器，通过列表生成器和sum函数求出最后的十进制值，代码简洁清晰。

二分查找法是针对有序序列的，这道题之所以可以使用二分查找是因为N2固定，随着radix的增加，N2所对应的十进制数值也就越大，构成一个递增序列。二分查找法需要的4个输入量：有序序列、目标值、low、high。目标值是N1对应的十进制值，而low和high是这道题的难点，在易错分析中有详细分析。经过几轮查找后查找到与目标值相同的值时，当前指针位置也就是相应的radix，输出mid，即为最终结果；如果查找失败，那么输出-1，在程序入口函数中判断，输出Impossible。

易错分析

本题题设中没有给出一个具体的数值范围，因此 C/C++ 编写时要采用long long形整数。Python 的整数长度足够长，不用考虑这类问题。

对于下界low的确定，需要考虑输入的任意进制数值。比如对于2进制数，各个位上不可能出现2，对于10进制数，各个位上不可能出现10，而是进位，从0重新开始。因此找出输入的任意进制数值中最大的一位，再加1，即为low。比如，输入105a，最大的是a，对应的值是10，那么这个数至少是个10+1=11进制数。（测试点0）

对于上界high的确定，与下界类似。首先要考虑最大的可能性，即可能是N1所对应的进制。然后，要考虑特殊的值，比如N1=0时，其上界不可能为0，至少是2，或者说high至少不能比low小，否则循环直接跳出。因此上界要取二者最大值，即high=max(N1_dec, low)。（测试点19）

Python 的数据类型是动态的，因此二分法计算中间元素的指针mid时必须将最终结果取整，否则会得到一个小数值，以此为radix计算输入数的十进制时会得到错误结果。

AC 源代码

def letter_to_int(n):
    return '0123456789abcdefghijklmnopqrstuvwxyz'.index(n)

def to_decimal(n, base):
    digits = map(lambda r: letter_to_int(r), n[::-1])
    return sum([ digit * base ** r for r, digit in enumerate(digits) ])

def binary_search(string, num):
    low = letter_to_int(max(string)) + 1
    high = max(num, low)
    while low <= high:
        mid = int((low + high) / 2)
        cnum = to_decimal(string, mid)
        if cnum == num:
            return mid
        elif cnum > num:
            high = mid - 1
        else:
            low = mid + 1
    return -1

n1, n2, tag, radix = input().split()
tag, radix = int(tag), int(radix)

if tag == 2:
    n1, n2 = n2, n1

ans = binary_search(n2, to_decimal(n1, radix))
if ans == -1:
    print('Impossible')
else:
    print(ans)

参考来源

https://www.liuchuo.net/archives/2458

https://segmentfault.com/a/1190000037525090

https://blog.csdn.net/Joyceyang_999/article/details/81908299

← 上一篇 下一篇 →