2023年杭州北斗联盟高二期中卷第17题解析
Python算法之旅
共 8516字，需浏览 18分钟
· 2024-03-31
说在前面：
选拔人才是考试的重要目的，不但要考查学生的学业水平，还要考查学生的核心素养，筛选出具有较高信息素养和计算思维的优秀学生。压轴题就是区分普通学生和优秀学生的主战场，也成为考验命题人业务水平和控场能力的试金石。 《2023年杭州北斗联盟高二期中卷》第17题考查了“加密和解密问题”，题目综合性强，问题设置巧妙，难度逐次增加，既给了中等生得分的机会，又为优等生创造了展示才华的空间，是一道具备“压轴题”特性的好题目。 当然，如果单纯从解决问题的角度来看，题目杂糅了进制转换和直接对十进制数进行循环移位处理两种方法，而且没有严格按照算法描述来编写代码，人为增加难度来提高区分度，显得不够“自然”。 笔者对原题代码进行了一些剖析，并给出了另一种更为贴合算法描述的代码实现。另外，在拓展思考中，笔者采用两种不同算法，分别实现了加密和解密功能。 由于笔者水平有限，理解可能有些不到位，若存在错误或偏激之处，敬请各位老师批评指正。题目及解析：
密码的文本（密码的组成都为 ASCII 字符），一旦文本内容泄露将造成巨大的损失。于是，小运自编了一套加密方法，对明文（原密码）的每个字符进行下列加密处理： （1）将该字符的ASCII码转换成8位二进制数（不足8位的，高位补上相应数量的0）； （2）将上述8位二进制循环左移3次(移出的数位放在最右边)；（3）将上述处理后的8位二进制数依次取反（1变0,0变1）；
（4）最后将这8位二进制分成左右两个4位二进制数，分别转换成十进制数，然后从下表中取出相应的字符作为新密码。
例如， 密码为小写字母 "a", 通过上述加密算法加密后的密文是“ Tf ” , 加密过程如下：
“a的ASCII码：01100001”➔“循环左移3次：00001011”➔“逐位取反：11110100”➔“转换为两个十进制数：15,4”➔“得到密文：Tf”。
（1）如果明文为小写字母“c”，则加密后的密文是______。 （2）根据加密的规律，小运用Python编写了一个程序，用于将加密后的新密码进行解密得到原密码，程序如下所示，请在划线处填写正确的代码：考查知识点：def DtoBqf(n): #DtoBqf函数实现将十进制数转为4位二进制数并取反s = ""for i in range(4):s = str(1 - n % 2) + sn = n // 2return s
def BtoD(s): #BtoD函数实现将二进制数转为十进制数n = 0for i in s:①return n
miwen = input("输入密文：")key = "WgQ#f02y*?ScApxT"a=[]; b=[]; n=0; ans=""; mingwen=""for i in miwen:for j in range(len(key)):if i == key[j]:a.append(j)②for i in range(len(a)):ans += DtoBqf(a[i])if i % 2 == 1:b.append(BtoD(ans))ans = ""for i in range(len(b)):③mingwen = mingwen + chr(n)print("明文为：",mingwen)
加密解密、进制转换算法、循环移位算法、自定义函数。要求学生理解加密解密基本思路和进制转换算法、熟悉字符串和列表基本操作。
解析： （1）模仿题面给出的示例，可知小写字母"c"的加密过程如下： “c的ASCII码：01100011”➔“循环左移3次：00011011”➔“逐位取反：11100100”➔“转换为两个十进制数：14,4”➔“得到密文：xf”。 （2）BtoD函数实现将二进制数转为十进制数，采用了经典的累乘相加算法，故第①空答案为n=n*2+int(i)。 第②空所在二重循环的作用是遍历密文字符串，找到每一个加密字符对应的十进制值（即在key中的下标）。当在key中找到字符i时，将其下标j存储到列表a中，并跳出循环，故第②空答案为break。当然，找到字符后不跳出循环也不是不可以，但效率就低了，不符合一般习惯。 初看第③空的答案好像是n=b[i]。但如果这样做就上当了。因为列表b中存储的是尚未循环移位的二进制数对应的整数，需要对其做循环移位操作后才能调用chr函数生成对应的字符。 那么如何直接对一个十进制整数实现二进制数循环移位的效果呢？这是本题的难点所在。 要想将二进制数的低3位循环右移到高3位（即左移5位），需要先将二进制数的低3位提取出来，方法是将十进制数对8求余数；然后再乘以32，实现左移5位的功能。最后加上原二进制数的高5位即可。故第③空答案为n=b[i]%8*32+b[i]//8。 本题采用了巧妙的技巧来对十进制数实现循环移位功能，提升了难度，增加了区分度。但解密算法的代码实现与算法描述不完全一致，造成理解上的困难。笔者尝试使用与加密算法恰好互逆的解密算法实现，提高了代码可读性。参考代码如下：
答案： (1 ） xf （ 2 分） (2) ① n=n*2+int(i) （2 分） ② break （2 分） ③ n=b[i]%8*32+b[i]//8 （2 分）#函数DtoBqf(n)和BtoD(s)与原题相同。代码略。miwen = input("输入密文：")dic_key = {'W': 0, 'g': 1, 'Q': 2, '#': 3, 'f': 4, '0': 5, '2': 6, 'y': 7, '*': 8, '?': 9, 'S': 10, 'c': 11, 'A': 12, 'p': 13, 'x': 14, 'T': 15}a=[]; b=[]; n=0; ans=""; mingwen=""for i in miwen:a.append(dic_key[i])for i in range(len(a)):ans += DtoBqf(a[i])if i % 2 == 1:ans = ans[-3:] + ans[:5]b.append(BtoD(ans))ans = ""for i in range(len(b)):n = b[i]mingwen = mingwen + chr(n)print("明文为：",mingwen)
拓展思考： 加密和解密算法经典实用，综合性强，难度适当，是考试命题的热点。此题给出加密算法，考查解密算法，是命题常用手法。在平时学习中，则应更注重算法的实用性和典型性，要求学生同时掌握加密和解密算法的代码实现。 笔者尝试从处理二进制数字串和直接处理整数两种途径，演示按位取反和循环移位的操作方法，供大家参考，欢迎各位老师批评指正。参考代码如下： 算法一：先转换成二进制数，再做按位取反和循环移位操作。
算法二：直接操作十进制数，通过求余数和整除运算实现循环移位功能，通过异或运算实现按位取反功能。def DtoBqf(d, n): #将十进制数d转为n位二进制数并取反s = ""for i in range(n):s = str(1 - d % 2) + sd = d // 2return s
def BtoD(b): #将二进制数b转为十进制数n = 0for i in b:n = n * 2 + int(i)return n
def encrypt(p_text): #将明文加密，返回密文key = "WgQ#f02y*?ScApxT" #加密密码表c_text = ""for ch in p_text:b = DtoBqf(ord(ch), 8) #此条语句的作用是什么？b = b[3:] + b[:3] #此条语句的作用是什么？c_text += key[BtoD(b[0:4])] + key[BtoD(b[4:8])]return c_text #返回密文def decrypt(c_text): #将密文解密，返回明文dic_key = {'W': 0, 'g': 1, 'Q': 2, '#': 3, 'f': 4, '0': 5,'2': 6, 'y': 7, '*': 8, '?': 9, 'S': 10, 'c': 11,'A': 12, 'p': 13, 'x': 14, 'T': 15} #解密密码表p_text = ""for i in range(0, len(c_text), 2): #2个密文字符对应1个明文字符b = DtoBqf(dic_key[c_text[i]], 4) + DtoBqf(dic_key[c_text[i+1]], 4)b = b[-3:] + b[:-3] #此条语句的作用是什么？p_text += chr(BtoD(b)) #此条语句的作用是什么？return p_text #返回明文
mingwen = input("输入明文：")#加密miwen = encrypt(mingwen)print("密文为：",miwen)#解密mingwen = decrypt(miwen)print("明文为：",mingwen)
写在后面def encrypt(p_text): #将明文加密，返回密文key = "WgQ#f02y*?ScApxT" #加密密码表c_text = ""for ch in p_text:d = ord(ch)d = d % 32 * 8 + d // 32 #此代码段的作用是什么？d = d ^ 255 #此代码段的作用是什么？c_text += key[d//16] + key[d%16]return c_text #返回密文def decrypt(c_text): #将密文解密，返回明文dic_key = {'W': 0, 'g': 1, 'Q': 2, '#': 3, 'f': 4, '0': 5,'2': 6, 'y': 7, '*': 8, '?': 9, 'S': 10, 'c': 11,'A': 12, 'p': 13, 'x': 14, 'T': 15} #解密密码表p_text = ""for i in range(0, len(c_text), 2): #2个密文字符对应1个明文字符d = dic_key[c_text[i]] * 16 + dic_key[c_text[i+1]]d = d ^ 255 #此代码段的作用是什么？d = d % 8 * 32 + d // 8 #此代码段的作用是什么？p_text += chr(d)return p_text #返回明文
mingwen = input("输入明文：")#加密miwen = encrypt(mingwen)print("密文为：",miwen)#解密mingwen = decrypt(miwen)print("明文为：",mingwen)
为了保证解析的原创性和思维的独特性，我都是独立解题后，先不看答案(除非题目不会做)，直接把解析写好，再去看答案。
当然，如果发现参考答案有更好的思路，我还是很乐于学习和借鉴的。同时，由于本人水平有限，解析中难免出现疏漏甚至错误之处，敬请谅解。
无论是赞同还是反对我的看法，都请你给我留言。如果你有新的想法，千万不要憋在心里，请发出来大家一起讨论。让我们相互学习，共同进步！
需要本文word文档、源代码和课后思考答案的，可以加入 “Python算法之旅”知识星球 参与讨论和下载文件， “Python算法之旅”知识星球 汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。
我们专注Python算法，感兴趣就一起来！
相关优秀文章：
评论
经典闭包题解析
问：下面代码中，标记?的地方输出分别是什么？function fun(n, o) { console.log(o) return { fun: function (m) { return fun(m, n); } };}var a = fun(0); // ?a.fun(1); // ...
MoMaek
0