第2～3章 算法与问题解决 算法的程序实现-浙江高中信息技术知识点

9 第二章 算法与问题解决 1. 算法可以帮助算法执行者高效地解决问题。 2. 算法指的是解决问题或完成任务的一系列步骤。 3. 根据算法的定义，算法具有下列特征：有穷性、可行性、确定性、0个或多个 输入、一个或多个输出。 4. 算法三要素 数据、运算及控制转移 5. 常见的算法描述方式有自然语言、流程图、伪代码、计算机程序设计语言等。 6. 流程图用一些图形符号表示规定的操作， 并用带箭头的流程线连接这些图形 符号， 表示操作进行方向。 流程图描述算法结构清晰、 寓意明确。 常用的流 程图基本图形及其功能 如图 2.1 所示。 图 2.1 7. 计算机程序设计语言经历了“机器语言一汇编语言一高级语言”的发展历程。 8. 常见的高级语言有 Basic、 C、C+＋、Java、Python、Ruby 等。 9. 算法的控制结构有三种，即顺序结构、分支结构和循环结构。 10. 顺序结构指的是算法中各个步骤按照先后顺序依次执行的结构。 11. 先进行条件判断，再根据判断结果分别执行不同处理的控制结构就称为分支 结构（也称选择结构） 12. 算法执行过程中， 在条件控制下， 某些操作步骤需要重复执行（循环） 的 控制结构称为循环结构。 13. 循环结构的重复执行（循环）并不是没有限制，没有限制就变成死循环了。 14. 用计算机解决问题时，由于实际问题情境的复杂性，需要先对实际问题进行 抽象与建模，再根据建立的计算模型设计算法，并将算法用合适的方式加以准确 描述。 15. 用计算机编程解决问题的一般过程：抽象与建模、设计算法、编写程序、调 试运行程序 10 第三章 算法的程序实现 1. Python 是一种面向对象、 解释型的计算机程序设计高级语言，其语法简洁清 晰，方便对数据进行组织和处理 2. 使用 Python 语言编程解决问题时，需要严格遵守 Python 语言的语法规则， 并选择合理的程序运行环境运行程序。 3. 用于编写 Python 程序的 IDE 较多，如 IDLE、 Spyder、 Wing、 PyCharm 等。 4. 数据按照其本身特征可以分为若干种不同的类型， 常见的 Python 基本数据 类型如图 3.1 所示 图 3.1 5. Python 的基本运算包括算术运算（图 3.2）、关系运算（图 3.3）和逻辑运算 （图 3.4）三大类。 6. Python 中的算术运算存在着优先级顺序， 优先程度最高级别为 1，级别数字 越大， 优先级越低。在同一个表达式中， 如果有一个及以上的运算符， 那么 先执行优先级高的运算， 同优先级的基本运算按照自左向右的顺序执行 图 3.2 11 7. 关系运算符中 in" 运算符用来检查一个值是否包含在指定的序列中，例如 “a” in “aaa”为 True,”b” in “aaa”为 false。注意 in 运算符要求 符 号左右两边都是字符型。例如 3 in 333 左右两边都是数值型，就会报错 图 3.3（关系运算符） 8. 逻辑运算符经常用于描述复杂情况的判断。 图 3.4（逻辑运算符） 9. 程序设计时， 有些数据是未知或可变的， 为了更灵活地使用这些数据， 可 以使用变量来存储。为了能对变量进行访问， 需要对变量进行命名。 Python 变量命名要求：1.不能是数字开头、2.不能是系统关键字、3.不能重复、 4.不能有特殊字符(下划线_除外)。Python 变量命名规范：在正常开发中，我们 对变量命名一般有两种方法，一种是匈牙利命名法（将单词中的元音字母去除） 例如 count 简写成 cnt，另一种是驼峰规则（首字母大写）例如用户数量 UserCount 在实际解题中，部分题目也会使用拼音首字母（例如用户数量：yhsl） 或者拼音首字母+匈牙利命名法实现(例如用户数量:yhcnt)常见变量名详见下表： 变量名 作用 c、cnt、count 统计个数 cur 当前 f、flag 标识 i,j 循环变量 n、num 数量 p 位置（当前） pre 上一个 q 位置（上一个） r、res 结果 s、str 字符串 t、temp 临时变量 12 10. 字符串（String）和列表(List)：字符串、 列表中的元素都是通过索引来 定位的。如图 3.5 所示， 第一个元素的索引 是 0, 第二个元素的索引是 1, 以 此类推不断递增（图 3.5）。 图 3.5 11. 字符串或列表中的元素可以通过索引进行访问，如图 3.6 所示： 图 3.6 12. 字典和列表类似， 可包含多个元素。字典中的每个元素包含两部分内容： 键和值。键通常用字符串或数值来表示， 值可以是任意类型的数据。键和值两 者一一对应， 且每个键只能对应一个值。 13. 键和值在字典中以成对的形式出现， 并以如下方式标记： d={keyl :valuel,key2:value2,…｝。键－值对用冒号分隔， 各个对之间用逗 号分隔， 所有这些都包括在花括号 “ {｝" 中。 字典中的元素是没有顺序的， 引用元素时以键为索引。 14. 注释：注释就是对代码的解释和说明，其目的是让人们能够更加轻松地了解 代码。注释是编写程序时，写程序的人给一个语句、程序段、函数等的解释或提 示，能提高程序代码的可读性。注释只是为了提高可读性，不会被计算机编译。 Python 中注释标识符为 #，例图 3.7 图 3.7 15. 常见内置函数见下表(下表中 s:字符串,f:实数,i:整数,[]:数组) 函数名 样例 备注 函数名 样例 备注 Int(s) Int(“3”) 将 String 型整数 转为 Int 型 Len([]) Len(“12”) 字符串数组的长度 Int(f) Int(3.9) 取整 Round(f,1) Round(2.15,1) 四舍五入保留 n位 Float(s) Float(“3.9”） 将 String 型实数 转为 Float 型 Max([]) Max([1,2,3]) 求数组中的最大值 Float(i) Float(3） 将 int 型实数转 为 Float 型 Min([]) Min([1,2,3]) 求数组中的最小值 Str(f) Str(3.9) 将 Float 型实数 转为 String 型 Sort([]) Sort([1,2,3]) 对数组进行排序 Str(i) Str（3） 将 Int 型整数转 为 String 型 Abs(i) Abs(-1) 取绝对值 Ord(s) Ord(“A”) 字符转为 ASC 码 Print() Print(“A”) 输出函数， Chr(i) Chr(65) ASC 码转为字符 Input() Intpu() 输入函数,返回字符 串 13 16. 数据结构-字典的内置函数(表 3.1) 假设有一个字典型变量 dic={"书名":"满分计划","作者":"陶小波"} 方法名 示例 说明 clear dic.clear 清空字典变量 get dic.get(“书名”) 根据 key 得到值 update dic.update({“页数”:” 100”}) 往字典内添加一项 / dic[“书名”] 根据 key 得到值 / dic[“书名”]=”必考满 分” 如果字典中有该 Key，则 会更新对应的 Value 值， 即 dic={"书名":"必考满 分","作者":"陶小波"} / dic[“版本”]=1 如果字典中有没有该 Key，则会增加对应的键 值对， 即 dic={"书名":"必考满 分","作者":"陶小波", “版本”:1} pop dic.pop(“书名”) 传入键删除。 表 3.1 17. 数据结构-列表的内置函数(表 3.2) 假设有一个列表型变量 ls=["满分计划",1234567,true] 方法名 示例 说明 结果 append ls.append(“陶”) 向列表中追加一项 ls=["满分计划 ",1234567,true,” 陶”] count ls.count(“满分计 划”) 统计列表中某项的 数量 1 index ls.index(‘满分计 划’) 指定内容在列表 中的位置 0 pop ls.pop(1) 删除指定项 ls=["满分计划 ",true,”陶”] sort ls.sort() 排序，默认升序 insert ls.insert(1,"张") 插入到指定位置 ['满分计划', '张 ', 1234567, True] 表 3.2 14 18. 数据类型-字符串的内置函数 假设有字符串 s=”this is ningbo is zhenhai” 方法名 示例 说明 结果 split s.split(“ ”) 根据指定符号分 割，如不传入参 数，即 s.split() 等价于 s.split(“”) ['this', 'is', 'ningbo', 'is', 'zhenhai'] upper s.upper() 将所有字母转换 为大写 THIS IS NINGBO IS ZHENHAI lower s.lower() 将所有字母转换 为小写 this is ningbo is zhenhai count s.count(“is”) 获取指定字符在 字符串中出现的 次数 3 strip s.strip() 去掉字符串中最 后的 (回车) this is ningbo is zhenhai 19. 分支结构： If 语句 常见有 4种结构。详见下表 if 条件： if x==1: 执行代码 print(“1”) 说明：只有一个分支的情况,条件满足执 行代码 if 条件： if x==1: 代码 1 print(“1”) else: else: 代码 2 print(“2”) 说明：有两个分支的情况,条件满足执行 代码 1 条件不满足执行代码 2 if 条件 1： if x==1: 代码 1 print(“1”) elif 条件 2: elif x==2: 代码 2 print(“2”) 说明：有两个分支的情况,条件 1满足执 行代码 1条件 2满足执行代码 2 if 条件 1： if x==1: 代码 1 print(“1”) elif 条件 2: elifx==2: 代码 2 print(“2”) else: else: 代码 3 print(“3”) 说明：有两个分支的情况,条件 1满足执 行代码 1条件 2满足执行代码 2，两个都 不满足执行代码 3 15 20. 循环结构 1. for 循环 格式： for 变量名 in range(初始值,终止值,步长): 其中循环范围为[初始值,终止值)。当步长为 1的时候可以不写 例如求 10! x=1 For i in range(2,11): x=x*i 2. for循 环(遍 历) 格式: for 变 量名 in 变量: 其中变 量需要 是数组、 字符串 等 例如： x=”123” For i in x: Print(i ) 结果： 1 2 3 3. while 循环 格式 while 循环条件： 条件满足进入循环，条件不满足退出循环 例如求 10! x=1 cnt=1 While cnt!=10: x=x*cnt cnt=cnt+1 16 21. 其他循环结构 其他写法（for）： for i in range(10): print("a") 没有 break，for 循环结束后 else: 会执行 else 之后的代码 print("b") 即 print(“b”) -------------------------------------------------------------------- for i in range(10): print("a") 有 break，for 循环结束后 break 不会执行 else 之后的代码 else: print("b") 22. 切片【可以对数组、字符串、pandas 对象等操作】【切片取值范围左闭右开】 假设有字符串 s=”满分计划是由陶小波编写的”。 代码 结果 说明 s[0] “满” 取字符串/列表的第一 个 s[0:2] “满分” 从字符串第0个取到第1 个(注意:[0,2],左边是 闭区间，右边是开区间) s[0:] “满分计划是由陶小波编写的” 取字符串/列表的所有 值 s[0::] “满分计划是由陶小波编写的” 取字符串/列表的所有 值 s[::1] “满分计划是由陶小波编写的” 取字符串/列表的所有 值 s[::-1] “的写编波小陶由是划计分满” 取反字符串 s[::2] “满计是陶波写” 间隔两位取值 表 3.3 23. 部分特殊代码列表 代码 等价代码 说明 a=b=0 a=0 b=0 定义变量 a,b=0,1 a=0 b=1 定义变量 a,b=b,a a=a+b b=a-b a=a-b a,b 两变量值交换 17 ls=input().split(",") k=[int(i) for i in ls] / 将字符串型的列表转换为数 值型，并赋值给 k Print("%.2f" % 123.45678) / 浮点数四舍五入输出，2f 表 示保留两位小数 Print("%.2d" % 1) / 按格式输出，2d 表示两位， 位数不足，值前面补 0 Print(num,end=" ") end=" ",表示将 print()函数 的结束值设置为一个空格，这 样下一次对print()的调用结 果将会从空格右边开始。（即 不换行） Python 自定义函数 1)函数代码块以 def 关键词开头，后接函数标识符名称和圆括号()。 2)任何传入参数和自变量必须放在圆括号中间。圆括号之间可以用于定义参数。 3)函数的第一行语句可以选择性地使用文档字符串—用于存放函数说明。 4)函数内容以冒号起始，并且缩进。 5) return [表达式] 结束函数，选择性地返回一个值给调用方。不带表达式的 r eturn 相当于返回 None 样例如下表所示 def 方法名(参数列表): return 结果 自定义函数格式 def pra(x): If x %2==0: return True else: return False 自定义函数样例 24. Python 第三方库导入方法。 导入方法 1 Import 库名 导入整个库 导入方法 2 Import 库名 as 别名 导入整个库，并定义别名 导入方法 3 From 库名 import 方法 名 导入库中的某些方法 18 25. 常见 Python 第三方库 库名 备注 Random 随机数 Math 数学包 Pandas 数据分析 Matplotlib 绘图工具 26. Python 文件读写。其中 open 函数需要传入两个参数，第一个是文件路径， 第二个是方法 其中 r:表示读入，w:表示覆盖写入，a+:表示追加写入。 假设有 1.txt 文件 #一次性输出所有值 f=open("1.txt","r") print(f.read())#f.read():#读取全部 f.close()#关闭文件流 #覆盖写入值 f=open("1.txt","w") f.write("11111") #f.write()#写入一行 f.close()#关闭文件流 #循环输出每一行 f=open("1.txt","r") For line in f.readlines(): Print(line.strip()) #循环输出每一行，并去掉末尾 f.close()#关闭文件流 #追加值 f=open("1.txt","a+") f.write("11111") #f.write()#追加一行 f.close()#关闭文件流 27. 随机数(Random)方法（下表中的 Ls 为：Ls=[1,2,3,4]) 方法名 说明 使用样例 randint 生成指定区间内的随机 数整数 random.randint(1,10) 即 生 成 [1,10]之间的随机整数 random 生成[0,1)区间内的随 机实数 random.random()即生成[0,1)之 间的随机实数 uniform 生成指定区间内的随机 数实数 random.uniform(1,10) 即 生 成 [1,10]之间的随机实数 choice 从数组中随机抽取一个 元素,返回的类型非数 组 random.choice(Ls)随机获取一个 变量，结果例：1 sample 从数组中随机抽取多个 元素返回的类型为数组 random.sample(Ls,2)随机获取 2 个变量，结果例：[1,2] shuffle 将数组中的数据打散 random.shuffle（Ls)结果 [4,2,1,3] 19 28.使用 Python 读取图片并根据图片黑色部分判定试卷分数。 #代码注释： from PIL import Image #引入 Image im = Image.open("RGB.bmp") #打开文件名为 RGB.bmp 的文件 pix = im.load() #加载（转为比特流） width = im.size[0] # size 中有两个参数，第 1个参数为图像宽度值 height = im.size[1] # size 中有两个参数， 第 2 个参数为图像高度值 count = 0 for x in range(width): for y in range(height): R,G,B = pix[x, y] # 根据像素坐标获得该点的 RGB 值 if bw_judge(R,G,B) == "黑色": # bw_judge 函数用于判断黑、白像素 count = count + 1 if count >= width * height * 0.64: print("已填涂！") else: print("未填涂！") 29.使用 Python 读取图片修改后，再导出成图片 from PIL import Image import numpy as np import matplotlib.pyplot as plt img=np.array(Image.open('lena.jpg').convert('L')) #读入文件并转制 rows,cols=img.shape #图像尺寸分别赋值 for i in range(rows): #依次取每个像素的坐标 for j in range(cols): if (img[i,j]>128): #像素值大于特定值 128，赋值 1否则为 0 img[i,j]=1 else: img[i,j]=0 plt.figure("lena") #指定当前绘图对象 plt.imshow(img,cmap='gray') #显示灰度图像 plt.axis('off') #关闭图像坐标 plt.show() #弹出包含了图片的窗口