[已解决]鱼C论坛python精英挑战赛（02期）

jerryxjr1220

Python的编程技能还是要靠平时不断地练习才能提高，为了提高大家的积极性，特别设立了这个精英挑战赛，希望大家多多参与！

本期挑战赛限时3天，截止日：6月22日24时，参赛人员：python论坛任何人员（包括版主）。

截止日后，从所有提交的解答中评选出最优秀的解答，奖励100鱼币。评选依据：答案正确，用时较短，代码优雅。

另外，如果有创意的解题方法，会酌情追加奖励！

本期题目：非负整数进制转换

我们按照62进制的 [ 0 ~ 9, A ~ Z, a ~ z]的顺序 与 [ 0 ~ 61]一一对应。如果<62进制，则靠前匹配。如36进制 [0 ~9, A ~ Z]与[0 ~ 35]一一对应。

那么，36进制的“FISHC”如果转化成16进制就应当是“18DCFB0”。 62进制的“FISHC”如果转化成26进制就应当是“J0GO26”。

显然，“18DCFB0”至少是16进制，因为“F"表示15。

现在请设计一个进制计算函数Calc（rawdata，newdata），输出原始的进制n和转化后的进制m，如Calc（“FISHC”，“18DCFB0”）-> (36，16）。

注意若输出有多个答案，应当遵循n和m都尽可能小的原则。n和m的取值范围：2<=m, n<=62。rawdata和newdata为字符串格式，字符串长度1 ～ 128位.

测试数据集：

1. Test = [('A', '11'),
   
2.         ('18', '18'),
   
3.         ('ABC', '41I'),
   
4.         ('3d8B', '254731'),
   
5.         ('FISHC', '18DCFB0'),
   
6.         ('python', 'B1687AEA1'),
   
7.         ('10110111010010010010101000101010', '11TIFA8BPMTL0'),
   
8.         ('10110111010010010010101000101010010101010101010010101001010100101101010101010010101001010100101010101010010101001010010101001010', '5Zr1zn3pm5znjGepqkPmDC')]

复制代码

本期挑战的题目已经降低难度，欢迎大家积极参与！

@SixPy @冬雪雪冬 @～风介～ @小甲鱼

最佳答案

月排行榜 / 总排行榜

WelanceLee

2017-6-20 00:28:58

1. import string
   
2. a = string.printable[:62]
   
3. a = a[:10] + a[-26:] + a[10:36]
   
4. str_table = dict((a[i],i) for i in range(len(a)))
   
5. 
   
6. def convert(a, n):
   
7.     x = 0
   
8.     for each in a:
   
9.         x += str_table[each]
   
10.         x*= n
    
11.     return x//n
    
12. 
    
13. def findmax(a):
    
14.     mmax = 0
    
15.     for each in a:
    
16.         if str_table[each] > mmax:
    
17.             mmax = str_table[each]
    
18.     return mmax + 1
    
19. 
    
20. def calc(a, b):
    
21.     m = findmax(a)
    
22.     n = findmax(b)
    
23.     for i in range(m, 63):
    
24.         for j in range(n, 63):
    
25.             if convert(a, i) == convert(b, j):
    
26.                 print((i, j))
    
27.                 return i, j
    
28. 
    
29.    
    
30. Test = [('A', '11'),
    
31.         ('18', '18'),
    
32.         ('ABC', '41I'),
    
33.         ('3d8B', '254731'),
    
34.         ('FISHC', '18DCFB0'),
    
35.         ('python', 'B1687AEA1'),
    
36.         ('10110111010010010010101000101010', '11TIFA8BPMTL0'),
    
37.         ('10110111010010010010101000101010010101010101010010101001010100101101010101010010101001010100101010101010010101001010010101001010', '5Zr1zn3pm5znjGepqkPmDC')]
    
38. 
    
39. for each in Test:
    
40.     calc(each[0], each[1])
    

复制代码

结果是
(11, 9)
(9, 9)
(16, 26)
(40, 10)
(36, 16)
(62, 16)
(4, 36)
(2, 62)

跳转到最佳答案楼层

WelanceLee

1. import string
   
2. a = string.printable[:62]
   
3. a = a[:10] + a[-26:] + a[10:36]
   
4. str_table = dict((a[i],i) for i in range(len(a)))
   
5. 
   
6. def convert(a, n):
   
7.     x = 0
   
8.     for each in a:
   
9.         x += str_table[each]
   
10.         x*= n
    
11.     return x//n
    
12. 
    
13. def findmax(a):
    
14.     mmax = 0
    
15.     for each in a:
    
16.         if str_table[each] > mmax:
    
17.             mmax = str_table[each]
    
18.     return mmax + 1
    
19. 
    
20. def calc(a, b):
    
21.     m = findmax(a)
    
22.     n = findmax(b)
    
23.     for i in range(m, 63):
    
24.         for j in range(n, 63):
    
25.             if convert(a, i) == convert(b, j):
    
26.                 print((i, j))
    
27.                 return i, j
    
28. 
    
29.    
    
30. Test = [('A', '11'),
    
31.         ('18', '18'),
    
32.         ('ABC', '41I'),
    
33.         ('3d8B', '254731'),
    
34.         ('FISHC', '18DCFB0'),
    
35.         ('python', 'B1687AEA1'),
    
36.         ('10110111010010010010101000101010', '11TIFA8BPMTL0'),
    
37.         ('10110111010010010010101000101010010101010101010010101001010100101101010101010010101001010100101010101010010101001010010101001010', '5Zr1zn3pm5znjGepqkPmDC')]
    
38. 
    
39. for each in Test:
    
40.     calc(each[0], each[1])
    

复制代码

结果是
(11, 9)
(9, 9)
(16, 26)
(40, 10)
(36, 16)
(62, 16)
(4, 36)
(2, 62)

jerryxjr1220

02期开赛啦，这次题目相对简单很多，希望大家多多参与！凡是答题都有奖励！

冬雪雪冬

可否给大家多一些测试数据？

jerryxjr1220

冬雪雪冬 发表于 2017-6-20 14:27
可否给大家多一些测试数据？

好的，我把测试数据都放上来好了。
大家可以先自行验证。

lh625243422

回家修改优化后发代码

jerryxjr1220

lh625243422 发表于 2017-6-20 14:41
回家修改优化后发代码

递归的话要当心递归深度限制

lh625243422

恩，可以改成循环

新手·ing

等待第三期

lh625243422

1. import sys
   
2. sys.setrecursionlimit(10000)#设置递归最大次数
   
3. #生成单个字符对应的10进制数
   
4. d={}
   
5. for i in range(10):
   
6.     d[chr(48+i)]=i  
   
7. for i in range(26):
   
8.     d[chr(65+i)]=i+10   
   
9. for i in range(26):
   
10.     d[chr(97+i)]=i+36
    
11.    
    
12. def R2d(s,R):    #转为10进制数
    
13.     if len(s)==1:
    
14.         return d[s[0]]*(R)**0
    
15.     else:
    
16.         return d[s[0]]*(R)**(len(s)-1)+R2d(s[1:],R)
    
17. 
    
18. def minR(s):     #确定最小进制
    
19.     num=[]
    
20.     for i in s:
    
21.         num.append(d[i])
    
22.     return max(num)+1
    
23. 
    
24. def all_d(s):    #所有的R进制数转为10进制的列表
    
25.     Ld=[]
    
26.     for i in range(minR(s),63):
    
27.         Ld.append(R2d(s,i))
    
28.     return Ld
    
29. 
    
30. def nm(s1,s2):   #所有的(n,m)组合
    
31.     L1=all_d(s1)
    
32.     L2=all_d(s2)
    
33.     mm=[]
    
34.     for i in L1:
    
35.         if i in L2:
    
36.             mm.append((L1.index(i)+minR(s1),L2.index(i)+minR(s2)))
    
37.     return mm
    
38. 
    
39. def min_nm(s1,s2):  #所有的(n,m)组合中(n+m)最小的
    
40.     sum_nm=[]
    
41.     nm_copy=nm(s1,s2).copy()
    
42.     if nm_copy:
    
43.         for n,m in nm_copy:
    
44.            sum_nm.append(n+m)
    
45.         print(nm_copy[sum_nm.index(min(sum_nm))])
    
46.     else:
    
47.         print('无结果')
    
48. min_nm('python','B1687AEA1')
    
49. 
    
50. 
    
51. Test = [('A', '11'),
    
52.         ('18', '18'),
    
53.         ('ABC', '41I'),
    
54.         ('3d8B', '254731'),
    
55.         ('FISHC', '18DCFB0'),
    
56.         ('python', 'B1687AEA1'),
    
57.         ('10110111010010010010101000101010', '11TIFA8BPMTL0'),
    
58.         ('10110111010010010010101000101010010101010101010010101001010100101101010101010010101001010100101010101010010101001010010101001010', '5Zr1zn3pm5znjGepqkPmDC')]
    
59. 
    
60. for s1,s2 in Test:
    
61.     min_nm(s1,s2)
    

复制代码

min_nm(s1,s2)等同于题目的“Calc(rawstr,newstr)"(s1->rawstr,s2-->newstr)
结果为(62, 16)
Test的结果:(11, 9)
(9, 9)
(16, 26)
(40, 10)
(36, 16)
(62, 16)
(4, 36)
(2, 62)

SixPy

http://bbs.fishc.com/forum.php?mod=redirect&goto=findpost&ptid=77596&pid=2692832
以前写过 十进制 转 任意进制

jerryxjr1220

SixPy 发表于 2017-6-20 19:19
http://bbs.fishc.com/forum.php?mod=redirect&goto=findpost&ptid=77596&pid=2692832
以前写过 十进制 转 ...

嗯，进制转换原理都是相通的。
这题只不过是反过来运用，告诉你转化后的结果，求是什么进制的。

Teagle

先这样吧，最后一个在计算的时候竟然在自动科学记数法并且还四舍五入，很生气
还没又找到方法，让它不使用科学记数法，心累，先交着

1. from math import pow
   
2. 
   
3. ##设置一个题目里面的62进制的列表
   
4. def make_table():
   
5.     table = []
   
6.     for i in range(48,58):
   
7.         table.append(chr(i))
   
8.     for i in range(65,91):
   
9.         table.append(chr(i))
   
10.     for i in range(97,123):
    
11.         table.append(chr(i))
    
12.     return table
    
13. 
    
14. ##判断高进制的字符串是哪一个，目的是：比较的时候以高进制的为主体
    
15. def judge_high(rawData,newData):
    
16.     ##如果位数相同，那么最高位小的，便是高进制的
    
17.     if len(rawData) is len(newData):        
    
18.         if rawData[0] > newData[0]:
    
19.             return (newData,rawData)
    
20.         else:
    
21.             return (newData,rawData)
    
22.     ##如果位数不相同，位数小的便是高进制的
    
23.     else:
    
24.         if len(rawData) > len(newData):
    
25.             return (newData,rawData)
    
26.         else:
    
27.             return (rawData,newData)
    
28.         
    
29. ##判断高低进制字符串起始比较的进制大小
    
30. def judge_system(highData,lessData):
    
31.     table = make_table()
    
32.     highMaxSys = table.index(max(highData))
    
33.     lessMaxSys = table.index(max(lessData))
    
34.     ##高进制字符串最大元素小于低进制字符串最大元素的时候
    
35.     if highMaxSys < lessMaxSys:
    
36.         highMaxSys = lessMaxSys + 1
    
37.     return (highMaxSys + 1,lessMaxSys + 1)
    
38. 
    
39. ## 计算字符串转化到十进制是多少
    
40. def compute(data,sys):
    
41.     table = make_table()
    
42.     temp = 0
    
43.     for i in range(len(data)):
    
44.         temp += table.index(data[i]) * pow(sys,len(data)-i-1)
    
45.     return temp
    
46. 
    
47. ##  进行十进制的比较，相等的话返回进制数
    
48. def compare(highData,lessData,highSys,lessSys):
    
49.     for i in range(highSys,63):
    
50.         for j in range(lessSys,i+1):
    
51.             if compute(highData,i) == compute(lessData,j):
    
52.                 return (i,j)
    
53.             
    
54. def Calc(rawdata,newdata):
    
55.     table = make_table()
    
56.     if rawdata is newdata: ##两字符串相同的情况
    
57.         return (table.index(max(rawdata))+1,table.index(max(rawdata))+1)
    
58.     else:
    
59.         highData,lessData = judge_high(rawdata,newdata)##判断谁是高进制字符串
    
60.         highSys,lessSys = judge_system(highData,lessData)##判断高低字符串最低比较进制
    
61.         ##若存在进制之间的转换，则返回对应进制数
    
62.         try:
    
63.             n,m = compare(highData,lessData,highSys,lessSys)
    
64.         except:
    
65.             return '无法进行转换'
    
66.         
    
67.         if highData == rawdata:
    
68.             return (n,m)
    
69.         else:
    
70.             return (m,n)
    
71. 
    
72. Test = [('A', '11'),
    
73.         ('18', '18'),
    
74.         ('ABC', '41I'),
    
75.         ('3d8B', '254731'),
    
76.         ('FISHC', '18DCFB0'),
    
77.         ('python', 'B1687AEA1'),
    
78.         ('10110111010010010010101000101010', '11TIFA8BPMTL0'),
    
79.         ('10110111010010010010101000101010010101010101010010101001010100101101010101010010101001010100101010101010010101001010010101001010', '5Zr1zn3pm5znjGepqkPmDC')]
    
80. 
    
81. for i in range(len(Test)):
    
82.     print(Calc(Test[i][0],Test[i][1]))

复制代码

1. (11, 9)
   
2. (9, 9)
   
3. (16, 26)
   
4. (40, 10)
   
5. (36, 16)
   
6. (62, 16)
   
7. (4, 36)
   
8. 无法进行转换

复制代码

lh625243422

jerryxjr1220 发表于 2017-6-20 14:49
递归的话要当心递归深度限制

这个递归深度和字符串长度一致，不会出现无线递归吧

lh625243422

Teagle 发表于 2017-6-20 19:57
先这样吧，最后一个在计算的时候竟然在自动科学记数法并且还四舍五入，很生气  
还没又找 ...

数据太大浮点误差？

1. #temp += table.index(data[i]) * pow(sys,len(data)-i-1)
   
2.         temp += table.index(data[i]) * sys**(len(data)-i-1)

复制代码

结果出来了

lh625243422

不要用pow试试
是math.pow的锅
你的第一句可以去掉，因为pow是内置函数的，结果也是整数

SixPy

1. 
   
2. NumSys62='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
   
3. 
   
4. def cov_sys10(num:str, sys:int)->int:
   
5.     return sum(n*sys**i for i,n in
   
6.                enumerate(NumSys62.index(c)
   
7.                for c in reversed(num)))
   
8. 
   
9. def get_numsys(num:str)->int:
   
10.     return NumSys62.index(max(num))+1
    
11.    
    
12. def covall2sys10(num:str)->dict:   
    
13.     return {cov_sys10(num,sys):sys for sys in range(get_numsys(num),63)}
    
14. 
    
15. def Calc(num1:str,num2:str)->(int,int):
    
16.     s1 = get_numsys(num1)
    
17.     if num1==num2:
    
18.         return (s1,s1)
    
19.     s2 = get_numsys(num2)
    
20.     swap = False
    
21.     if s1<s2 :
    
22.         swap = True
    
23.         s1,s2 = s2,s1
    
24.         num1,num2 = num2,num1
    
25.    
    
26.     d = covall2sys10(num1) if len(num1)>1 else {cov_sys10(num1,s1):s1}
    
27.     for sys in range(s2,63):
    
28.         n10 = cov_sys10(num2, sys)
    
29.         if n10 in d:
    
30.             return  (sys,d[n10])if swap else (d[n10],sys)
    
31. 
    
32.         
    
33.    
    
34. Test = [('A', '11'),
    
35.         ('18', '18'),
    
36.         ('ABC', '41I'),
    
37.         ('3d8B', '254731'),
    
38.         ('FISHC', '18DCFB0'),
    
39.         ('python', 'B1687AEA1'),
    
40.         ('10110111010010010010101000101010', '11TIFA8BPMTL0'),
    
41.         ('101101110100100100101010001010100'
    
42.          '101010101010100101010010101001011'
    
43.          '010101010100101010010101001010101'
    
44.          '01010010101001010010101001010',
    
45.          '5Zr1zn3pm5znjGepqkPmDC')]
    
46. 
    
47. for n1,n2 in Test:
    
48.     print(Calc(n1,n2))
    
49. 
    

复制代码

1. (11, 9)
   
2. (9, 9)
   
3. (16, 26)
   
4. (40, 10)
   
5. (36, 16)
   
6. (62, 16)
   
7. (4, 36)
   
8. (2, 62)

复制代码

lh625243422

SixPy 发表于 2017-6-20 21:55

写得好精简，各种推导式，学习了

jerryxjr1220

SixPy 发表于 2017-6-20 21:55

这题我觉得对你来说太easy了
我比较想看你上一期挑战赛题目的解答

达锅

1. import time
   
2. ti=time.time()
   
3. def to10(jzx,num):#转化为10进制，返回十进制数值
   
4.     total=0
   
5.     for i in range(len(num)):
   
6.         total+=zd[num[i]]*(jzx**(len(num)-i-1))
   
7.     return total
   
8.    
   
9. 
   
10. def zh(zf): #转换zh,将字符转换为一个列表(十进制表示的数,进制x），用于比较，变量为字符zf
    
11.     total=[]
    
12.     zf=str(zf)#以防传入数字
    
13.     if min([i in zd for i in zf]):#判断是否含有非法字符，如果有，最小值为0
    
14.         minn=max([zd[i] for i in zf])+1#按字典顺序找到代表最大进制的字符，以此作为最低进制进行判断
    
15.         #return [[to10(i,zf),i] for i in range(max([zd[i] for i in zf])+1,63)]#返回所有列表
    
16.     else:
    
17.         return '非法字符'
    
18.     for i in range(minn,63):
    
19.         total.append([to10(i,zf),i])
    
20.         
    
21.     return total  #返回所有列表
    
22.    
    
23. def calc(t1):
    
24.    
    
25.     x1=zh(t1[0])#生成两个列表，储存从最小进制到62进制的进制及对应的十进制数
    
26.     x2=zh(t1[1])
    
27.    
    
28.     c=[] #临时
    
29.    
    
30.     for i in x1:#比较十进制数是否一致
    
31.         for j in x2:
    
32.             if i[0]==j[0]:
    
33.                 c.append((i[1],j[1]))
    
34.         if c!=[]:#有一致的退出，即最小值
    
35.             break
    
36.     return c if c!=[] else '无法匹配'
    
37. 
    
38. 
    
39.    
    
40. zd={} #生成字典zd,
    
41. z='0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z'.split()
    
42. for i in range(62):
    
43.     zd[z[i]]=i
    
44.    
    
45. Test = [('A', '11'),
    
46.         ('18', '18'),
    
47.         ('ABC', '41I'),
    
48.         ('3d8B', '254731'),
    
49.         ('FISHC', '18DCFB0'),
    
50.         ('python', 'B1687AEA1'),
    
51.         ('10110111010010010010101000101010', '11TIFA8BPMTL0'),
    
52.         ('10110111010010010010101000101010010101010101010010101001010100101101010101010010101001010100101010101010010101001010010101001010', '5Zr1zn3pm5znjGepqkPmDC')]
    
53. 
    
54. 
    
55. for i in Test:
    
56.     print(calc(i))
    
57. 
    
58. print(time.time()-ti)
    

复制代码

以上是完整版的，以防未来的我回头看时看不懂

1. import time
   
2. ti=time.time()
   
3. def to10(jzx,num):#转化为10进制，返回十进制数值
   
4. 
   
5.     return sum([zd[num[i]]*(jzx**(len(num)-i-1)) for i in range(len(num))])
   
6. 
   
7. 
   
8. def zh(zf): #转换zh,将字符转换为一个列表(十进制表示的数,进制x），用于比较，变量为字符zf
   
9.     zf=str(zf)#以防传入数字
   
10.     if min([i in zd for i in zf]):#判断是否含有非法字符，如果有，最小值为0
    
11.         return [[to10(i,zf),i] for i in range(max([zd[i] for i in zf])+1,63)]#返回所有列表
    
12.     else:
    
13.         return '非法字符'
    
14.    
    
15. def calc(t1):
    
16.    
    
17.     x1=zh(t1[0])#生成两个列表，储存从最小进制到62进制的进制及对应的十进制数
    
18.     x2=zh(t1[1])
    
19.    
    
20.     c=[] #临时
    
21.    
    
22.     for i in x1:#比较十进制数是否一致
    
23.         for j in x2:
    
24.             if i[0]==j[0]:
    
25.                 c.append((i[1],j[1]))
    
26.         if c!=[]:#有一致的退出，即最小值
    
27.             break
    
28.     return c if c!=[] else '无法匹配'
    
29. 
    
30. 
    
31.    
    
32. zd={} #生成字典zd,
    
33. z='0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z'.split()
    
34. for i in range(62):
    
35.     zd[z[i]]=i
    
36.    
    
37. Test = [('A', '11'),
    
38.         ('18', '18'),
    
39.         ('ABC', '41I'),
    
40.         ('3d8B', '254731'),
    
41.         ('FISHC', '18DCFB0'),
    
42.         ('python', 'B1687AEA1'),
    
43.         ('10110111010010010010101000101010', '11TIFA8BPMTL0'),
    
44.         ('10110111010010010010101000101010010101010101010010101001010100101101010101010010101001010100101010101010010101001010010101001010', '5Zr1zn3pm5znjGepqkPmDC')]
    
45. 
    
46. 
    
47. for i in Test:
    
48.     print(calc(i))
    
49. 
    
50. print(time.time()-ti)

复制代码

以上是简写版的

我的答案是：
[(11, 9)]
[(9, 9)]
[(16, 26)]
[(40, 10)]
[(36, 16)]
[(62, 16)]
[(4, 36)]
[(2, 62)]