python程序设计教学基础实例-课程word公开课.docx

Python程序设计教学基础实例

浙江省普通高中

Python程序设计教学基础实例

浙江省浦江中学 方春林

目 录
第一讲 取数问题 ………………………………………………….. 3
第二讲 最值问题 ………………………………………………….. 5
第三讲 累加专题 ………………………………………………….. 7
数字累加
字符串累加
第四讲 秦九韶算法 ……………………………………………… 12
第五讲 对称数（回文） ………………………………………….. 14
第六讲 进制转换专题 …………………………………… 17
十进制数转二进制数
二进制数转十进制数
二进制与十六进制相互转换
第七讲 字符串专题 …………………………………………… 23
字符串基本操作
字符串中取数字
字符串中取单词
字符串中统计
字符串加密
第八讲 “数”问题 …………………………………………….. 37
质数
最大公约数
斐波那契数列
第九讲 约瑟夫问题 ………………………………………………. 42

第一讲 取数问题

中国象棋是中国的一种二人对抗性游戏的棋戏，可以修心养性，陶冶情操，丰富文化生活，深受广大群众的喜爱。玩象棋时，必须先确定动哪一个“棋子”，然后将“棋子”移动到下一步；数学上计算两数之和，要先确定是哪2个数做加法运算；在windows中要删除某个文件，需要先选择要删除的文件，然后再执行删除操作；……我们做任何事，必须先弄清对象，然后再执行相应的操作。
编写程序，就是将任务用计算机能看懂的语言一行行地写好，然后交给计算机一步一步执行。计算机执行指令，也需要先确定要操作的对象，比如做加法指令，必须确定要操作的两个数据。而很多时候，需要指定数据中获取需要的数据——这就是取数问题。
根据目标数据类型不同，取数问题可以分为整数型中取数问题和字符串中取数问题。下面分这两种类型分别讲解如何取数。
1.整数型
对于整数型数据，利用整除和取余方法获取各位上的数字
① 已知一个两位数x，写出该数的个位数a及十位数b的python表达式
a = x % 10 # x除以10的余数就是个位数
b = x // 10 # 整除10得到十位数
② 写出三位数x的个位数a，十位数b，百位数c的python表达式
a = x % 10
b = x // 10 % 10 (或者 b = x % 100 // 10)
c = x // 100
2.字符串型
字符串取子串用切片；s[start:end:step]表示从索引start开始取，直到索引end为止，但不包括索引end，步长step。举例如下：

练习

① 写出计算一个三位整数x的各位数之和的python表达式。
② 根据18位身份证号码sfz，写出计算年龄的python表达式。
③ 写出以一个三位数x开头的对称数的python表达式，如x=123,则输出123321。
④ 写出以n位字符串s开头的长度2n-1位的对称字符串的python表达式，如s="abcdef",则输出"abcdefedcba"。

第二讲 最值问题

最值指在一个数据范围中的最大值或最小值。比如2500名学生成绩数据中找出成绩最好的学生；在一段字符串中找出最大的字符等等。
1.求最值一般的思路
① 假定第一个数据最大并赋值给Maxx；
② 取出下一个数与最大值Maxx比较，若大于最大值Maxx，则更新最大值Maxx，直到枚举完所有数据；
2.求最值程序模板
Maxx = List[0] #List为数据集合
for item in List[1:]: #第2个元素开始枚举数据
if item > Maxx: #取出的数据大于Maxx的更新Maxx
Maxx = item
3.实例讲解
输入一串字符串，输出该字符串中最大的字符。
思路：该问题是最值问题，可以直接应用求最值的程序模板，代码如下:

4.python方法求最值
python中提供了函数max(),min()分别求最大值,最小值。
max()函数原型
max(iterable, *[,key,default])
参数：iterable,表示可迭代对象，数据集合
函数功能：取传入的多个参数中（或可迭代对象元素中）的最大值。
min()函数原型
min(iterable,*[,key,default])
参数：iterable,表示可迭代对象，数据集合
函数功能：取传入的多个参数中（或可迭代对象元素中）的最小值。
举例如下：

上述实例，可以利用max()函数实现，代码为：maxchar = max(strs)

练习

① 输入批量数据，编程输出该批量数据中的最大值，最小值。
② 输入一个三位数，将该数各位上的数字重新排列得到新整数，求最大整数和最小整数。
③ 输入一个正整数，将该数各位上的数字重新排列得到新的整数，求最大整数和最小整数。

第三讲 累加专题

3.1 数值累加
《道德经》 ：“九层高台，起于累土。” 累：积累，叠加。加：增加。累加：在原有基础上添加。我们讲累加是指批量数据做加法运算。根据数据类型的不同，分数值累加和字符串累加两类问题进行讲解。本节介绍数值累加。
1.问题引入
①计算s=1+2+3的和
我们可以按如下分步运算
s=0
s=s+1
s=s+2
s=s+3
经过以上4个步骤，可以得到s的结果。
②如果计算s=1+2+3+…+100呢，也可以分步完成
s=0
s=s+1
s=s+2
...
s=s+100
如何将上述计算过程转化为程序代码呢？编程也可以像数学上的提取公因数法，取出每个语句的公共部分，然后加上不同的部分来写代码。

上述的100(n=100)条语句可以简化为一条语句s=s+ x ,然后让x在[1,n]之间逐一枚举。要实现[1,n]之间逐一枚举，可以使用for语句和range对象实现。因此计算s=1+2+3+...+100的代码可以如下：

2.数值累加模板
累加程序的代码可以用以下通用模板（写程序也可以用模板，简化写程序的过程）。

在该模板中，程序将实现n个X的累加；X是每一个需要累加的数据，可以用python表达式表示，累加程序关键是变量X如何表达。
3.python方法实现累加
python使用函数sum()函数累加。该函数的原型如下sum(iterable[,start])
参数说明：
iterable -- 可迭代对象，如：列表、元组、集合。
start -- 指定相加的参数，如果没有设置这个值，默认为0。
返回值：计算结果。
4.实例讲解
① 编程实现计算s=1+1/2+1/3+…1/n 的值(n<=100)
本问题是n个数相加的问题，可以应用累加模板，计算范围是[1,n]，变量X = 1 / i。因此该问题可以写成如下代码：

【pythonic】利用函数sum()计算累加,构造好迭代对象即可。
s = sum([1 / k for k in range(1,n + 1)]) ，其中
[1 / k for k in range(1,n + 1)]为列表生成式，该表达式生成列表[1,1/2,1/3,..,1/n]。
② 编程实现s=1+3+5+…+n (n<=100)
本问题是n个数相加的问题，可以应用累加模板，计算范围是[1,n]，变量x是范围中的奇数。代码如下：

【pythonic】先生成迭代对象，再利用函数sum()求和
[k for k in range(1,n,2)]该列表生成式生成[1,3,5,…]范围内的奇数。代码如下： s=sum([k for k in range(1,n,2)])

练习

① 编程计算s=1+(1+2)+(1+2+3)+…+(1+2+3…+n) (n<=10000)。
② 编程计算s=1-2+3-4+…+n(n<=10000)。
③ 编程实现100以内能被3整除数的和。

3.2 字符串累加

字符串累加是指批量字符串前后连接起来，生成新的字符串。
1. 问题引入
① 输入5，屏幕上显示”12345”。
本题的结果是将数据1,2,3,4,5前后拼接得到，这是字符串的累加。按1,2,3,4,5的先后顺序将数据累加。最先出现的1在最前面，最后出现的5在最后面。这就像排队时，先来的人排在前面，后来的人排在后面。我把它称为“排队累加”。代码如下：

运行结果如下：

② 输入5，屏幕是上显示”54321”。
本题也是将数据1,2,3,4,5拼接得到的结果，拼接的时候是最先出现的1在最后面，最后出现的5在最前面。这就像排队时，后来的人插队，排在了前面。我把它称为“插队累加”。代码如下：

运行结果如下：

2.字符串累加模板
“排队累加”中看出变量i从1递增到5，程序每次将i累加到字符串s的后面。程序模板如下：

x是待累加的字符串数据，s是累加的结果。
“插队累加”中看出变量i从1递增到5，程序每次将i累加到字符串s的前面。程序模板如下：

x是待累加的字符串数据，s是累加的结果。
3.实例讲解
输入数据5，在屏幕上打印如下的数字图形。

排队累加
插队累加
从图上看出输出共5行，第i行打印的数据是第i-1行的内容加上i，因此这是字符串累加问题。再观察发现左边的是字符串的排队累加，右边的是插入累加，代码如下：

练习

① 十进制数转BCD码。5421BCD码是一种采用四位二进制数表示一位十进制是的编码，其各位的权依次为5，4,2,1，并要求大于等于5的十进制数所对应的编码最高位为1（如十进制数7所对应的“5421BCD”码为1010）。转换时，将十进制数从右往左按位转换成对应的“5421BCD”码，然后依次连接。(程序运行如右图)
② .输入1个整数，输出如下的图形。

第四讲 秦九韶算法

秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法。一般地，一元n次多项式的求值需要经过(n+1)*n/2次乘法和n次加法，而秦九韶算法只需要n次乘法和n次加法。

1.数学描述
把一个n次多项式改写如下所示：

求多项式的值时，首先计算最内层括号内一次多项式的值，
ans0 = an
ans1 = ans0 * x +an-1
然后由内向外逐层计算一次多项式的值，即
ans2 =ans1 * x +an-i
……
ansn=ansn-1*x+a0
这样，求n次多项式f(x)的值就转化为求n个一次多项式的值。
2.算法描述
① 输入f(x)的系数a0,a1,…,an，输入x的值
② 答案ans初始化为an
③ 对于I =1,2,3…，n，循环执行ans=ans * x +an-i
④ 输出ans
3.流程图描述

4.程序代码
n = int(input("请输入多项式项数\n"))
xs = list(map(int,input().split()))
x = int(input("输入x的值"))
ans = xs[n]
for i in range(1,n + 1):
ans = ans * x + xs[n - i]
print(ans)
xs列表中存放多项式系数，多项式格式为：
f(x)=xs[n]*x**n+xs[n-1]*x**(n-1)+…+xs[1]*x+xs[0]

练习

① 输入一个正整数，计算各位数之和。

第五讲 对称数(回文)

对称数是指从左到右读和从右到左读是完全一样的数据。下面分数值类型和字符串类型两类进行描述。
1.对称数
1.1 对称数的判断思路及算法
判断某数是否为对称数，只需要生成该数的逆序数，然后判断这两者是否一致。生成逆序数的方法可以使用秦九韶算法。
如数据x = 12321,生成它的逆序数的方法

逆序数结果保存在变量rst中，首先赋初值0即rst = 0，接下来的步骤如下：
①取出倒数第1位1，并计入结果变量rst中,rst = 10 * rst + 1
②取出倒数第2位2，并计入结果变量rst中,rst = 10 * rst + 2
…
⑤取出倒数第5位12，并计入结果变量rst中,rst = 10 * rst + 1
最后再判断x 和rst是否相同，相同为对称数，否则不是。
1.2.对称数代码实现

1.3.生成对称数
从数字1开始连续递增生成指定长度（不超过18位）的对称数。如长度为5，则生成对称数12321，长度6，则生成123321。
思路：生成n位对称数，根据n的奇数偶数分别来生成对称数。步骤如下：
①先生成前半部分，从1开始循环到n // 2结束，利用秦九韶算法生成整数并存储在rst；
②若n为奇数，则将中间数(n+1) // 2，添加到rst尾部；
③再生成后半部分，从n//2开始到1结束，利用秦九韶算法生成整数并存储在rst；
1.4 生成对称数代码
方法1：对称数分前后2部分分别生成

方法2：1个循环生成对称数(n为正奇数)
分析：奇数个数的对称数的特点，如对称数123454321，中间数mid=5。

第1个数x=1，与mid 相差y=4
第2个是x=2，与mid 相差y=3
第3个是x=3，与mid 相差y=2
…
第7个数x=3，与mid相差y=2
第8个数x=2，与mid相差y=3
第9个数x=1，与mid相差y=4
发现规律没有？
x 加 y(x与mid的差值的绝对值)等于1个常量（mid的值）。
代码如下：

2 对称字符串（或回文）
2.1 对称字符串的判断2个思路
思路1：与对称数的判断方法一样，利用字符串累加方法生成原始字符串的逆序字符串，然后判断生成的字符串与原始字符串是否相同。（代码请同学们完成）
思路2：假定字符串长度为n，逐个判断第1个和倒数第1个是否相同，…，第i个与第n-i-1个是否相同，直到n // 2为止。若有一次取出的前后两个字符不相同，说明不是对称字符串，否则就是对称字符串。
2.2思路2 程序代码

3 生成对称字符串
生成对称字符串与生成对称数类似，不同的数据类型发生改变，原来是数字，现在变成字符串。
3.1 生成以字符”a”开始长度n(n<=52)的字符串。思路与生成对称数一样，有两种不同的方法。
思路1 分前后两部分生成。
思路2 利用字符串累加原理。（请自行完成代码）
思路3 利用一个循环一次生成循环序列。（请自行完成代码）
思路1 程序代码：

练习

① 生成对称字符串的其它两个思路的程序实现。
② 编写程序生成左下图的菱形。

第六讲 进制转换专题

计算机中所有数据都用二进制表示，而现实生活中更多的是十进制的数据。因此需要对不同的进制进行转换。

6.1 二进制数转十进制数

1.二进制数转换为十进制数算法及程序实现
以二进制数”1011B”转换为十进制数为例讲解转换步骤。
方法1：逐位按权值求和（从左往右）
1011B=1*2^3+0*2^2+1*2^1+1*2^0 ①
思路：上述表达式①中可以看成是4个数字x相加，每个x有什么特征呢？x是二进制数的某1位数字 * 相应的权值。该过程就是一个4个数据累加的过程，因此可以用累加语句模板来实现将二进制数转换为十进制数。
代码实现

方法2：逐位按权值求和（从右往左），这是取的方向不一样，结果是一致的。
1011B=1*2^0+1*2^1+0*2^2+1*2^3 ②
思路同方法1，只是数据的位置发生改变，代码如下：

上述代码中，如果熟练了就没有必要变量a,b分步写，可以直接写一个表达式。这样写为了让学生初学时更好理解。
方法3：运用秦九韶算法，该算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法。通俗的说十进制数x，在其尾数加一位数y，得到新的数z，则z=10*x+y；同理对于任何二进制数x，其尾数加一位数y，得到新的数z，则z=2*x+y。
将二进制数“1011B”转换为十进制数的分步过程如下表
1011B
二进制数每1位
初始值s=0
第1次取的数
1
s=2*s+ 1
第2次取的数
0
s=2*s+ 0
第3次取的数
1
s=2*s+ 1
第4次取的数
1
s=2*s+ 1
经过以上4个步骤，s的值就是该二进制数所对应的十进制数。怎么转换为代码呢，通过观察同样是累加问题。应用累加模板代码得到如下代码：

以上是二进制数转换为十进制数的3种方法，1，2两种方法其实是一样的，只是顺序不一样而已，第3种方法比较简单明了。其它进制转换为十进制数原理是一样的，只需要将相应的权值基数2改掉即可，如十六进制转为十进制数，将程序中2改成16即可。
2.pythonic
Python实现上述问题，有pythonic的方式实现。现介绍2种方法：
①列表生成式

②利用lambda表达式和reduce()函数

③除此之外，python利用int()方法，将一个数字字符串转换十进制数。
函数int()原型
class int(x, base=10)
参数
x -- 字符串或数字。
base -- 进制数，默认十进制。
返回值
返回整型数据
函数int()一般用于将数值字符串转换为数字（十进制数），但是如果加上base参数，就可以将不同进制数转换为十进制数。如上述的二进制数”1011B”转换可以用下面的代码。

练习

① 编程实现十六进制数转换为十进制数。
② [浙2018.4选考14]某种编码以 4 位二进制码为一组，每组前两位表示方向，后两位表示距离。编写一个程序,将编码翻译成方向和距离，距离值为每组编码后两位二进制码转换为十进制数的值。（如右图）

6.2 十进制数转二进制数

1.十进制数转二进制数的方法：辗转相除取余法
十进制数转换为二进制数的步骤
①13除以 2，得到商6，余数1；
②6 除以2，得到商3，余数0；
③3 除以2，得到商1，余数1；
④1 除以2，得到商0，余数1；
⑤商为0，结束。
依次将步骤④③②①得到的余数前后连接起来，结果是(1101)2
注意结果是余数的倒序排列。可以应用字符串的插队累加模板。

2.程序实现
思路：除2取余法，并利用字符串的插队累加得到最终结果。

3.十进制数转十六进制数
思路：与十进制数转二进制数一样，只需要将权值2改为16；同时处理好余数大于9的数字转换为字母"ABCDEF"的问题。代码如下：

上述代码中取得的余数转换成十六进制数应用了一个对照表；也可以利用chr()函数将大于9的数值转换为十六进制元素"ABCDEF"，代码如下：

练习

① [浙17.4学考14]奇偶校验是一种校验数据传输正确性的方法。其中奇校验方法：统计二进制数据的数位中“1”的个数，若个数为奇数，则校验位值为0，否则校验位值为1。小李编写了一个计算奇校验位值程序，功能如下：输入1～255十进制待校验数，输出该数的二进制数及校验位值。
② 编写程序求一个负整数的反码。（提示：原码即将一个整数转换为二进制数，正数的反码等于原码，负数的反码等于原码逐位取反）
③ 求一个十进制负数(范围-127~-1)的8位二进制补码。

6.3 二进制与十六进制相互转换

1 十六进制数转换为二进制数
思路：将十六进制数中的每一位转换为四位二进制数并累加；本问题难点是将十六进制中的元素A-Z转化为相应的十进制数10-15。代码如下：

2 二进制数转换为十六进制数
思路：将二进制数从右往左每隔4位分割，并将之转换为一位十六进制数，最后逐位按字符串插队累加。

程序将四位二进制数转换为十进制数自定义了一个函数btod来实现，也可以使用int()函数来实现该问题。本实例是从右往左逐位取出并转换为十六进制数，也可以从左往右取出，并将之转换为十六进制数；代码请自行实现。

第七讲 字符串专题

7.1 字符串一般操作

字符串的一般操作有字符串的插入，删除，修改，查找等操作。
1.查找
在字符串source中查找指定的关键字key，若存在，则返回第1次出现该key的位置，否则返回-1。
思路：从字符串第1个位置开始，取出关键帧key长度的子串，并与关键字key比较，若相同则返回该位置，否则继续，直到字符串结束。
程序代码实现

2.插入字符串
编写函数实现字符串中指定位置前插入指定的字符串key
思路：先找到插入字符串的位置，然后插入指定的字符串key。
程序代码1：利用切片实现

程序代码2：用循环逐一取字符并累加到结果变量中

该函数参数说明：strs原始字符串，pos待插入的位置，key待插入的字符串。
3.删除字符串
输入原始字符串，输入待删除的key，返回删除key后的字符串。例如原始字符串souceStr=”abcabdabcfab”，key=”abc”。如下图：

i i
思路1：原始字符串不变，将与key比较后，不同的字符串保存到新的变量中。算法流程如下：
置初值i=0
① 当i<= len(sourceStr)-len(key)，从位置i开始取出子串(长度len(key))。将取出的子串与key比较，若相同转②，否则转③
② i = i + len(key)，转①
③ 将该字符souceStr[i]累加到结果变量result中，并转①
程序代码如下：

思路2：找到key字符串后修改原始字符串
置初值i=0，s=len(sourceStr)
① 当s-i>= len(key)，从位置i开始取出子串(长度len(key)),将取出的子串与key比较，若相同转②，否则转③
② 将key内容从原始字符串中删除，转①
③ 继续下一个位置查找即i=i+1，并转①
程序代码如下：

4.其它：将字符串中的小写字母变大写字母
(1)常规思路：枚举字符串中每1个字符，碰到小写字母的将之转换为大写字母。因为字符串是不可变对象，因此，需要定义一个新的对象保存新的字符串。
程序代码如下：

(2)pythonic方法
python中提供lower()、upper()、capitalize()、title()、swapcase()
这几个方法分别实现字符串转换为小写、大写字符串、字符串首字母变为大写、每个首字母变为大写以及大小写互换。因此，上述问题可以用如下代码实现：
rst = strs.upper()
print(rst)
字符串函数的使用举例

运行结果

练习

① 输入数字的年份转换为中文年份，比如输入2018，输出“二0一八”。
② 输入一串字符，将字符串后面相同的字符删除只剩下一个。

③ 输入一个大于10000的正整数，程序会去除其中4个数字，在保证余下的数字不改变顺序的情况下其数值最大。运行结果如下图。

7.2 字符串中取数字

取出字符串中连续数字，并加以处理。如有字符串”aba123aA456a655”，则输出[123,456,655]。本节讲解解决该问题的3种思路。
思路1.数字字符串累加法
从字符串第1个字符开始，碰到数字的，把它取出来累加到变量中，碰到非数字字符时，将变量追加到结果列表中，同时清空变量，重复上述过程，直到字符串结束。

【思考】①处的if语句去掉，分析对程序结果有什么影响？
思路2 切片法
从字符串第1个字符开始，碰到数字的，统计数字出现的次数，碰到非数字字符时，利用切片将该位置之前的长度为num的数字字符串取出来，并记录到结果列表中，同时清空计数变量num，重复上述过程，直到字符串结束。

思路3 利用秦九韶算法取出数字
从字符串第1个字符开始，碰到数字的，把它取出来，利用秦九韶算法累加到变量num中，当碰到非数字字符时，将变量追加到结果列表中，同时清空变量num，重复上述过程，直到字符串结束。

【思考】 本程序中变量c的作用是什么？
小结
字符串一重要公式：下标与长度之间的关系
下标
0
1
2
3
4
5
6
7
8
9
数据
a
b
c
1
2
d
5
f
7
8

i j
上图中起始下标i，结束下标j，长度L与i,j的关系如下：
L = j + 1 – i
字符串切片或range(start,end,step)生成对象时，因为end不包括，所以要生成s[i:j](包含j)时必须用s[i:j+1] 或range(i,j+1)。
字符串中取数问题中的思路2就是应用了该公式。

练习

① 输出字符串中连续数字的最大值。如” (5YgYi\qIy6(uVC4;81Sk”最大数是81。
② [浙2018.11选考14]在平面坐标系中，给定一组有序的点。从原点出发，依次用线段连接这些点，构成一条折线。要求编写一个“计算折线长度”的程序，功能如下：输入这些点的坐标值（数据都用逗号分隔并以逗号结尾），程序计算这条折线的长度。例如，三个点的坐标为(5,10),(8,12),(6,17)，则输入的字符串strs=”5,10,8,12,6,17，”，输出20.17。
③ [浙2017.11选考14]编写“字符串生成”程序，实现如下功能：输入多个正整数 (以“，”为分割符和结束符，这些整数代表字符位置），程序以这些整数为位置信息，依次从原始字符串（字典内容）提取字符并连接成新的字符串，最后输出将新的字符串（如右图）。

7.3字符串中取单词

给定一段文本中拆分单词，拆分规则是一个单词以字母开头和结束。实现的思路可以参考字符串中取数字。
实例1 一段文本中拆分单词，将单词取出存入列表。
思路1 位置法：枚举文本的所有字符，记录单词中字符的个数，以及单词的结束位置，截取单词。代码如下：

思路2 累加法：枚举文本的所有字符，遇到字母开头的，将字母累加，遇到非字母时，将累加的单词添到列表中。代码如下：

实例2 编写程序实现英文句子每个单词首字母大写。
思路1：首先判断文本首字符是否首字母，若是将之改成大写后保存到结果字符串中；否则直接复制到结果变量；之后枚举其他字符，并根据规则改写大写；判断首字母的条件是，当前字符是英文字母，其前一个为标点符号如" ,.;!?"。程序代码如下：

思路2 pythonic方法
python中提供字符串的title()方法，自动将单词首字母变大写。使用方法如下：

练习
① [2017.4浙选考16] 小王编写了一个实现文字查找替换功能的程序，输入原始字符串，待查找的key，输入替换的文本。 如下图。
② 字符串分行将字符串分行（分行时单词不得跨行，每行字符尽可能多但不超过40个）分行算法如下：
(1) 将文本框中的字符串保存到变量s中；
(2) 当s中字符个数超过40时，循环执行下列Ⅰ，Ⅱ步，否则跳转到(3)
Ⅰ.如果第41个字符不是英文字母，则分行位置p = 40;否则，向左逐个查找，直至找到第一个非英文字母，将其位置作为分行位置p;
Ⅱ.截取s的前p个字符，存入列表;
Ⅲ.将s中未分行部分重新赋值给变量s，转到Ⅰ继续处理。
运行结果如下图

③ 单词查询。输入一段英文文本，输入一个字母key，程序得到包含key的单词。运行结果如下图。

7.4 字符统计

字符串中经常需要统计字母，数字的个数。
实例1 输入一串字符串，统计数字和英文字母和其它字符的个数
思路：枚举字符串，并逐个判断字符串属于数字，英文字母和其他字符，并计数于不同的变量中。如本题中letters表示英文字符个数，digits表示数字字符个数，others表示其它字符。程序代码如下：

实例2 输入一串字符串，统计每个字母个数
思路1：英文字母有26个，统计每个字母的个数，可以定义一个列表。用来存放每个字母的个数。代码见下图思路1。
思路2：定义字典来保存每个字母及个数，字母表示字典的key，个数表示字典的values。代码见下图思路2。

思路1：定义列表保存数量

思路2：定义字典保存数量

练习
① 统计“英文句子单词平均长度”的程序，输入要统计的英文句子，程序输出句子中共有几个单词、单词的平均长度。（单词以字母为开头和结束）。
② 检测密码强度。输入要检测的密码，输出检测结果。将密码字符分为数字，字母和其它符号三类，检测方法：Ⅰ若密码位数少于8位，则不进行强度检测，Ⅱ若密码位数8位以上的，若密码字符属于同1类字符，则密码强度为“弱”；若密码字符属于不同的二类字符，则密码强度为“中等”；若密码字符属于不同的三类字符，则密码强度为“强”。

7.5 字符串加密

凯撒密码是罗马扩张时期朱利斯• 凯撒（Julius Caesar）创造的，用于加密通过信使传递的作战命令。它将字母表中的字母移动一定位置而实现加密。例如如果向右移动 2 位，则字母 A 将变为 C，字母 B 将变为 D，…，字母 X 变成 Z，字母 Y 则变为 A，字母 Z 变为 B。下面讲解具体思路。
思路1 假定原文s = " abcdefghijklmnopqrstuvwxyz"，加密的规则小写字母是向后移动4位，v变z，w变a，x变b，y变c，z变d，其它不变。只要逐一枚举字符串，算出ASCII码并加上4后得到加密后的字符，同时需要判断一下是否超出字母"z"的ASCII码，超出的需要修正。代码如下：

思路2 生成循环序列 本题可以转化为如何生成循环序列”0，1，2，3···25，0，1···”（该序列每个数加上97就变成小写字母的ASCII码）的问题。本序列的大小为26，因此可以通过模26获得序列。按以下步骤执行：
① x % 26 生成 “0，1，2，3···25，0，1···” (x=0,1,2,…)
② (x + 4) % 26 生成”4，5，6···25，0，1···” (x=0,1,2,…)
程序代码如下：

运行结果如下：

凯撒大帝加密解密函数代码如下：
encrypt()加密函数，参数mw为待加密的字符串，pos为向右移动位数；decrypt()解密函数，参数同encrypt函数。

实例1 某加密算法描述如下:
(1)若明文是小写字母，则转换成对应密文字符；
(2)若明文是大写字母，则转换为对应小写字母对应的密文字符；
(3)明文中其余字符不进行转换，按原字符显示。
思路：枚举明文字符串，规则算法描述的步骤逐个加密。分大写字母，小写字母和其它字符分别进行加密。代码如下：

实例2 二进制字符串压缩。输入包含1和0的字符串，程序将对其压缩。压缩方法是：取二进制字符串的首字符为压缩后的第一个符号，接着统计首字符的个数，二者连接后再连接一个分隔符“/”，接着是另一个连接字符的个数，再是分隔符“/”，……以此类推。程序如下。

练习
①【浙2015.10选17】某数据加密方法描述如下：
Ⅰ 以字节为单位进行加密处理；
Ⅱ 将1个字节的8位二进制数分割成前4位与后4位两个二进制数；
Ⅲ 分别将上述两个4位二进制数转换为十进制数；
Ⅳ 将每个十进制数转换为1个加密字符，对应的“密码表”如下：
值(十进制)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
加密字符
I
l
i
k
e
C
H
N
P
0
s
t
c
a
r
d
小明按照上述方法，设计了一个字符串（仅包含ASCII字符）加密的程序。下表显示了字符串中一个字符的加密过程：

运行结果如下图。

② 某字符串(字节数是3的倍数)的加密规则如下：
Ⅰ 将该字符串内码分成3个字节一组，顺次连接后得到24位二进制数
Ⅱ 将得到的24位二进制数按每6位一组分成4组，每组6位
Ⅲ 在每组数字前补上2个0，得到4个字节的二进制数
Ⅳ 将③得到的4个二进制数分别转换为十进制数
Ⅴ 将得到的每1个十进制数转换为1个加密字符，对应的”密码表”按数值由小到大依次为"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"。
③ 某字符串加密算法如下（仅限ASCII码），对明文中每个字符如下处理：
Ⅰ 将该字符串内码转换成2位十六进制数
Ⅱ 将两位十六进制数互换位置，得到的数就是该字符的加密后的字符。

第八讲 “数”问题

8.1 质数

质数又称素数，指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。
1.质数的判断
自然数n，只有1和本身能整除，其它都不能整除，该数就是质数；利用数学知识可以将判断的条件改为[2,int(n ** 0.5) +1]。

2.输出100以内的质数
思路1：枚举100以内的每个数，若是质数，则输出该数。

思路2：埃拉托斯特尼筛法
先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。程序代码如下两种代码：
代码1

代码2

练习
① 输出100以内的孪生素数，（孪生素数是指2个素数相差2）
② 编写程序实现将偶数拆分成两素数之和。

8.2 最大公约数

最大公因数，指几个整数中公有的约数，其中最大的一个，叫做这几个数的最大公约数。例如：12、16的公约数有1、2、4，其中最大的一个是4，4是12与16的最大公约数，一般记为（12，16）=4。12、15、18的最大公约数是3，记为（12，15，18）=3。求最大公约数有多种方法，常见的有质因数分解法、短除法、