# 这个题还是蛮难的,显示中等难度(其实也不是很难,一开始没理解题意,但是要思考的细节很多,有意思) # 对于10进制数87: 可以通过n步加法得到一个回文数 # STEP1:87+78 = 165 STEP2:165+561 = 726 # STEP3:726+627 = 1353 STEP4:1353+3531 = 4884 # 在这里的一步是指进行了一次N进制的加法,上例最少用了4步得到回文数4884。(注意是N进制的加法,我一开始看错以为是转成10进制然后加法) # 注意这里每一次加法都是加上把本身翻转后的数 # 写一个程序,给定一个N(2<=N<=10或N=16)进制数M(100位之内),求最少经过几步可以得到回文数。 # 如果在30步以内(包含30步)不可能得到回文数,则输出“Impossible!” # 进制N>10时,使用大写'A'字母表示10,'B'表示11,...,'E'表示16 # 感觉一个首先的思路是,对于输入的不同进制得先统一进制 def to_ten(x, N): # 任意输入进制转成10进制 number = 0 for i in range(len(x)): if x[i]=="A": number+=10*int(N)**(len(x)-1-i) elif x[i]=="B": number+=11*int(N)**(len(x)-1-i) elif x[i]=="C": number+=12*int(N)**(len(x)-1-i) elif x[i]=="D": number+=13*int(N)**(len(x)-1-i) elif x[i]=="E": number+=14*int(N)**(len(x)-1-i) elif x[i]=="F": number+=15*int(N)**(len(x)-1-i) else: number+=int(x[i])*int(N)**(len(x)-1-i) return number def ten_ToAny(N, x): # 将10进制转回一开始的输入进制,N为进制 N= int(N) ls = [] while True: div, mod = divmod(x, N) ls.append(mod) x = div if x==0: break temp_list=list(map(str, ls[::-1])) for i in range(len(temp_list)): if temp_list[i] == '10': temp_list[i] = 'A' elif temp_list[i] == '11': temp_list[i] = 'B' elif temp_list[i] == '12': temp_list[i] = 'C' elif temp_list[i] == '13': temp_list[i] = 'D' elif temp_list[i] == '14': temp_list[i] = 'E' elif temp_list[i] == '15': temp_list[i] = 'F' return ''.join(temp_list) # 关于是不是回文数这个问题自己一开始想傻了,忘记python可以直接利用字符串相等判断 def huiwen(x): if x==x[::-1]: return True else: return False def add(x, X, num=0): if huiwen(x): print("STEP={}".format(num)) return True else: y = x[::-1] # 翻转,得到加数 if X != 10: c = to_ten(x, X)+to_ten(y, X) c = ten_ToAny(X, c) # 10进制加完之后在转换回去 else: c = int(x) + y num += 1 if num>30: print("Impossible!") return True else: return add(str(c), X, num) # 采用递归的思想,因为要加很多步嘛,很自然的想法 if __name__ == "__main__": N = input() # 进制数 M = input() # 数值 add(M, N) ### 代码稍微写的有点复杂,懒得重构了