Posts pythonTip 71 回文数 II
Post
Cancel

pythonTip 71 回文数 II

题目描述: 又是回文数!但这次有所不同了。 给定一个N进制正整数,把它的各位数字上数字倒过来排列组成一个新数,然后与原数相加,如果是回文数则停止,如果不是,则重复这个操作,直到和为回文数为止。如果N超过10,使用英文字母来表示那些大于9的数码。例如对16进制数来说,用A表示10,用B表示11,用C表示12,用D表示13,用E表示14,用F表示15。

例如:10进制87则有: STEP1: 87+78=165 STEP2: 165+561=726 STEP3: 726+627=1353 STEP4: 1353+3531=4884

给你一个正整数N(2<=N<=16)和字符串M(”1”<=M<=”30000”(10进制)),表示M是N进制数,输出最少经过几步可以得到回文数。如果在30步以内(含30步)不可能得到回文数,则输出0。输入的数保证不为回文数。 如N=10, M=”87”, 则输出4.注意:M是以字符串的形式给定的。

示例: 输入: N = 10 M = “87”

输出: 4

分析: 这个题和前面的判断回文数基本上就是一样的,只不过有一点点不一样的区别,只是这个题目里面包含了一个进制转换的问题。 所以我直接把前面关于回文的题的代码弄了过来,做了一个关于 进制转换的解码和编码函数。见下面代码:

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
CODE = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A','B', 'C', 'D', 'E', 'F']

def decode(num, n):
    # 将一个十进制数转换成任意 n 进制数, 返回一个字符串
    ans = ""
    while num:
        ans += CODE[num % n]
        num //= n
    
    return ans[::-1]

def incode(num, n):
    # 将一个任意 n 进制的字符串,转化成一个 是十进制的数
    ans = 0
    for ch in num:
        ans = ans * n + CODE.index(ch)
    return ans
        

def judge(s):
    s = decode(s, N)
    ts = s[::-1]
    return s == ts


ans = 0
m = incode(M, N)
while not judge(m) and ans <= 30:
    
    sm = decode(m, N)
    tsm = incode(sm[::-1], N)
    m += tsm
    ans += 1

print(ans if ans <= 30 else 0)
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 70 最大整数

pythonTip 72 球迷购票问题

Trending Tags