資源簡介

5.3 運用典型算法
第5單元 程序設計入門
任務 1
運用排序算法
列表
1
數據處理通常會涉及很多數據，這些數據需要一個容器進行管理，這個容器就是數據結構，Python中的數據結構主要有序列(列表、元組等)集合和字典。列表(list)是 Python最常用的序列，具有可變性，可以追加、插、刪除和替換元素。
創(chuàng)建列表
創(chuàng)建列表可以使用方括號“[]”將元素括起來，元素之間用逗號分隔。
a=[12,35,56,23]
b=['張三','李四','王五']
列表
1
追加元素
a=[12,35,56,23]
a.append(30) #在列表后面追加一個元素
a+=[30,40] #利用“+=”運算符在列表后面追加多個元素
a.extend([30,40]) #利用“extend()”方法在列表后面追加多個元素
要在列表中追加單個元素,可使用 append()方法；要在列表中追加多個元素或另一個列表，可使用“+=”運算符或 extend()方法。
列表
1
插入元素
a=[12,35,56,23]
a.insert(2,30) #在列表索引2（第3個元素）位置上插入一個元素
使用insert()方法可以在列表中指定索引位置插入一個元素。
替換元素
使用“=”運算符可以替換列表的元素。
a=[12,35,56,23]
a[1]=10 #在列表索引1位置上將35替換為10
列表
1
刪除元素
a=[12,35,56,23]
a.remove(35) #在列表中查找第一個值為35的元素并刪除
a.pop(1) #刪除列表索引1位置上的元素
使用 remove()方法或pop()方法可以刪除列表中的元素。remove()方法從左至右查找列表中的元素，如果找到匹配的元素則刪除；如果找到多個匹配元素，只刪除第一個；如果沒有找到則提示錯誤。pop()方法刪除指定索引位置上的元素，如果不指定索引位置，則刪除最后一個元素。
選擇排序算法
2
選擇排序基本思路：每次從待排序的數據中選出最小元素，順序放在之前已經排好序的數據最后，直到全部數據排序完畢。實現(xiàn)方法：取第一個數和后面的數逐一比較，然后一輪之后得到最小的數放在第一個，然后開始取第二個,重復之前的比較。
選擇排序算法
2
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}7
4
5
9
8
2
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
4
5
9
8
2
7
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
2
5
9
8
4
7
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
2
4
9
8
5
7
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
2
4
5
8
9
7
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
2
4
5
7
9
8
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
2
4
5
7
8
9
初始狀態(tài)：
第1輪：
第2輪：
第3輪：
第4輪：
第5輪：
第6輪：
選擇排序算法
2
假設排序列表為a，數據個數為n。
a=[7,4,5,9,8,2,1]
for i in range(len(a)-1):
minIndex=i #記錄最小數索引
for j in range(i+1,len(a)):
if a[minIndex]>a[j]: #若找到更小的數
minIndex=j #將找到的最小數和未排序的第一個數交換
a[i],a[minIndex]=a[minIndex],a[i]
print(a)
插入排序算法
3
插入排序基本思路：每次取出一個待排序的數據元素，按其大小插入到之前已經排好序的數據集中，直到全部待排序元素插入完畢。具體實現(xiàn)方法為：從左邊開始取值，然后和它左邊的所有元素值進行比較，如果取的值比它左邊的值小就與其交換，重復以上操作。
插入排序算法
3
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}7
4
5
9
8
2
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}4
7
5
9
8
2
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}4
5
7
9
8
2
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}4
5
7
9
8
2
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}4
5
7
8
9
2
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}2
4
5
7
8
9
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
2
4
5
7
8
9
初始狀態(tài)：
第1輪：
第2輪：
第3輪：
第4輪：
第5輪：
第6輪：
插入排序算法
3
假設排序列表為a，數據個數為n。
a=[7,4,5,9,8,2,1]
for i in range(1,len(a)): #從第二個數開始
for j in range(i-1,-1,-1): #從外層循環(huán)的下標值比較到第一個數
if a[j+1] a[j+1],a[j]=a[j],a[j+1] #較小的值左移
print(a)
Python功能庫
4
Python既有內置函數和標準庫，又有第三方庫和工具，可用于文件讀寫、網絡抓取和解析、數據庫連接、音視頻處理、數據挖掘、機器學習等，靈活運用 Python功能庫，能夠擴展程序功能，提高編程效率。
通常用 import命令就可以引Python功能庫，例如，要與 MySQL數據庫建立連接，就要使用第三方庫 pymysql，引入這個庫的語句為:
import pymysql
實踐體驗
5
編寫籃球比賽積分排名程序。
課后拓展
6
采用插入排序算法，對某一字符列表進行降序排序。
操作提示：字符排序是按照字符的ASCII碼順序，且相同字母的大小寫其ASCII碼不相同。
02
鞏固提高
01
討論與交流
通過網絡查閱并討論其他排序算法。
任務 2
運用查找算法
順序查找算法
1
順序查找也稱線性查找，即從數據結構線性表的一端開始，順序掃描，依次將掃描到的關鍵字與給定值相比較，若相等則表示查找成功；若掃描結束仍沒有找到關鍵字等于給定值的數據，表示查找失敗。順序查找多用于查找對象的排列無規(guī)律時。假設查找列表為a，對象個數為n，算法流程圖如圖所示。
流程圖
順序查找算法
1
a=['B','A','E','F','D','C']
target='E' #查找目標
i=0 #初始查找位置
found=False #查找是否成功標志
while i if a[i]==target: #查找匹配對象
found=True
else:
i+=1 #未找到繼續(xù)掃描下一個對象
print(found)
示例代碼
二分查找算法
2
二分查找也稱折半查找，比順序查找的效率高，但它要求待查數據結構是有序排列的，適用于不經常變動且查找頻率較高的有序數據。二分查找從數據結構的中間位置開始，如果中間元素正好與查找關鍵字相等，則查找成功；否則利用中間位置將數據分成前、后兩個部分，如果中間元素大于查找關鍵字，則繼續(xù)在前一半數據中查找，否則繼續(xù)在后一半數據中查找，重復這樣的操作，每一次比較都使搜索范圍縮小一半。
二分查找算法
2
如要在序列“10,20,40,60,70,80,90”中查找70，查找過程示意圖如圖所示。
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}10
20
40
60
70
80
90
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}70
80
90
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}70
第1輪：
第2輪：
第3輪：
偏小
偏大
正確
二分查找算法
2
假設查找列表a，對象個數為n。
a=[10,20,40,60,70,80,90] #有序列表
target=70 #查找目標
i=0 #初始查找位置
j=len(a)-1
while i<=j:
m=(i+j)//2 #取中間值
if a[m]==target:
print("所查對象位置下標:",m)
break
elif a[m]>target:
j=m-1
else:
i=m+1
流程圖
示例代碼
實踐體驗
3
編寫英語單詞默寫程序。
課后拓展
4
02
鞏固提高
01
討論與交流
通過網絡查閱并討論其他查找算法，討論5.2任務2中猜數字游戲，用哪種查找方式速度最快。
某公司舉行新產品發(fā)布會，參會客戶都進行了登記，采用二分查找算法，在登記表中查找是否有某一客戶參會。操作提示:需要先按照客戶名稱排序。
課后拓展
5
03
探究與合作
1.玩轉“漢諾塔”游戲——遞歸算法
“漢諾塔”是一個古老的益智游戲，如圖所示，木板上有3根柱子，分別是原始柱、借力柱和目標柱，原始柱上有若干個圓盤，規(guī)定每次只能移動一個圓盤，且小的圓盤只能疊在大的圓盤上面。請設計算法，用盡可能少的次數把所有圓盤從原始柱全部移動到目標柱上。
操作提示：遞歸算法是一種直接或者間接調用自身的算法(如函數的自調用)，它體現(xiàn)了“以此類推” “用同樣的步驟重復”的思想，可以使算法的描述簡潔，易于理解，其實質是把問題轉換為規(guī)模縮小了的同類問題。
課后拓展
5
03
探究與合作
2.繪制遞歸圖形
Python程序中內置了大量的函數，turtle模塊是其中一個繪制圖形的函數庫，就像一只小烏龜，在一個橫軸為x、縱軸為y的坐標系原點(0,0)位置開始，根據一組函數指令的控制，在這個平面坐標系中移動，從而在它爬行的路徑上繪制了圖形。嘗試繪制一個自己喜歡的遞歸圖形。
單元小結
6
本單元主要學習了算法的基本概念，計算機程序、程序設計語言、程序基本結構、Python基本語法及排序算法、查找算法等典型算法的基礎知識，初步掌握了程序設計的方法，能使用程序設計工具編輯、運行和調試簡單的程序，具備了運用程序設計解決簡單問題的初步能力。
謝謝觀看！

展開更多......

收起↑