第5章 Python程序设计基础与算法

1、 第5章 Python程序设计基础与算法5.1 程序设计概述5.1.1 程序设计基本概念与方法1程序设计与程序设计语言2程序设计的基本方法 进行程序设计之前，首先要确定解决问题的三个要素，即数据、处理、结果。（1）数据：即程序要处理的数据是什么，有哪些，它们是什么类型的（比如整数、实数或者文字符号等），它们内部有什么逻辑关系等。数据是程序设计最主要的考虑对象，是程序处理的基础。（2）处理：是指程序的主要逻辑，解决问题的主要步骤。它是对数据进行的处理策略和处理过程。（3）结果：是指程序的执行目的，程序运行最终产生的影响。一个程序一定会有执行结果，不产生结果的程序设计是没有意义的。编程解决问题的具

2、体步骤：（1）分析问题：即对要解决的问题进行认真分析和研判，确定数据、处理和结果三要素。（2）设计算法：即设计出求解问题的方法和具体步骤。（3）编写程序：将算法翻译成计算机程序设计语言，将解决问题的思路变为计算机可执行的形式。（4）运行程序：对程序进行调试、测试，确保程序能够按照正确的语法规则和逻辑运行，输出正确结果。5.1.1 程序设计基本概念与方法5.1.2 Python语言简介Python语言是一种面向对象的解释型开源语言，其特点如下：（1）面向对象。（2）可扩展性。（3）可移植性。（4）免费和开源。（5）丰富的库。（6）可嵌入性。5.1.3 Python的开发环境Python开发环境的

3、搭建步骤如下:（1）Python的下载。（2）设定安装选项。（3）安装Python 3.8.3。（4）安装成功。5.2 数据类型、运算符与函数5.2.1 常用内置数据类型1数值数据类型Python包括四种内置的数值数据类型。2序列数据类型不可变序列数据类型有三种。（1）字符串（str）：表示Unicode字符序列。（2）元组（tuple）：表示任意类型数据的序列。（3）字节（bytes）：表示字节（8位）序列数据。可变序列数据类型有两种。（1）列表（list）：表示可修改的任意类型数据的序列。（2）字节数组（byte sarray）：表示可以修改的字节（8位）数组。3集合与字典数据类型（1）集

4、合（set）：属于可变对象。（2）字典（dict）：属于可变对象。4 其它数据类型5.2.1 常用内置数据类型5.2.2 运算符与表达式1. 算术运算符2赋值运算符3比较运算符4位运算符5逻辑运算符6运算符优先级5.2.3 函数1函数调用表达式2Python内置函数3Python自定义函数4模块5.3 序列数据类型5.3.1 元组1元组的基本操作（1）元组的创建。（2）访问元组。（3）修改元组。（4）删除元组。（5）元组运算符。（6）元组索引、截取。2元组的内置函数5.3.2 列表1列表的基本操作（1）定义一个列表。 （2）改变列表第4个元素的内容。2删除列表元素（1）定义长度为4的姓名列表。

5、（2）删除第3个元素。 （3）最后列表长度由4变为3。3分片赋值（1）定义一个list。 （2）改变list中的最后两个值。 （3）分片替换。（4）分片赋值还可以在不需要更改原有列表任何内容的情况下进行新元素插入。（5）在第一个元素后插入新的元素。（6）给第一个和第三个元素之间分片赋值一个空序列，即删除元素。（7）负数分片操作。4列表函数（1）list函数。 （2）len函数。 （3）max函数。5.3.3 字符串字符串是一个由字符组成的序列。字符串常量用单引号（）或双引号（“）括起来。5.4 字典与集合数据类型5.4.1 字典1字典的基本操作（1）定义一个字典。（2）字典元素的访问。2字典元

6、素的修改、添加与删除（1）当给指定“键”为索引的字典元素赋值时，假设该“键”存在，则修改该“键”对应的值；如果“键”不存在，则添加新的元素。（2）可使用del删除指定键对应的元素；可使用字典对象的clear()方法清空字典；del也可以删除字典。5.4.2 集合集合的基本操作：（1）创建集合。（2）添加元素。（3）合并集合。（4）移除元素。（5）判断元素是否在集合中存在。（6）计算集合元素个数。5.5 程序的基本结构5.5.1 Python的输入输出1input()函数2print()函数5.5.2 顺序结构5.5.3 选择结构1双（单）分支结构2多分支结构1while循环（1）while基本

7、结构。 （2）while-else循环语句。2for循环（1）for循环语句。 （2）for-else循环语句。3break语句4continue语句5.5.4 循环结构5.6 类和对象5.6.1 使用已有的类5.6.2 定义新的类5.7 基础算法设计思想5.7.1 枚举法枚举法，也称穷举法，是把问题所有可能的解一一尝试，从而找出问题的解。这就要求问题的可能解是有限的、容易枚举的、不会产生组合爆炸的。枚举法的基本思想是根据题目的部分条件确定解的大致范围，对此范围内所有可能的解一一验证。若某个情况经过验证符合题目的全部条件，则为本题的一个解。若所有可能的解经过验证后都不符合题目的全部条件，则本题

8、无解。使用枚举算法解题的基本思路如下： 确定枚举对象、枚举范围和判定条件。 逐一列举可能的解，验证每个解是否是问题的解。使用枚举算法要注意以下几点： 题解的可能范围，不能漏掉任何一个正确的解，也要避免重复。 判断是否是正确解的方法。 使可能解的范围降至最小，提高解决问题的效率。5.7.2 递推法 所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。利用递推法解决问题，需要做好以下四个方面的工作： 确定递推变量。应用递推法解决问题，要根据问题的具体情况设置递推变量。 建立递推关系。递推关系

9、是指如何从变量的前一些值推出其下一个值，或从变量的后一些值推出其上一个值的公式（或关系）。有的问题递推关系明确，大多数问题没有明确的递推关系，需通过对问题的分析和推理确定递推关系。 确定初始（边界）条件。对所确定的递推变量，要根据问题最简单情形的数据确定递推变量的初始（边界）值，这是递推的基础。 对递推过程进行控制。递推过程不能无休止地重复执行下去。递推过程在什么时候结束，满足什么条件结束，这是编写递推算法必须考虑的问题。5.7.3 递归法递归法是一种直接或者间接地调用自身的算法，递归法的具体实现过程一般通过函数（或子过程）来完成，在函数（或子过程）的内部，编写代码直接或者间接地调用函数（或子

10、过程）自己，即可完成递归操作。递归法的思想是把求解问题转化为规模缩小了的同类问题的子问题，然后递归调用函数（或子过程）来表示问题的解，通过多次递归调用，最终可求出最小问题的解，然后通过这个最小问题的解返回上层调用，再求出次小问题的解，再返回上层调用，不断重复，最终得到整个问题的解，完成递归操作在使用递归算法时，应该注意如下几点： 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 递归法虽然显得很简洁，但是运行效率较低，所以一般不提倡用递归法设计程序。 在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出。5.7.4 分治法 分治法是把复杂问题

11、简单化，将一个复杂的问题拆分为几个相对简单的子问题，如果子问题依然无法解决，再 次分割。直到能够解答问题为止。这听起来好像和递归法差不多，两者的差异在于分治法使用的子过程可以为多 个，而递归法只能是1个。在子问题一致时，两者几乎一致。而分治法产生的子问题，一定程度上和父问题相似，比较适合配合递归方法使用。分治法的思想是先把整个问题分解成几个较小的子问题，求出这几个子问题的解后，再把它们组合成整个问题的解。如果这些子问题还是比较大，可以继续再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。使用分治法解题的步骤如下： 分解，将要解决的问题拆分成若干个规模较小的同类问题。 求解，当子问

12、题划分得足够小时，用较简单的方法解决。 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。5.7.5 贪心法贪心法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望达到结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行推销员每次都选择最近的城市，那就是一种贪心法。贪婪法是不考虑整体的情况下，只针对局部问题最优解的算法，其优势是能够节省时间。由贪心法的思想可看出，贪心法存在以下3个问题： 不能保证最后的解是最优的。 不能用来求最大或最小解问题。 只能求满足某些约束条件的可行解的范围。使用贪心法解题的步骤如下： 建立数学模型来描述问题； 把求解的问题分成若干个子问题； 对每一个子问题求解，得到子问题的局部最优解； 把子问题的局部最优解合成原来问题的一个解。5.7.6 回溯法 回溯法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。许多复杂的，规模较大的问题都可以使用回溯法。 回溯法的思想是枚举所有的解，找到满足期望的解。为了有规