### wk13_1130_演算法_排序與搜尋
#### ch08_演算法_排序與搜尋
- 8.1 認識演算法
- 8.2 排序
泡沫排序
追蹤泡沫排序過程
- 8.3 搜尋
循序搜尋
二分搜尋
#### 【inclass practice】
##### {範例}
由小排到大排序 \<bubble>
追蹤泡沫排序法的過程 \<bubble_debuge>
```python
def switch(i) :
datas[i], datas[i+1] = datas[i+1], datas[i]
datas = [3,5,2,1]
print("排序前", datas)
switch(2)
print("排序後", datas)
```
排序前 [3, 5, 2, 1]
排序後 [3, 5, 1, 2]
```python
def switch(i) :
datas[i], datas[i+1] = datas[i+1], datas[i]
datas = [31,50,42,1]
print("排序前", datas)
n = len(datas)
for i in range(0, n):
for j in range(0, n-1):
if datas[j]<datas[j+1]:
switch(j)
print("排序後", datas)
```
排序前 [31, 50, 42, 1]
排序後 [50, 42, 31, 1]
```python
def switch(i) :
datas[i], datas[i+1] = datas[i+1], datas[i]
datas = [14,50,42,20]
print("排序前", datas)
n = len(datas)
for i in range(0, n):
print(f"i = {i}, j = {j}",end="")
for j in range(0, n-1):
if datas[j]<datas[j+1]:
switch(j)
print("排序後", datas)
```
排序前 [14, 50, 42, 20]
i = 0, j = 0i = 1, j = 2i = 2, j = 2i = 3, j = 2排序後 [50, 42, 20, 14]
###### 期末專題參考
- {實戰#3} : 透過 Python 抓取 Wiki 頁面訊息
wikipedia 工具
```python
! pip install requests beautifulsoup4
```
Requirement already satisfied: requests in c:\users\cjc11\anaconda3\lib\site-packages (2.31.0)
Requirement already satisfied: beautifulsoup4 in c:\users\cjc11\anaconda3\lib\site-packages (4.12.2)
Requirement already satisfied: charset-normalizer<4,>=2 in c:\users\cjc11\anaconda3\lib\site-packages (from requests) (2.0.4)
Requirement already satisfied: idna<4,>=2.5 in c:\users\cjc11\anaconda3\lib\site-packages (from requests) (3.4)
Requirement already satisfied: urllib3<3,>=1.21.1 in c:\users\cjc11\anaconda3\lib\site-packages (from requests) (1.26.16)
Requirement already satisfied: certifi>=2017.4.17 in c:\users\cjc11\anaconda3\lib\site-packages (from requests) (2023.7.22)
Requirement already satisfied: soupsieve>1.2 in c:\users\cjc11\anaconda3\lib\site-packages (from beautifulsoup4) (2.4)
```python
import requests
from bs4 import BeautifulSoup
import webbrowser
while True:
ur1 = requests.get("https://zh.wikipedia.org/wiki/special:Random")
soup = BeautifulSoup(ur1.content, "html.parser")
title = soup.find(class_="firstHeading").text
print(f"{title} \nDo you want to view it? (Y/N)")
ans = input("").lower()
if ans == "y":
ur1 = "https://zh.wikipedia.org/wiki/%s" % title
webbrowser.open(ur1)
break
elif ans == "n":
print("Try again")
continue
else:
print("Wrong choicel")
break
```
嘉玛尤诺斯
Do you want to view it? (Y/N)
y
#### 【afterclass practice】
1. 綜合演練 選擇題1-10 (需抄題在markdown cell ; 有程式碼的題目要有code cell )
2. 名詞解釋 : 演算法、虛擬碼、流程圖
###### 綜合演練 選擇題1-10
1. 執行下列程式，下列結果何者正確？
datas=[3,5,2,1]
n=len(datas)-1
for i in range(0,n):
for j in range(0,n-i):
if (datas[j]>datas[j+1]):
datas[j],datas[j+1]=datas[j+1],datas[j]
print(datas)
(A) [3,5,2,1] (B) [ 5,3,2,1] (C) [1,2,3,5] (D) [3,5,1,2 ]
Ans:( C )
2. 執行下列程式，下列顯示結果何者正確？
num=[67,12,9,52,91,3]
no=52
for i in range(len(num)):
if (num[i]==no):
break
print(i)
(A) 52 (B) i (C) no (D) 3
Ans:( D )
3. 下列那一個排序法，在執行搜尋前必須先將資料排序？
(A) 循序搜尋法 (B) 二分搜尋法 (C) 泡沫搜尋法 (D) 以上皆是
Ans:( B )
4. 有 10000 筆資料時，使用循序搜尋最少需多少次？
(A) 1 (B) 10000 (C) 15 (D) 14
Ans:( A )
5. 有 10000 筆資料時，使用循序搜尋最多需多少次？
(A) 1 (B) 10000 (C) 15 (D) 14
Ans:( B )
6. 有 10000 筆資料時，使用二分搜尋最多需多少次？
(A) 1 (B) 10000 (C) 15 (D) 14
Ans:( D )
7. 下列那一種搜尋方法效率最好？
(A)二分搜尋 (B)循序搜尋 (C)泡沫搜尋 (D)三者效率相同
Ans:( A )
8. 執行下列程式，下列結果何者正確？
num=[256,731,943,389,142,645,829,945]
name=["林小虎","王中森","邵木淼","李大同",
"陳子孔","鄭美麗","曾溫柔","錢來多"]
no = 100
IsFound=False
for i in range(len(name)): #逐一比對搜尋
if (num[i]==no): #號碼相符
IsFound=True #設旗標為 True
break #結束比對
if (IsFound==True):
print("中獎者的姓名為：",name[i])
else:
print("無此中獎號碼！")
print("共比對 %d次 " %(i+1))
Ans:( D )
9. 同第 8 題，中獎者的姓名為？
(A)錢來多 (B)曾溫柔 (C)鄭美麗 (D)無此中獎號碼！
Ans:( D )
10. 同第 8 題，這個程式是？
(A)二分搜尋 (B)循序搜尋 (C)泡沫搜尋 (D)以上皆非
Ans:( B )
```python
#1. 執行下列程式，下列結果何者正確？
datas=[3,5,2,1]
n=len(datas)-1
for i in range(0,n):
for j in range(0,n-i):
if (datas[j]>datas[j+1]):
datas[j],datas[j+1]=datas[j+1],datas[j]
print(datas)
```
[1, 2, 3, 5]
```python
# 2. 執行下列程式，下列顯示結果何者正確？
num=[67,12,9,52,91,3]
no=52
for i in range(len(num)):
if (num[i]==no):
break
print(i)
```
3
```python
#8. 執行下列程式，下列結果何者正確？
#9.同第 8 題，中獎者的姓名為？
#10. 同第 8 題，這個程式是？
num=[256,731,943,389,142,645,829,945]
name=["林小虎","王中森","邵木淼","李大同","陳子孔","鄭美麗","曾溫柔","錢來多"]
no = 100
IsFound=False
for i in range(len(name)): #逐一比對搜尋
if (num[i]==no): #號碼相符
IsFound=True #設旗標為 True
break #結束比對
if (IsFound==True):
print("中獎者的姓名為：",name[i])
else:
print("無此中獎號碼！")
print("共比對 %d次 " %(i+1))
```
無此中獎號碼！
共比對 8次
###### 名詞解釋 : 演算法、虛擬碼、流程圖
- 演算法（Algorithm）：演算法是一系列解決問題步驟的有序集合，是解決特定問題或執行特定任務的程式計算過程。
- 虛擬碼（Pseudocode）：虛擬碼是一種高階描述性程式碼，它類似於程式碼但不是任何特定編程語言的真正語法。虛擬碼用於描述算法或程式的邏輯結構，以一種易於理解和解釋的方式呈現，可以作為開發程式碼之前的藍圖。
- 流程圖（Flowchart）：流程圖是一種視覺化的圖形表示法，用於描述演算法、程序或系統中的流程和步驟。它以不同的符號和箭頭來表示不同的操作步驟、決策和控制流程，幫助理解算法的執行邏輯。
#### 【self practice】
```python
def disp_scores():
for score in scores:
print(score,end=" ")
print()
scores = []
while True:
inscore = input("請輸入學生的成績：")
if (inscore==""): # 雙擊 enter結束
break
scores.append(int(inscore))
print("排序前：",end=" ")
disp_scores()
n=len(scores)-1
for i in range(0,n):
for j in range(0,n-i):
if (scores[j]<scores[j+1]): # 由大到小排序
scores[j],scores[j+1]=scores[j+1],scores[j] # 兩數互換
print("成績由大到小排序：",end="")
disp_scores() # 顯示排序後串列
```
請輸入學生的成績：96
請輸入學生的成績：89
請輸入學生的成績：79
請輸入學生的成績：96
請輸入學生的成績：93
請輸入學生的成績：92
請輸入學生的成績：80
請輸入學生的成績：66
請輸入學生的成績：75
請輸入學生的成績：
排序前： 96 89 79 96 93 92 80 66 75
成績由大到小排序：96 96 93 92 89 80 79 75 66
```python
num=[67,12,9,52,91,3]
datas=[]
for i in range(0,3):
no = int(input("請輸入第 " + str(i+1) + " 個號碼："))
datas.append(no)
n=0
for i in range(0,3):
for j in range(len(num)):
if (num[j]==datas[i]):
n+=1
break
if (n>0):
print("恭喜您，中了",n,"個號碼!")
else:
print("可惜，您未中獎！")
```
請輸入第 1 個號碼：3
請輸入第 2 個號碼：24
請輸入第 3 個號碼：60
恭喜您，中了 1 個號碼!
Sign in with Wallet
Connect another wallet