2023年杭州北斗联盟高二期中卷第17题解析-技术圈

说在前面：

选拔人才是考试的重要目的，不但要考查学生的学业水平，还要考查学生的核心素养，筛选出具有较高信息素养和计算思维的优秀学生。压轴题就是区分普通学生和优秀学生的主战场，也成为考验命题人业务水平和控场能力的试金石。《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) + s
      
      
                n = n // 2
      
      
            return s
      
      
        
          

      
      
        def BtoD(s): #BtoD函数实现将二进制数转为十进制数
      
      
            n = 0
      
      
            for 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。本题采用了巧妙的技巧来对十进制数实现循环移位功能，提升了难度，增加了区分度。但解密算法的代码实现与算法描述不完全一致，造成理解上的困难。笔者尝试使用与加密算法恰好互逆的解密算法实现，提高了代码可读性。参考代码如下：

      
        #函数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)

答案： (1 ） xf （ 2 分） (2) ① n=n*2+int(i) （2 分） ② break （2 分） ③ n=b[i]%8*32+b[i]//8 （2 分）
拓展思考： 加密和解密算法经典实用，综合性强，难度适当，是考试命题的热点。此题给出加密算法，考查解密算法，是命题常用手法。在平时学习中，则应更注重算法的实用性和典型性，要求学生同时掌握加密和解密算法的代码实现。笔者尝试从处理二进制数字串和直接处理整数两种途径，演示按位取反和循环移位的操作方法，供大家参考，欢迎各位老师批评指正。参考代码如下：算法一：先转换成二进制数，再做按位取反和循环移位操作。

      
        def DtoBqf(d, n): #将十进制数d转为n位二进制数并取反
      
      
            s = ""
      
      
            for i in range(n):
      
      
                s = str(1 - d % 2) + s
      
      
                d = d // 2
      
      
            return s
      
      
        
          

      
      
        def BtoD(b): #将二进制数b转为十进制数
      
      
            n = 0
      
      
            for 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算法，感兴趣就一起来！

相关优秀文章：

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类