资源简介

(共41张PPT)
专题五　解析与枚举
算法及其程序实现
思维导图
归纳提炼
一、模块化思想
在用算法解决问题的过程中,经常采用模块化程序设计思想,将问题分解成若干个子问题,并用相对独立的程序段来针对性地解决各个子问题,提高程序设计的效率。
二、函数的构造及应用
Python中的内建函数能实现许多功能,但在实际程序设计中,并不是所有的功能都有内建函数来直接提供支持,有时候需要根据实际情况自己构造函数以实现常用代码的模块化。
定义函数的语法如下:
def函数名(参数集合):
　　<函数体>
　　[return函数值]
三、模块的导入及应用
在编写程序时,经常需要引用其他模块,这些模块包括Python内置的模块和来自第三方的模块。在使用import语句或from-import语句将函数所在的模块导入后,就能使用其中的函数。
1.math模块
math模块中的常用常数和部分函数如表所示。
math模块中的常用常数与函数
名称 含义
math.sqrt(x) 求x的算术平方根
math.e 自然常数e
math.pi 圆周率π
math.fabs(x) 取x的绝对值
math.trunc(x) 取x的整数部分
math.ceil(x) 对x向上取整,例如x=2.3,返回3
math.floor(x) 对x向下取整,例如x=2.6,返回2
math.pow(x,y) 指数运算,得到x的y次方
math.log(x) 对数运算,默认基底为e
math.sin(x) 正弦函数
math.cos(x) 余弦函数
math.tan(x) 正切函数
math.degrees(x) 弧度转换成角度
math.radians(x) 角度转换成弧度
2.random模块
random模块用来生成随机数,其常用函数如表所示。
random模块中的常用函数
名称 含义
random.random( ) 随机生成一个[0,1)范围内的实数
random.uniform(a,b) 随机生成一个[a,b]范围内的实数
random.randint(a,b) 随机生成一个[a,b]范围内的整数
random.choice(seq) 从序列的元素中随机挑选一个元素
比如random.choice(range(10)),从0到9中随机挑选一个整数
random.sample(seq,k) 从序列中随机挑选k个元素
random.shuffle(seq) 将序列的所有元素随机排序
3.Image模块
Image模块是PIL库(Python Imaging Library)中的重要模块,引用它可以完成对图像的一些常用操作,比如获取图像尺寸和像素颜色、旋转图像或改变图像格式等。
调用PIL库的Image函数:from PIL import Image
常用方法和属性 功能
方法open("文件") 打开图像文件
format属性 图像的文件格式
mode属性 图像的颜色模式
size属性 图像的尺寸大小
方法rotate(角度) 将图像旋转一定的角度
方法show() 显示图像
方法save("文件名") 保存文件
四、解析算法及其程序实现
1.解析算法的基本思想
解析算法的基本思想是指根据问题的前提条件与所求结果之间的关系,找出求解问题的数学表达式,并通过表达式的计算来实现问题的求解。
2.解析算法的解题过程
(1)建立正确的数学模型,即写出正确的数学表达式。
(2)保证计算过程描述的正确性。
(3)使用Python表达式来表示数学表达式。
3.解析算法程序实现的步骤
(1)运用解析算法分析问题,寻找问题中各要素之间的关系,用数学表达式表示它们的关系。
(2)写出解决问题的解析步骤,编写程序实现,通过运行程序求得问题的解。
五、枚举算法及其程序实现
1.枚举算法的基本思想
(1)枚举算法的基本思想是把问题所有可能的解一一列举,然后判断每一个列举出的可能解是否为正确的解。
(2)枚举算法常用于解决是否存在或有多少种可能等类型的问题。
2.使用枚举算法的两个条件
(1)可预先确定每个状态的元素个数,且问题的规模不是特别大。
(2)状态元素a1,a2,…,an的可能值为一个连续的值域。
3.枚举算法的三要素
枚举算法的三要素:枚举范围、枚举对象和判断条件。
4.枚举算法的实现框架
循环结构嵌套分支结构,可表示为:
　　循环结构
　　　　　分支结构
说明:
①枚举范围是用来表示枚举对象存在的一个连续区间,用循环结构实现。
②判断条件用来检测当前枚举的对象是否为问题的解,用分支结构实现。
【归纳与总结】
枚举算法的优点与缺点
枚举算法的优点:
①由于枚举算法一般是现实生活中问题的直译,因此比较直观,易于理解。
②由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明。
枚举算法的缺点:
枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价,因此效率比较低。
典型例题
[例1] 有如下Python程序段:
import math
y=math.pow(3,2**3%5)
程序段执行后,变量y的值为(　 　)
A.3.0 B.27 C.27.0 D.81.0
C
解析:math模块中pow函数的功能是返回xy的值,其结果是实数类型,2**3%5的结果为3,即y=math.pow(3,3),结果为27.0,因此答案为C。
[例2] 有如下Python程序段:
import math
y=math.floor(9.85)
程序段执行后,变量y的值为(　 　)
A.9.8 B.9.9 C.9 D.10
C
解析:math模块中floor函数的功能是向下取整,math.floor(9.85)=9,因此答案为C。
[例3] 有如下Python程序段:
import random
x=random.randint(1,8)
程序段执行后,变量x的值不可能的是(　 　)
A.0 B.1 C.5 D.8
A
解析:random.randint(1,8)的功能是随机生成[1,8]范围内的整数,因此答案
为A。
[例4] 有如下Python程序段:
def isnumber(x):
　 if "9">=x>="0":
　　　flag=True
　 else:
　　　flag=False
　 return flag
ab=""
for i in range(26):
　 ab=ab+chr(97+i)　#小写字母a的ASCII值为97
s1=input("please input string:")
n=0
s2=""
for i in range(len(s1)):
　 if isnumber(s1[i]):
　　 n=n*10+int(s1[i])
　 else:
　　　s2+=ab[n]
　　　n=0
print(s2)
程序执行时,输入"0aba28a6",输出的结果为　　　　　。
aaac
解析:自定义函数isnumber(x)的功能是判断字符x是否为数字字符,若是则返回True,否则返回False。本题的功能是根据字符串的数字从小写字母表中取出对应的字母,若不是数字,则取出字母“a”,需注意的是,若字符串以数字字符结尾,则不会取出最后数字所对应的字母,因此答案为aaac。
[例5] 编写程序,实现如下功能:用篱笆靠墙围成一块长方形菜地,菜地的长和宽都是整数。输入篱笆总长度(整数),输出该篱笆围成的菜地最大面积。
实现上述功能的程序如下,请在划线处填入合适的代码。
n=int(input("请输入篱笆长度:"))
maxs=0
for i in range(1,(n-1)∥2+1):
　　　①　　
s=i*w
if s>maxs:
　　　②　　
print("菜地最大面积:",maxs)
程序划线①处应填入的代码为:　　　　　　;
程序划线②处应填入的代码为:　　　　　　。
w=n-2*i
maxs=s
解析:本题主要考查的是枚举算法。i为长方形长度,则宽度为w=n-2*i,面积为s,因此①处代码为w=n-2*i;最大面积保存在变量maxs中,因此②处代码为maxs=s。
[例6] 编写程序,实现如下功能:某任务系统中,奖励以金币形式发放。第一
天,参与者获得一枚金币;之后两天(第二天和第三天),每天获得两枚金币;之后三天(第四、五、六天),每天获得三枚金币;之后四天(第七、八、九、十天),每天获得四枚金币……这种奖励发放模式会一直这样延续下去:当连续N天每天获得N枚金币后,参与者会在之后的连续N+1天里,每天获得N+1枚金币。请计算在前K天里,参与者一共获得了多少枚金币。
此题的算法思想为:金币数为1时发1天,金币数为2时发2天,…,当发金币的天数和当前发的金币数相等时,则下一天发的金币数将增加一个,并重新计算发放天数。
(1)实现上述功能的程序如下,请在划线处填入合适的代码。
k=int(input("请输入发金币的天数:"))
money=0　　　 #money表示总金币数
salary=1 #salary表示每天发的金币
time=0 #time表示以n枚金币数发的天数
for i in　　①　　:
money+=salary
time+=1
if　　②　　:
　　salary+=1
　　time=0
print("金币总计:",money)
程序划线①处应填入的代码为:　 　　　　　　　　　　;
程序划线②处应填入的代码为:　　　　　　　　　　　。
range(k) 或range(1,k+1)或其他等价答案
time==salary
解析:本题主要考查的是简单算法的处理。(1)划线①处循环表示共发放金币的天数,只要循环k次即可,因此可填range(k)或range(1,k+1);划线②处if条件为当前金币已发放time天,因此下一天的发放金币数为当天发放金币数加1,发放天数time重置0,故②处代码为time==salary。
(2)程序运行时,输入10,则程序运行的结果为:　　　　。
30
解析: (2)发金币的天数为10天时,金币总数=1+2×2+3×3+4×4=30,故答案为30。
[例7] 利用更相减损术求两个正整数的最大公因数。更相减损术的算法思想是:先用较大的数减去较小的数,然后把所得的差与较小的数比较,如果相等,则较小数为它们的最大公因数,若不相等,再用较大数减去较小数,继续上面的操作,直到差和较小数相等为止。例如,求24和16的最大公因数可表示为:
(24,16)→(16,8)→(8,8),此时两数的差与较小数相等(均为8),因此24和16的最大公因数为8。
实现上述功能的Python程序如下,请在程序划线处填入合适的代码。
def gcd(a,b):
　 while　　　　①　　　　:
　 　　if a>b:
　　　　a=a-b
　　　 else:
　　　　　b=b-a
　 　　　　　　　②　　　　
number1=int(input('请输入第一个数:'))
number2=int(input('请输入第二个数:'))
if number1　 number1,number2=number2,number1
　 　　　　　③　　　　　
print(number1,',',number2,'的最大公因数为:',ans)
程序划线①处应填入的代码为:　　　　　　;
程序划线②处应填入的代码为:　　　　　　　　　　　;
程序划线③处应填入的代码为:　　　　　　　　　　　　　　　。
a!=b　
return a或return b
ans=gcd(number1,number2)
解析:自定义函数gcd(a,b)的功能是求整数a、b的最大公因数,当a、b不相等时,重新构造一对新的数,直到这两个数相等为止,因此①处的条件为a!=b,当a=b时while循环结束,即求得最大公因数为a(或b),最后将最大公因数返回至函数调用处,因此②处代码为return a或return b;根据print语句可知,两数的最大公因数为ans,③处代码为调用自定义函数gcd,参数分别为number1和number2,因此代码为ans=gcd(number1,number2)。
[例8] 如果一个大于1的整数只能被1和它本身整除,这个数称为素数。如果一个数从左到右和从右到左读都是一样的,称这个数为回文数,例如121是一个回文数。既是素数又是回文数的数称为回文素数。下列程序的功能输出所有的三位数回文素数,并统计三位数回文素数个数。程序运行效果如下图所示。
实现上述功能的程序如下,请回答下列问题。
def prime(x):
　 for k in range(2,int(x**0.5)+1):
　　　if　　　①　　　:
　　　　　return False
　 return True
def judgehw(m):
　 n=m
　 p=0
　 while n!=0:
　　　②　　
n=n∥10
　 if p==m:　#④
return True
　 else:
return False
count=0
for i in range(100,1000):
if　　　③　　　:
　　　　print(i)
　　　　count+=1
print("三位数回文素数共有:",count,"个")
(1)程序划线①处应填入的代码为:　　　　　　　　;
程序划线②处应填入的代码为:　　　　　　　　 ;
程序划线③处应填入的代码为:
　　 　　 　　　　。
x%k==0
p=p*10+n%10
prime(i) and judgehw(i)或
prime(i)==True and judgehw(i)==True
解析:本题主要考查的是枚举算法。(1)自定义函数prime(x)的功能是判断整数x是否为素数,若是则返回True,否则返回False,划线 ①处条件为合数时的情况,因此①处语句为x%k==0;自定义函数judgehw(m)的功能是判断整数m是否为回文数,划线②处所在循环的功能是将整数n进行倒置,因此②处代码为p=p*10+n%10;划线③处条件表示当前整数i为回文素数时的情况,因此③处代码为prime(i) and judgehw(i),也可以表示为prime(i)==True and judgehw(i)==True。
(2)若将④处的语句修改为“if p==n:”,请预测一下输出的三位数回文素数共有　　　　个(填数字)。
0
解析:(2)程序执行后,变量n的值为0,因此if p==n:不可能满足,则输出的三位数回文素数为0个。
感谢观看

展开更多......

收起↑