Python零基础速成班-第7讲
零基础速成班-第7讲-注释、算法基础、排序、查找、时间复杂度 学习目标 注释算法基础排序、查找、时间复杂度课后作业（4必做1挑战）
友情提示：将下文中代码拷贝到中直接执行即可，部分代码需要连续执行。
1、注释(note)介绍
1.注释就是对代码的解释和说明，其目的是让人们能够更加轻松地了解代码。
2.注释是编写程序时，写程序的人给一个语句、程序段、函数等的解释或提示，能提高程序代码的可读性。
3.在有处理逻辑的代码中，源程序有效注释量必须在20％以上。
代码注释分类 1.1 行注释：使用#号开头，在符号后那一行不会被编译（显示）
python">print("hello everyone!") #向大家打招呼
hello everyone!
1.2 块注释：使用三个单引号 ’ 或者双引号 " 开头和结尾，被块注释符号中间的部分不会被编译
'''
这是使用三个单引号的多行注释
这是第二行
这是第三行
'''
'\n这是使用三个单引号的多行注释\n这是第二行\n这是第三行\n'
"""
这是使用三个双引号的多行注释
"""
'\n这是使用三个双引号的多行注释\n'
1.3 注释的使用，文档注释在函数中的应用
在函数体的第一行使用一对三个单引号 ‘’’ 或者一对三个双引号 “”" 来定义文档字符串。你可以使用 doc（注意双下划线）调用函数中的文档字符串属性。
编写示例如下：
def addfun(num1,num2):""" 完成传入的两个数之和:param num1: 加数1:param num2: 加数2:return: 求两个数的和"""return num1 + num2print( addfun.__doc__ )
完成传入的两个数之和:param num1: 加数1:param num2: 加数2:return: 求两个数的和
1.4 文档注释常用编写风格
文档注释常用关键字：
①为函数传入参数
②为函数返回结果
③为函数可能会有的报错信息
1.4.1 这是现在流行的一种风格，reST风格，的御用格式，比较紧凑。
“”"
This is a reST style.
:param : this is a first param
:param : this is a param
:: this is a of what is
: : an
“”"
1.4.2 风格
“”"
This is a style docs.
:
- this is the first param
- this is a param
:
This is a of what is \
:
- an
“”"
1.4.3. (Numpy风格)
“”"
My of a kind
of very .
first :
the 1st param name first
:
the 2nd param
third : {‘value’, ‘other’},
the 3rd param, by ‘value’
a value in a
when a key error
when an other error
“”"
1.5 一些注释经验 注释不是越多越好。对于一目了然的代码，不需要添加注释。对于复杂的操作，应该在操作开始前写上相应的注释。对于不是一目了然的代码，应该在代码之后添加注释。绝对不要描述代码。一般阅读代码的人都了解的语法，只是不知道代码要干什么。 2、算法基础 basis 2.1 我们以计算 π \pi π值为例子：可以使用下面公式 π 4 = 1 − 1 3 + 1 5 − 1 7 + 1 9 . . . \frac{\pi}{4}= 1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}... 4π=1−31+51−71+91...
算法思路：
我们设计一个变量flag，当它为0时，做+法并设置为1，当他为1时，做-法并设置为0，反复循环形成+ - + - + -…
通过i%2有余数，求出奇数，得出1/i
pi=0
flag=0
for i in range(1,1000000):if i%2: #有余数 Trueif flag == 0:pi += 1/iflag=1else:pi -= 1/iflag=0
print(pi*4)
3.141590653589692
2.2 我们还可以通过预估模型：蒙特卡洛模拟计算 π \pi π值
算法思路：
想象一个圆形靶子，我们不停地向靶面射击，命名圆内的我们算是"击中" 也就是 x 2 + y 2 = 1 x^2+y^2=1 x2+y2=1。假如我们不停地射击，直到我们把这个方形的靶子全部覆盖"打成筛子"。圆的面积应该是 S c i r c l e = π r 2 S_{}={\pi}r^2 =πr2方形的面积应该是 S s q u a r e = a 2 S_{}=a^2 =a2也就是说 S c i r c l e / S s q u a r e = π r 2 / a 2 r = 1 , a = 2 {S_{}/S_{}={\pi}r^2/a^2}_{r=1,a=2} /=πr2/a2r=1,a=2 S c i r c l e / S s q u a r e = π / 4 S_{}/S_{}={\pi}/4 /=π/4 π = 4 ∗ ( S c i r c l e / S s q u a r e ) {\pi}= 4 * (S_{}/S_{}) π=4∗(/)
在程序中trys 变量为我们尝试的次数，次数越多，越精确
hits 变量为命中数量
x = -1+2 * ()表明x轴在-1到1之间；y = -1+2 * ()表明y轴在-1到1之间
x ** 2 + y ** 2 1，求x的平方根y，0 ②假设 guess是(low+high)/2，如果guess的平方非常接近x，那么y=guess
③若 g u e s s 2 guess^2 ④若 g u e s s 2 guess^2 >x，high设定为guess，然后重复第二步
在程序中，trys为迭代次数，次数越多，越精准。
trys =10000
x =int(input("请输入需要求平方根的数字>>>\n"))
low,high=0,x
for i in range(trys):guess = (low+high)/2if guess**2 < x:low = guesselse:high = guess
print(guess)
请输入需要求平方根的数字>>>
5
2.23606797749979
3、排序、查找、时间复杂度 3.1 我们简单介绍冒泡、插入、归并三种排序 Sort 多次遍历数组，每次遍历相邻元素，如果没有按照顺序排列，则互换他们。 Sort 重复地将新元素插入到一个排好序的子线性表中，直到整个线性表排好序。Merge Sort 将数组分为两半，对每部分递归地应用归并排序，在两部分都排好序后，对它们进行归并。 1.冒泡排序 Sort示例：因为是双循环嵌套，所以时间复杂度是O( n 2 n^2 n2)
①
②
③
④
⑤
import random #冒泡排序
def bubbleSort(list:"需要排序的数组")->"输出排好序的数组":for i in range(1,len(list)):for j in range(0,len(list)-i):if list[j] > list[j+1]:list[j],list[j+1]=list[j+1],list[j]return list
bubbleSort(random.sample(range(0,100),8))
[32, 40, 42, 69, 80, 86, 91, 96]
2.插入排序 Sort示例：将不断与之前的元素进行比较，如小于前一个元素则互换位置，时间复杂度介于 O(n) and O( n 2 n^2 n2)之间
① =9
② >> =5
③ >> =4
④ >> =8
⑤ >> =1
def insertionSort(list:list)->"sortedlist":for i in range(1,len(list)):current =list[i]k= i-1 #从左边第一个开始循环while k>=0 and list[k] > current: #左边大于current值时，向右移一位，直到不大于currentlist[k+1] = list[k]k-=1list[k+1] = current #把current相应的位置赋值currentreturn list
insertionSort([3,7,10,5,8,12,4,6])
[3, 4, 5, 6, 7, 8, 10, 12]
3.归并排序Merge Sort示例：不断向下拆分后比较，最后合并，时间复杂度O(n log n)
295481672954 816729 54 81 67
2 9 5 4 8 1 6 729 45 18 672459 167812456789
merge sort 时间复杂度
64 log n32 32 O(n)16 16 O(n)8 8 O(n)
import random
def mergeSort(list):n = len(list)#获取长度if n <=1:#如果列表长度1，直接返回return listmid = n//2 #取中间值，把数组拆分left = mergeSort(list[:mid])#取左半部分right = mergeSort(list[mid:])#取右半部分leftp = 0 #左半指针从0开始rightp = 0 #右半指针从0开始result =[]#定义空数组存储每次归并好的列表while leftp < len(left) and rightp < len(right):#当左右指针分别小于长度时if left[leftp] <= right[rightp]:result.append(left[leftp])leftp +=1else:result.append(right[rightp])rightp +=1result += left[leftp:]#考虑数组为奇数，把最后元素添加进来result += right[rightp:]return result
mergeSort(random.sample(range(0,100),20))
[0, 4, 8, 14, 16, 24, 35, 38, 49, 56, 62, 68, 75, 77, 78, 81, 87, 88, 89, 97]
3.2 系统排序采用归并排序和插入排序相结合 例如对128位长度的数组进行排序，前期均采用归并排序，当长度到达16时，则采用插入排序
128 Merge64 64 Merge32 32 Merge16 16 Insertion
3.3 查找及时间复杂度 O(1)时间复杂度为1的情况
def square(x):return x*x
square(100)
10000
查找数组中的最大值，需要遍历数组，时间复杂度为O(n)
def findmax(list):max = list[0]for i in range(1,len(list)):if list[i] > max:max = list[i]return max
findmax([1,4,0,8,4,9,3])
9
查找数组中重复的数字，需要双循环嵌套，时间复杂度为 O( n 2 n^2 n2)
def findduplicate(list):dupli=[]for i in range(len(list)):for j in range(i+1,len(list)):if list[i] == list[j]:dupli.append(list[i])breakreturn dupli
findduplicate([1,3,5,7,9,2,3,6,8,0,7])
[3, 7]
二分法查找 ，又称折半检索，时间复杂度为 O( l o g 2 n log2n)
二分法查找思路：
首先将给定值key与字典中间位置上元素的关键码(key)比较，如果相等，则检索成功。否则，若key小，则在字典前半部分中继续进行二分法检索。若key大，则在字典后半部分中继续进行二分法检索。这样，经过一次比较就缩小一半的检索区间，如此进行下去，直到检索成功或检索失败，失败返回-1。二分法检索是一种效率较高的检索方法。
进阶提示：
二分法查找需要先对数组进行排序。
def binarySearch(list,value):low=0high=len(list)while(low <= high):mid = (low + high) // 2if (list[mid]==value):return midelif (value > list[mid]):low = mid + 1else:high = mid - 1return -1
print(binarySearch([1,2,3,4,5,6,7],5))
4
4、课后作业，答案在下一讲 1、完成一个包含文档注释的函数(函数功能为两个数相除)，注释风格为主流reST Style，包含param，，raise， by，等关键字。
您的代码：
2、请统计"Hello, have you tried our yet?" 中每个元音字母各出现了多少次？
您的代码：
3、根据公式 n ∗ ( n − 1 ) n * (n-1) n∗(n−1)，生成一个100个数组的列表，例如：
[0,2,6,12,20,30,42…]
您的代码：
4、制作一个 Uint ，通过dict快速实现①选择转换类型②参数输入③结果输出 1英寸inch=25.4毫米 1英尺feet=30.5厘米 1英里mile=1.61公里 1码yard=0.914米 1浪wave=204米
您的代码：
*(挑战) 5、编程实践项目 大数据下：比较两种排序的效率情况 随机从0~中，取1000个整数，填入数组，分别进行冒泡排序和归并排序(两种方法可参考上文书写)，比较它们的效率(执行耗时)。再取10000个整数，再试试执行效率。将程序写进class，分别通过class+函数名调用方法。
tips:函数运行时间可以使用下列函数
def timer(f):def _f(*args):t0=time.time()f(*args)return time.time()-t0return _f
您的代码：
5、上一讲零基础速成班-第6讲-异常处理，try&，raise，，输入模块 课后作业及答案 1、计算银行带来的回报，假设你存银行一笔钱是10000，年利率是5%，则计算20年后，变成了多少钱？打印每一年的变化
rate=5.00
balance =10000.00
bal_list = []
for year in range(1,21):balance += balance*rate/100print("%4d .2f" %(year,balance))bal_list.append(balance)
1 10500.002 11025.003 11576.254 12155.065 12762.826 13400.967 14071.008 14774.559 15513.2810 16288.9511 17103.3912 17958.5613 18856.4914 19799.3215 20789.2816 21828.7517 22920.1818 24066.1919 25269.5020 26532.98
2、(扩展)在第一题的基础上通过绘制一张x(金额)/y(年)的曲线图(收益表)
import matplotlib.pyplot as plt
fig,ax =plt.subplots()
ax.plot([i for i in range(1,21)],bal_list)
ax.set(xlabel="n th year",ylabel="Money",title="How much I got")
ax.grid()
plt.show()
3、安装并使用输入模块，完成age输入验证(数字0~110，最多输入2次)，性别输入(男、女，限时10秒钟内)，输出年龄，性别
import pyinputplus as pi
age = pi.inputInt("Please enter age：",min=0,max=110,limit=2)
gender = pi.inputChoice(['Male','Female'],timeout=10)
print("age={} gender={}".format(age,gender))
Please enter age：20
Please select one of: Male, Female
Male
age=20 gender=Male
4、制作一个菜单，其中包括小吃、饮料、主食等分类，每个分类下包含多种食物，左边是名字右边是价格，请尽量美观的把菜单打印出来。
menu_dict={"1.主食":{"1.面条":6,"2.米饭":2,"3.抄手":8,"4.馒头":1},"2.饮料":{"1.芬达":3,"2.无糖可乐":4,"3.面汤":1,"4.酸梅汁":2},"3.小吃":{"1.甩饼":4,"2.糍粑":7,"3.小油条":8,"4.金银馒头":6},
}
menu_dict={"1.主食":{"1.面条":6,"2.米饭":2,"3.抄手":8,"4.馒头":1},"2.饮料":{"1.芬达":3,"2.无糖可乐":4,"3.面汤":1,"4.酸梅汁":2},"3.小吃":{"1.甩饼":4,"2.糍粑":7,"3.小油条":8,"4.金银馒头":6},
}
for k,v in menu_dict.items():print("{}".center(20,"-").format(k))for k1,v1 in v.items():print("{}".ljust(6," ").format(k1),"价格:{}".rjust(15-len(k1.encode("GBK"))," ").format(v1))
---------1.主食---------
1.面条 价格:6
2.米饭 价格:2
3.抄手 价格:8
4.馒头 价格:1
---------2.饮料---------
1.芬达 价格:3
2.无糖可乐 价格:4
3.面汤 价格:1
4.酸梅汁 价格:2
---------3.小吃---------
1.甩饼 价格:4
2.糍粑 价格:7
3.小油条 价格:8
4.金银馒头 价格:6
*(挑战)5、编程实践项目 判卷问题：设计一个自动判卷程序 我们帮助数学老师判卷子，本次数学题一共10题，每题10分。已经知道正确答案分别是""，要求输入学生结果能找出错误并指出最终分数。
correct_answers = "adbdcacbda"
correct_list = list(correct_answers)
done =False
while not done:user_answers = input("Enter your exam answers!\n>>>")if len(user_answers)== len(correct_answers):user_list =list(user_answers)done = Trueelse:print("length is not equal")
judge_list= list(map(lambda user,corr:"Y" if user ==corr else "X",user_list,correct_list))
judge_dict={i: judge_list.count(i)for i in set(judge_list)}
total= judge_dict["Y"]*10
print("user_answers={}\njudgement={}\nfinallytotal={}".format(judge_list,judge_dict,total))
Enter your exam answers!
>>>abbdaccdda
user_answers=['Y', 'X', 'Y', 'Y', 'X', 'X', 'Y', 'X', 'Y', 'Y']
judgement={'X': 4, 'Y': 6}
finallytotal=60
