Python零基础速成班-第7讲

零基础速成班-第7讲-注释、算法基础、排序、查找、时间复杂度 学习目标 注释算法基础排序、查找、时间复杂度课后作业(4必做1挑战)
友情提示:将下文中代码拷贝到中直接执行即可,部分代码需要连续执行 。
1、注释(note)介绍
1.注释就是对代码的解释和说明,其目的是让人们能够更加轻松地了解代码 。
2.注释是编写程序时 , 写程序的人给一个语句、程序段、函数等的解释或提示,能提高程序代码的可读性 。
3.在有处理逻辑的代码中,源程序有效注释量必须在20%以上 。
代码注释分类 1.1 行注释:使用#号开头 , 在符号后那一行不会被编译(显示)
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 aparam
:: this is aof what is
: :an
“”"
1.4.2 风格
“”"
This is astyle docs.
:
- this is the first param
- this is aparam
:
This is aof what is \
:
-an
“”"
1.4.3. (Numpy风格)
“”"
Myof a kind
of very.
first :
the 1st param name first

Python零基础速成班-第7讲

文章插图
:
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=0flag=0for i in range(1,1000000):if i%2: #有余数 Trueif flag == 0:pi += 1/iflag=1else:pi -= 1/iflag=0print(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 =10000x =int(input("请输入需要求平方根的数字>>>\n"))low,high=0,xfor i in range(trys):guess = (low+high)/2if guess**2 < x:low = guesselse:high = guessprint(guess)
请输入需要求平方根的数字>>>52.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 listbubbleSort(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 listinsertionSort([3,7,10,5,8,12,4,6])
[3, 4, 5, 6, 7, 8, 10, 12]
3.归并排序Merge Sort示例:不断向下拆分后比较,最后合并,时间复杂度O(n log n)
29548167295481672954816729548167294518672459167812456789
merge sort 时间复杂度
Python零基础速成班-第7讲

文章插图
64log n3232O(n)1616O(n)88O(n)
【Python零基础速成班-第7讲】import randomdef 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 resultmergeSort(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时 , 则采用插入排序
128Merge6464Merge3232Merge1616Insertion
3.3 查找及时间复杂度 O(1)时间复杂度为1的情况
def square(x):return x*xsquare(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 maxfindmax([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 duplifindduplicate([1,3,5,7,9,2,3,6,8,0,7])
[3, 7]
二分法查找  , 又称折半检索 , 时间复杂度为 O( l o g 2 nlog2?n)
二分法查找思路:
首先将给定值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 -1print(binarySearch([1,2,3,4,5,6,7],5))
4
4、课后作业 , 答案在下一讲 1、完成一个包含文档注释的函数(函数功能为两个数相除),注释风格为主流reST Style,包含param , ,raise,by,等关键字 。
您的代码:
2、请统计"Hello, have you tried ouryet?" 中每个元音字母各出现了多少次?
您的代码:
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.00balance =10000.00bal_list = []for year in range(1,21):balance += balance*rate/100print("%4d .2f" %(year,balance))bal_list.append(balance)
110500.00211025.00311576.25412155.06512762.82613400.96714071.00814774.55915513.281016288.951117103.391217958.561318856.491419799.321520789.281621828.751722920.181824066.191925269.502026532.98
2、(扩展)在第一题的基础上通过绘制一张x(金额)/y(年)的曲线图(收益表)
import matplotlib.pyplot as pltfig,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 piage = 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:20Please select one of: Male, FemaleMaleage=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.面条价格:62.米饭价格:23.抄手价格:84.馒头价格:1---------2.饮料---------1.芬达价格:32.无糖可乐价格:43.面汤价格:14.酸梅汁价格:2---------3.小吃---------1.甩饼价格:42.糍粑价格:73.小油条价格:84.金银馒头价格:6
*(挑战)5、编程实践项目 判卷问题:设计一个自动判卷程序 我们帮助数学老师判卷子,本次数学题一共10题,每题10分 。已经知道正确答案分别是"",要求输入学生结果能找出错误并指出最终分数 。
correct_answers = "adbdcacbda"correct_list = list(correct_answers)done =Falsewhile 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"]*10print("user_answers={}\njudgement={}\nfinallytotal={}".format(judge_list,judge_dict,total))
Enter your exam answers!>>>abbdaccddauser_answers=['Y', 'X', 'Y', 'Y', 'X', 'X', 'Y', 'X', 'Y', 'Y']judgement={'X': 4, 'Y': 6}finallytotal=60