教科版 高二选择性必修1信息技术第2单元第3课《字符串应用》课件+教案

2.3字符串应用高中信息技术/教科版/选择性必修1目录1.案例导入2.体验探究3.编程实现4.课堂小结1.案例导入字符串使用案例在文本编辑软件中利用“查找”命令，可以在指定的文本信息中查找特定形式的字符串；在邮件过滤器中，根据事先定义的字符串属性特征，通过获取电子邮箱地址、标题及正文来识别垃圾邮件。另外，在文本挖掘、机器翻译、信息检索、问答系统和对话系统等自然语言处理技术中，也随处可见字符串的身影。2.新课讲授学习任务本节围绕“破译恺撒密码”项目展开学习，通过项目活动熟悉字符串的基本操作，理解字符串抽象数据类型的定义，并利用字符串的基本方法编程实现破译恺撒密码的操作。本节主要包含“体验手动破译恺撒密码”和“编程实现破译恺撒密码”两个任务。“恺撒密码”的历史故事 任务一 体验手动破译恺撒密码 活动1体验恺撒加密恺撒加密作为一种最为古老的加密技术，在古罗马的时候就已经很流行。它通过把字母移动一定的位数来实现加密。明文中的所有字母都在字母表上向左 (或向右) 按照某个位数进行偏移后被替换成密文，其中的位数就是恺撒密码加密和解密的密钥。明文: Imagination is more important than knowledge.密钥:3当密钥为3时，所有字符向左偏移3位，加密时明文里所有的字母A将被替换成X，B变成Y，以此类推，X将变成U，Y变成V，Z变成W，如下图所示。 任务一 体验手动破译恺撒密码 活动1体验恺撒加密明码表密码表请补全加密后的密文: fp jlob fjmloqxkq . 明文: Imagination is more important than knowledge.密钥:3FJxdfkxqflkqexk hkltibadb 任务一 体验手动破译恺撒密码 活动2体验恺撒解密明码表密码表请补全解密后的明文: great was ever without . 密文: Fglzafy yjwsl osk wnwj suzawnwv oalzgml wflzmkaske密钥:8当密钥是8的时候，解密时密文里所有的字母A将被替换成I，B变成J，以此类推，X将变成F，Y变成G，乙变成H，如图所示。Nothingachievedenthusiasm字符串及其概念字符串:是一种由字符构成的线性结构。上面活动中的明文和密文均是字符串，字符串中的每个字符从左到右依次排列，且有确定的位置。字符串中第一个字符的位置下标是0，可以根据字符在字符串中的位置下标来访问字符。 任务一 体验手动破译恺撒密码 活动2体验恺撒解密字符串长度:字符串所含字符的总数称为字符串的长度，长度为0的字符串称作空字符串或空串。子串:字符串中某一连续的片段称为字符串的子串。任何字符串都是自己的子串。 任务一 体验手动破译恺撒密码 活动2体验恺撒解密字符串s="Data Structure”由14个字符构成，因此字符串长度为14，其中位置下标为5的字符是“S“ata”是字符串s的个子串。 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码密文:pqrabkqzxoapqrxoq线索:信息中包含了Stuar，不区分大小写，共有17个字符。恺撒加密技术的密钥是有限的，只有1~25，所以可以用穷举的方法来破译密文。可分三步操作来破译密文。(1)对“stuart”加密，选代循环，密匙从1到25；(2)在任务给的密文里面查找“stuart”的密文；(3)如果存在即可以知道密钥，进而破译密文； 否则密钥增加1，继续进行操作(1)。 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码”stuart”的密文为“rstzqs“。手动的字符串查找当密钥为1时，过程如下:字符串“pqrabkqzxoapqrxoq”为目标串T，字符串“rstzqs”为模式串P。分别写在等间距格子的纸带上，字符串T的纸带固定不动，字符串P的纸带的首字符与字符串T的首字符对齐，如图所示。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码第1轮匹配:从目标串T的第一个字符开始，将T和P对应的字符逐个依次比对。如图所示，第一个字符“p”和“r”不相同，此轮匹配失败。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ≠ 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码第2轮匹配:将模式串P向右移动一个字符，继续将T和P对应的字符逐个依次比对。如图所示，比较的字符对不相同，此轮匹配失败。模式串P0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ≠ 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码第3轮匹配:将模式串P向右移动一个字符，继续将T和P对应的字符逐个依次比对。如图所示，比较的首字符相同，但下一个字符对“a”和“s”不相同，此轮匹配也失败。模式串P0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 =≠ 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码第4轮匹配:将模式串P向右移动一个字符，继续将T和P对应的字符逐个依次比对。如图所示，比较的首字符不相同，此轮匹配也失败。模式串P0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ≠ 任务一 体验手动破译恺撒密码 活动3手动破译恺撒密码第5~17轮匹配:每轮匹配均失败。“stuart”的密文为“qrsypr”，手动查找字符的结果密钥为2时，字符匹配失败。当密钥为2时，stuart”的密文为“qrsypr”，手动查找字符的结果是字符匹配失败。当密钥为3时，“stuart”的密文为“pqrxoq”，手动查找字符的结果是在第12轮字符匹配成功。经过解密，密文对应的明文是 。studentcardstuart字符串匹配的方法(1) 字符串匹配检测需要进行多轮，首轮匹配检测的起始端从目标串T的第一个字符开始。(2)将目标串T和模式串P的对应字符逐个依次比对，如果所有字符都相同，匹配成功，操作结束;否则只要有任一个字符不同，本轮匹配失败，执行 (3)，进行下一轮匹配检测。(3)若T和P的右边界已对齐，整个匹配检测过程失败;否则，将匹配检测的起始端在T中后移一位，执行(2)。字符串匹配在字符串中检测查找特定形式的字符串的这类操作都属于字符串匹配(string matching)。即给定目标串T和模式串P之后，判定T中是否存在某一子串与P相同，如果存在则匹配成功。字符串匹配的应用非常广泛，比如垃圾邮件的检测、搜索引擎关键字的查询、网络热搜排行榜的更新等都会用到字符串匹配操作。字符串抽象数据类型的定义字符串抽象数据类型的定义 任务一 体验手动破译恺撒密码 活动4体验字符串基本方法的操作Python内置的字符串类型str是字符串抽象数据类型的一种具体实现，对于抽象数据类型中定义的每个接口，Python的字符串类型都有对应的实现，可以根据需要直接调用。若字符串s="imagination is more important than knowledge"，如图所示，请完成下表。 任务一 体验手动破译恺撒密码 活动4体验字符串基本方法的操作“i” 任务一 体验手动破译恺撒密码 活动4体验字符串基本方法的操作“Imagination is more important than knowledge”“Imagination is more important than knowledge data Structure”“gination”3.编程实现 任务二 编程实现破译恺撒密码 活动1建立数据结构密文: sohdvhzulwhwkhqdphriwkhiluvwsurjudpphulqwkhzruog。线索:明文中包含有“programmer“根据字符串的抽象数据类型的定义，首先创建两个字符串对象分别来保存已知密文目标串T和线索模式串P。01.#密文目标串初始化02.tStr="sohdvhzulwhwkhqdphriwkhiluvwsurjudpphulqwkhzruog”03.pStr="programmer" #线索模式串初始化 任务二 编程实现破译恺撒密码 活动2算法设计与实现密文: sohdvhzulwhwkhqdphriwkhiluvwsurjudpphulqwkhzruog。线索:明文中包含有“programmer“根据字符串的抽象数据类型的定义，首先创建两个字符串对象分别来保存已知密文目标串T和线索模式串P。01.#密文目标串初始化02.tStr="sohdvhzulwhwkhqdphriwkhiluvwsurjudpphulqwkhzruog”03.pStr="programmer" #线索模式串初始化 任务二 编程实现破译恺撒密码 活动2算法设计与实现如前所述，利用字符串的基本操作实现破译恺撒密码的算法描述如下。(1)对已知线索字符串加密，密钥初始值为1。(2) 在任务二给出的密文里面查找线索字符串的密文。(3)如果存在即可以知道密钥，进而破译密；;否则密钥增加1，继续进行操作(1)。根据以上算法，定义加密函数enCrypt(message,key)，参数key是密钥，message是明文，根据密钥key对明文message进行加密。若左移后的位置大于0则直接左移，否则需要回到字母表末尾继续计算移动位置，这里用对26求余得出移动位置。请补全下面的代码。 任务二 编程实现破译恺撒密码 活动2算法设计与实现04.#加密函数05. def enCrypt(message, key) : #用key对message加密06.alphabet='abcdefghijklmnopqrstuvwxyz' #字母表07.encrypted=' ’ #加密后的密文08.for char in message: #对明文字符依次加密09.if char not in alphabet: #非字符不变10.encrypted=encrypted+char11.else: #字符加密12.rotatedIndex=alphabet.index(char)-key #左移位数 任务二 编程实现破译恺撒密码 活动2算法设计与实现13.#位数对26求余14.encrypted=encrypted+ .15.return encryptedalphabet[rotatedIndex%26] 任务二 编程实现破译恺撒密码 活动2算法设计与实现在任务二给出的密文里面查找线索字符串的密文可以通过字符串匹配算法来实现，具体描述如下。(1) 字符串匹配检测需要进行多轮，首轮匹配检测的起始端从目标串T的第一个字符开始。(2)将目标串T和模式串P的对应字符逐个依次比对，如果所有字符都相同，匹配成功，算法结束;否则只要有任一个字符不同，本轮匹配失败，执行(3)，进行下一轮匹配检测。(3)若T和P的右边界已对齐，整个匹配检测过程失败;否则，将匹配检测的起始端在T中后移一位，执行(2)。 任务二 编程实现破译恺撒密码 活动2算法设计与实现以上算法可以用嵌套的for循环实现字符串匹配过程，外层的for循环实现每轮匹配检测向右移动，内层的for循环实现依次比对字符。以下代码是通过函数stringMatch(t,p)实现字符串匹配的过程。请补全下面的代码。16. #字符串匹配函数17. def stringMatch(t,p): 18. n=len(t) #目标串长度 19.m=len(p) #模式串长度20.for i in range(n-m+1): #字符串匹配过程 21. for j in range(m): #字符比对过程 任务二 编程实现破译恺撒密码 活动2算法设计与实现以上算法可以用嵌套的for循环实现字符串匹配过程，外层的for循环实现每轮匹配检测向右移动，内层的for循环实现依次比对字符。以下代码是通过函数stringMatch(t,p)实现字符串匹配的过程。请补全下面的代码。16. #字符串匹配函数17. def stringMatch(t,p): 18. n=len(t) #目标串长度 19.m=len(p) #模式串长度20.for i in range(n-m+1): #字符串匹配过程 21. for j in range(m): #字符比对过程22.if #字符不同23.break24.else: #匹配成功25.return i26.return -1 #匹配失败t[i+j]!=p[j]: 任务二 编程实现破译恺撒密码 活动2算法设计与实现最后还需要定义解密函数deCrypt(message,key)，参数key是密钥，message是密文，依据密钥key对密文message进行解密。若右移后的位置小于26则直接右移，否则需要回到字母表首位继续计算移动位置，这里用对26求余得出移动位置。请补全下面的代码。27.#解密函数28.def deCrypt(message, key) : #用key对message进行解密29.alphabet='abcdefghijklmnopqrstuvwxyz’ #字母表29.decrypted=' ’ #解密后的明文31.for char in message: #对密文字符依次解密 任务二 编程实现破译恺撒密码 活动2算法设计与实现32.if char not in alphabet: #非字符不变33. decrypted=decrypted+charelse: #字符右移34.else：35.rotatedIndex= .##右移位数36.#位数对26求余37.decrypted=decrypted+alphabet[rotatedIndex % 26]38.return decrypted输出破译后的明文的程序代码如下所示。alphabet.index(char)+key 任务二 编程实现破译恺撒密码 活动2算法设计与实现39.#输出明文40. for key in range(1,26): #密钥依次递增41.#密文字符串匹配42.if stringMatch(tStr.lower(),enCrypt(pStr,key))!=-1:43. print(deCrypt(tStr.lower(),key)) #解密密文44.break4.else:46.print("can not find it")4.课堂小结本节可我们学习了一种特殊的线性数据结构——字符串。通过活动熟悉了字符串的基本操作，总结·了字符串抽象数据类型的定义，并利用字符串的基本方法编程实现破译了恺撒密码的操作！请同学们认真完成教材中的拓展练习哦！下节课见！