目录

字典

常用函数

pop() 方法

del 方法

clear()方法

用字典推导式的方法创建字典：

字典的遍历

列表嵌套字典

迭代算法

谷角猜想

阿米巴简单分裂

求平方根

牛顿迭代

二分法

enumerate(iterable, start=0)

二分函数查找数字

例题一：编写函数，函数功能是在已排序的重复数据列表A中，查找比指定的元素x小的最大的数，给出该数在列表中最后一次出现的下标，找不到输出-1。

二分查找方程的根

例题一：函数f(x)=x**2−10*x+3在区间[8,12]单调上升且与x轴相交，求解该近似解，要求精度0.0001，即|f(x)|<=0.0001。

例题二：函数f(x)=x2−10x+3在区间[-2, 2]单调下降且与x轴相交，求解该近似解，要求精度0.0001 (|f(x)|<=0.0001)。

例题三：函数f(x)=x2−10x+3在区间[-2, 12]与x轴有两个交点，求解这两个近似解，要求精度0.0001，即|f(x)|<=0.0001。

二分法查找和或平方和

例题一：编写一个程序，用来在一个数字列表中搜索2个数a和b，使得a2+b2=x，其中x为一个给定的数。

例题二：二分求和扩展：在列表A中搜索元素b，使得a的各位数之和加上b的各位数之和==x（如12与34的每一位数字之和为10）

求和问题

给定4组数（元素总数n相同，n<=100 ），在每组数中找一个数，使得4个数之和为0，求共有多少组数符合条件（不同的索引号算不同的结果）。例如：[-45, -41, -36, -36, 26, -32] [22, -27, 53, 30, -38, -54] [42, 56, -37, -75, -10, -6] [-16, 30, 77, -46, 62, 45] 结果为：5

递归

例题一：从键盘输入两个整数n，m，求出n与m的最大公约数 样例输入

例题二：递归求阶乘

例题三：输入一个字符串，判断该字符串是不是回文字符串，如果是返回“Yes”，不是返回“No”

例题四：从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。

从键盘输入整数n，m，计算从n个不同元素中取出m个元素的组合数。

例题五：从键盘输入一个列表，元素为整数，调用递归函数sumLIst(L)，求出列表L中所有元素的和，返回和，在主函数中输出。

matplotlib

实训

导入文件

用pandas载入excel文件

用numpy载入csv文件/文本文件

对载入的数据进行可视化

实训编程要求

期末模拟题

编程题

1.递归法解题（状态转移方程）.【题目描述】

2.Numpy的应用（求定积分）

3.二分法查找数字

4.反推的一个循环

5.列表的应用

6 .Numpy应用

7.Numpy的切片和统计函数的应用

8.

9.循环输出

10.二分法求根

11.数组的操作

选择题

---

常用函数

键值对

通过 value 来获取 key 值，在 Python 中并没有提供直接的方法，我们可以通过自定义函数来实现，如下：

pop() 方法

删除指定给定键所对应的值，返回这个值并从字典中把它移除。

del 方法

clear()方法

clear()方法是用来清除字典中的所有数据，因为是原地操作，所以返回 （也可以理解为没有返回值）

用字典推导式的方法创建字典：

结果如下：

通过两个list创建字典：

字典的遍历

例题

给定一个字符串s,统计0-9每个数字在字符串s中出现的次数存储在字典count，并输出字典

列表嵌套字典

字典和列表可以相互嵌套。本关中我们通过列表嵌套字典来存储若干个同学的成绩，如下例所示。

[{'name':'张小明','score':95}, {'name':'李小红','score':85},{'name':'王小刚','score':75}]

列表的每一个元素都是字典类型，存储一位学生的姓名与成绩，本关任务是按指定姓名查找成绩，并统计平均、最高、最低成绩，输出上述信息。

谷角猜想

日本数学家谷角静夫在研究自然数时发现了一个奇怪现象：对于任意一个自然数 n ，若 n 为偶数，则将其除以 2 ；若 n 为奇数，则将其乘以 3 ，然后再加 1。如此经过有限次运算后，总可以得到自然数 1。人们把谷角静夫的这一发现叫做“谷角猜想”。

编写一个程序，由键盘输入一个自然数 n ，把 n 经过有限次运算后，最终变成自然数 1 的全过程保存在列表中并打印出来。

样例1输入20输出[20, 10, 5, 16, 8, 4, 2, 1]

阿米巴简单分裂

它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内， 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 2n(n从键盘输入)个。试问，开始的时候往容器内放了多少个阿米巴？考虑特例，当容器容量较小时，开始1个阿米巴也不需要45分钟就可以充满，答案为1。请编程序算出开始时容器里面的阿米巴个数。

样例1输入20输出32

求平方根

求平方根的迭代公式：x1=1/2*(x0+a/x0）。

算法：

1. 先自定一个初值x0，作为a的平方根值，在我们的程序中取a/2作为x0的初值；利用迭代公式求出一个x1。此值与真正的a的平方根值相比，误差很大。
2. 把新求得的x1代入x0中，准备用此新的x0再去求出一个新的x1.
3. 利用迭代公式再求出一个新的x1的值，也就是用新的x0又求出一个新的平方根值x1，此值将更趋近于真正的平方根值。
4. 比较前后两次求得的平方根值x0和x1，如果它们的差值小于我们指定的值，即达到我们要求的精度，则认为x1就是a的平方根值，去执行步骤5；否则执行步骤2，即循环进行迭代。
5. 输出方程的根x1。

牛顿迭代

牛顿迭代公式：假设r是方程f(x)=0的根，选取x0作为r的近似初值，过点(x0,f(x0))作切线L：y=f(x0)+f’(x0)(x-x0)，则L与x轴的交点

x1=x0-f(x0)/f’(x0)称为r的一次近似值。过点(x1,f(x1))做切线与x轴的交点x2=x1-f(x1)/f’(x1) 称为r的二次近似值。重复该过程，得到第n+1交点

xn+1=xn-f(xn)/f’(xn) 称为r的n+1次近似值，这就是牛顿迭代公式。

已经证明，如果是连续的，并且待求的零点是孤立的，那么在零点周围存在一个区域，只要初始值位于这个邻近区域内，那么牛顿法必定收敛。 并且，如果不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

使用牛顿迭代法求解给定方程x3-10*x2-25*x+250在输入x0附近的解，精度要求前后两次迭代的差值小于10的负六次方。样例1输入3输出x=5.000000

直接从头到尾进行搜索的算法是非常消耗时间的，时间复杂度为O(n)

线性序列查找数字（有序）其时间复杂度是O(logn)

参数：

• iterable:可迭代对象
• start：计数器启动的索引值，默认为 0

返回：索引和元素对

二分函数查找数字

如果A不是有序数列

例题一：编写函数，函数功能是在已排序的重复数据列表A中，查找比指定的元素x小的最大的数，给出该数在列表中最后一次出现的下标，找不到输出-1。

思路：先用二分法查找x，用另一个变量标记x的索引，再通过while循环

改：编写函数，函数功能是查找已排序的重复数据列表A中的指定元素x，找到给出该数在列表中第一次出现的下标，找不到输出-1。

改：函数功能是查找已排序的重复数据列表A中的指定元素x，找到给出该数在列表中最后一次出现的下标，找不到输出-1

二分查找方程的根

针对单调递增或单调递减函数，在两端正负函数值下夹出一个根

例题一：函数f(x)=x**2−10*x+3在区间[8,12]单调上升且与x轴相交，求解该近似解，要求精度0.0001，即|f(x)|<=0.0001。

例题二：函数f(x)=x2−10x+3在区间[-2, 2]单调下降且与x轴相交，求解该近似解，要求精度0.0001 (|f(x)|<=0.0001)。

例题三：函数f(x)=x2−10x+3在区间[-2, 12]与x轴有两个交点，求解这两个近似解，要求精度0.0001，即|f(x)|<=0.0001。

二分法查找和或平方和

1. 对前面n-1个数循环（外循环），每次循环，都将这个数和它后面的数进行配对（内循环），时间复杂度是O(n2)。
2. 先排序，然后对前n-1个元素循环，每次循环时，对元素a，到后面用二分法搜索X-a，虽然排序的复杂度是O(nlogn)，但是循环的复杂度也是O(nlogn)，因此优于算法1。

算法一：

算法二：O(nlogn)

例题一：编写一个程序，用来在一个数字列表中搜索2个数a和b，使得a2+b2=x，其中x为一个给定的数。

例题二：二分求和扩展：在列表A中搜索元素b，使得a的各位数之和加上b的各位数之和==x（如12与34的每一位数字之和为10）

求和问题

给定4组数（元素总数n相同，n<=100 ），在每组数中找一个数，使得4个数之和为0，求共有多少组数符合条件（不同的索引号算不同的结果）。例如：[-45, -41, -36, -36, 26, -32] [22, -27, 53, 30, -38, -54] [42, 56, -37, -75, -10, -6] [-16, 30, 77, -46, 62, 45] 结果为：5

最容易想到的思路是暴力求解，即设计4重循环，对每种可能的组合进行求和，每当和为0时，计数器加1即可。O(n4)

解题思路：考虑若4个数a+b+c+d=0,则a+b=-(c+d)。如果找出所有的a+b，放入一个列表X，对于任一个-(c+d)，若能在X中找到，则存在1个解，而搜索的过程可以利用二分法提高效率。

对列表A和B进行所有可能的求和，将结果放入列表X，对X排序。 对列表C和D进行所有可能的求和，求和结果取负数，记为key，然后用二分法在X中搜索key，如果找到，则存在一组数据的和为0。

时间复杂度，对n2个元素排序：O(n2log(n2))=O(n2log(n))

n=100时，循环次数<105，时间不到1秒

每次找到x，都尝试向前搜索，直到找到最前面的x为止；再尝试向后搜索，直到找到最后面的x为止

例题一：从键盘输入两个整数n，m，求出n与m的最大公约数 样例输入

24 78样例输出6

例题二：递归求阶乘

例题三：输入一个字符串，判断该字符串是不是回文字符串，如果是返回“Yes”，不是返回“No”

样例输入

上海自来水来自海上

样例输出

Yes

例题四：从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。

从键盘输入整数n，m，计算从n个不同元素中取出m个元素的组合数。

样例输入

5 2

样例输出

10

例题五：从键盘输入一个列表，元素为整数，调用递归函数sumLIst(L)，求出列表L中所有元素的和，返回和，在主函数中输出。

样例输入：

[1,2,3,4,5,6]

样例输出

sum = 21

中文支持

默认使用英文字库，汉字会乱码，要指定中文字库

解决负号不显示问题

用plot函数绘制线图并存为文件

用pie函数绘制饼图

plt.pie(data,explode)

Data为绘图数据,explode为图形显示的方式，为0表示该部分与整个图不分离，大于0表示该部分与整个图分离，分离距离与该数据大小有关。

用bar函数绘制条形图plt.bar(left,height,width,bottom)

Left为x轴坐标，height为条形高度，width为宽度(默认0.8），bottom为条形起始位置（ex4.py)

 对图片进行修饰

  plt.plot(x,y,'b:s',label='直线')

‘b:s’包含线的颜色

线条的颜色：r红色、g绿色、b蓝色、m洋红、k黑色等

线的类型：实线-、虚线--、虚点线-.、点线: 等

标记符号：

Label表示要显示标注的内容

title表示图表标题

plt.xlabel(‘自变量’)，表示横坐标方向的提示

plt.ylabel(‘因变量’)，表示纵坐标方向的提示

plt.legend(loc=‘lower right’)，表示标注的显示位置

分别有：lower right、lower left、upper left、upper right、upper center、lower center

实训

1 线图不同周期正弦曲线对比图（2π周期和π周期）

2 饼图某手机店上个月各品牌手机销量的饼图（分离块的距离为0.1）

3 条形图4个班级考试平均成绩的条形图

导入文件

用pandas载入excel文件

使用read_excel函数从excel文件载入数据，read_excel函数返回1个DataFrame对象。

用numpy载入csv文件/文本文件

使用numpy载入csv文件，其本质是文本文件，数据之间用逗号隔开。

使用numpy载入csv文件的方式如下：

注意，csv文件如有表头，应先删除表头再载入，numpy假设csv数据文件中全是数值信息。

对载入的数据进行可视化

使用matplotlib绘图时，坐标轴使用的数据既可以是列表，也可以是numpy数组中的一列，或者pandas的DataFrame电子表格的一列。

将numpy和pandas载入文件的知识和matplotlib绘图知识结合起来，就能完成数据的可视化任务，有关使用matplotlib绘图的知识，请参考第一关的内容。

实训编程要求

本关卡需要完成2个图片的绘制。1 绘制股票的走势图输入的excel文件拥有5列：日期、开盘、最高、最低、收盘，文件的第一行是列名，文件中有10天的股票数据，数据的格式如下所示：

要求：在同一张图中绘制开盘价的走势图（蓝色，横轴是日期，纵轴是开盘价），以及收盘价的走势图（红色，横轴是日期，纵轴是开盘价），在线图中使用到三角形标记。下图是正确的图像：

2 绘制不同年度的国民生产总值的条形图输入的csv文件为我国1998年到2005年的国民生产总值数据，包含年度、国内生产总值、第一产业、第二产业、第三产业共5列数据，其数据格式如下：

要求：使用年度为横轴，国内生产总值为纵轴，绘制条形图。下面是正确的图像：

编程题

1.递归法解题（状态转移方程）.【题目描述】

小明上台阶时，有时候一步迈上1级台阶，有时候一步迈上2级台阶。若一个台阶有n级，问小明一共有多少种方案上完台阶。例如，如果台阶为3级，小明有3种不同的方案：1）每次都迈上1级。2）先迈上1级，再迈上2级。3）先迈上2级，再迈上1级。

【输入输出格式】

输入为整数n，表示台阶的级数。0<n<=50。

输出为整数，表示方案总数。

【输入输出样例】

输入：3输出：3

提示：可以用递归来求解，也可以用迭代法来求解；若使用递归，需要进行优化以消除重复计算，否则n较大时会超时。

这里其实是一个状态转移方程，一般形式的话就是斐波那契数列

定义一个数组 dp，其中 dp[i] 表示到达第 i 级台阶的不同方式的总数。

初始化条件：

dp[0] = 1，表示有1种方式停留在地面。

dp[1] = 1，表示只有1种方式到达第1级台阶。

状态转移方程：对于 i >= 2，dp[i] = dp[i-1] + dp[i-2]，即可以从 i-1 级台阶和 i-2 级台阶到达第 i 级台阶。

dp[3] = dp[2] + dp[1] = 2 + 1 = 3

递归法：

迭代法：

2.Numpy的应用（求定积分）

【题目描述】

用蒙特卡罗投点法求下面的积分

投点矩形的上界取函数在区间内的最大值，下界取0。

【输入输出格式】

从键盘输入总的实验点数n，输出的结果保留8位小数。

【输入输出样例】

输入：20000输出：0.07177380

提示：ln(x)可使用np.log(x)完成

3.二分法查找数字

对于给定的整数X，请使用二分法在一个升序列表中查找两个整数a和b，要求符合下面的条件：
a3+b3=X
如果找到了，请输出这两个数，并用空格分隔；如果没有找到，请输出-1
序列是使用随机函数生成的，已经给出生成序列并排序的代码。
【输入输出】
输入为一个整数：X
输出为2个整数：要找的2个数，中间用空格隔开，较小的数放前面。若有多组符合条件的数，仅输出其中a最小的一组。
【输入输出样例】
输入：24397输出：2 29

请使用二分法在一个升序列表中查找两个数，使得两者的立方和等于给定的数X。如果找到了，请输出这两个数，并用空格分隔；如果没有找到，请输出-1

4.反推的一个循环

一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了n个村子后还剩m只鸭子，问他出发时共赶多少只鸭子？（n和m是输入的已知值）

比如6只，卖去一半又一只后为两只，反推的话，没经过一个村子，原来的鸭子数等于剩下的鸭子数+1再乘2

5.列表的应用

学生成绩已经输入到列表scores中，请计算成绩的均值mean和中位数med(中位数计算方式为：若序列个数为奇数，中位数为序列升序排列中正中间的数，若若序列个数为偶数，中位数为序列升序排列中正中间的2个数的均值）。

6 .Numpy应用

代码中score表示n个学生3门功课的成绩表，数据已经生成，要求：（1）求出每门课程的最高分以及对应的行索引，输出最高分及行索引（从第1行开始计数）。（2）求出每个学生的平均成绩并输出。
样例1：
输入
3
输出
课程最高分
[75 99 98]
课程最高分对应的行号
[3 2 3]
学生平均成绩
[70. 75.66666667 84. ]

np.argmax函数可以返回数组中最大元素的索引。

如果数组是多维的，则可以指定要沿着哪个轴进行搜索最大值。

如

7.Numpy的切片和统计函数的应用

a是一个n行m列的二维数组，求出数组周边元素之和。

例如：a为

[[16, 7, 23, 58],

[46, 23, 32, 69],

[40, 85, 45, 8]]

周边元素之和为397

8.

9.循环输出

10.二分法求根

或

11.数组的操作

C

B

二分查找的时间复杂度 O(log n) 通常优于暴力查找的时间复杂度 O(n)，尤其在数据量较大时。