## 【wk13_1130】演算法_排序與搜尋
## 【ch08_演算法_排序與搜尋】
## 【inclass practice】
8.1 認識演算法
8.2 排序
- 泡沫排序
- 追蹤泡沫排序過程
8.3 搜尋
- 循序搜尋
- 二分搜尋
```python
# 由小排到大排序
# <bubble>
# 下禮拜做
def switch(i) :
datas[i], datas[i + 1] = datas[i + 1], datas[i]
datas = [31, 5, 12, 1]
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) :
print(datas[i], datas[j], end = " ")
if datas[j] < datas[j + 1] :
switch(j)
print(datas)
print("排序後", datas)
```
File <tokenize>:15
for j in range(0, n - 1) :
^
IndentationError: unindent does not match any outer indentation level
```python
datas[0], datas[1] = datas[1], datas[0]
print(datas)
```
[5, 3, 2, 1]
```python
! pip install requests beautifulsoup4
```
Defaulting to user installation because normal site-packages is not writeable
Requirement already satisfied: requests in c:\programdata\anaconda3\lib\site-packages (2.28.1)
Requirement already satisfied: beautifulsoup4 in c:\programdata\anaconda3\lib\site-packages (4.11.1)
Requirement already satisfied: urllib3<1.27,>=1.21.1 in c:\programdata\anaconda3\lib\site-packages (from requests) (1.26.14)
Requirement already satisfied: charset-normalizer<3,>=2 in c:\programdata\anaconda3\lib\site-packages (from requests) (2.0.4)
Requirement already satisfied: idna<4,>=2.5 in c:\programdata\anaconda3\lib\site-packages (from requests) (3.4)
Requirement already satisfied: certifi>=2017.4.17 in c:\programdata\anaconda3\lib\site-packages (from requests) (2023.5.7)
Requirement already satisfied: soupsieve>1.2 in c:\programdata\anaconda3\lib\site-packages (from beautifulsoup4) (2.3.2.post1)
```python
# 期末專題參考
# 透過 Python 抓取 Wiki 頁面訊息
import requests
from bs4 import BeautifulSoup
import webbrowser
while True :
url = requests.get("https://zh.wikipedia.org/wiki/Special:Random")
soup = BeautifulSoup(url.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" :
url = "https://zh.wikipedia.org/wiki/%s" % title
webbrowser.open(url)
break
elif ans =="n" :
print("Try again!")
continue
else :
print("Wrong choice!")
break
```
黃紹曾
Do you want to view it ? (Y/N)
y
## 【afterclass practice】
1. 綜合演練 選擇題1-10 (需抄題在markdown cell ; 有程式碼的題目要有code cell )
2. 名詞解釋 : 演算法、虛擬碼、流程圖
### 綜合演練
#### 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]
( A ) [3,5,2,1]
( B ) [5,3,2,1]
( C ) [1,2,3,5]
( D ) [3,5,1,2]
```python
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]
#### 2. 執行下列程式，下列顯示結果何者正確？
num=[67,12,9,52,91,3]
no=52
for i in range(len(num)):
if (num[i]==no):
break
( A ) 52
( B ) i
( C ) no
( D ) 3
```python
num=[67,12,9,52,91,3]
no=52
for i in range(len(num)):
if (num[i]==no):
break
print(i)
```
3
#### 3. 下列那一個排序法，在執行搜尋前必須先將資料排序？
( A ) 循序搜尋法
( B ) 二分搜尋法
( C ) 泡沫搜尋法
( D ) 以上皆是
答:( B ) 二分搜尋法
#### 4. 有 10000 筆資料時，使用循序搜尋最少需多少次？
( A ) 1
( B ) 10000
( C ) 15
( D ) 14
答:( A ) 1
#### 5. 有 10000 筆資料時，使用循序搜尋最多需多少次？
( A ) 1
( B ) 10000
( C ) 15
( D ) 14
答:( B ) 10000
#### 6. 有 10000 筆資料時，使用二分搜尋最多需多少次？
( A ) 1
( B ) 10000
( C ) 15
( D ) 14
答:( D ) 14
#### 7. 下列那一種搜尋方法效率最好？
( A ) 二分搜尋
( B ) 循序搜尋
( C ) 泡沫搜尋
( D ) 三者效率相同
答:( 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))
( A ) no = 256
( B ) IsFound=True
( C ) 共比對 9 次
( D ) 以上皆非
```python
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次
答:( D ) 以上皆非
#### 9. 同第 8 題，中獎者的姓名為？
( A ) 錢來多
( B ) 曾溫柔
( C ) 鄭美麗
( D ) 無此中獎號碼！
答:( D ) 無此中獎號碼！
#### 10. 同第 8 題，這個程式是？
( A ) 二分搜尋
( B ) 循序搜尋
( C ) 泡沫搜尋
( D ) 以上皆非
答:( B ) 循序搜尋
### 名詞解釋
#### 演算法（Algorithm）
1. 定義：演算法是一組明確的、有限的、按照一定順序運行的規則或指令，用於解決特定問題或 完成特定任務。
2. 特點：演算法是一種計算過程的抽象描述，它不依賴於特定的程式語言或硬體。
3. 目的：演算法的主要目的是在有限的步驟內解決問題，並且對於相同輸入應該始終產生相同的輸出。
4. 解決問題的計算步驟集合。
#### 虛擬碼（Pseudocode）
1. 定義：虛擬碼是一種介於自然語言和真實編程語言之間的半結構化程式設計語言。它提供了一種簡單、高層次的描述方式，用於描述演算法的邏輯結構。
2. 特點：虛擬碼不是一種具體的編程語言，而是一種過渡性的表達方式，通常使用自然語言和一些 常見的程式結構（如循環、條件判斷等）。
3. 用途：虛擬碼通常用於演算法的設計和描述，它使得開發者能夠快速理解演算法的邏輯，而不受具體語言的限制。
4. 對演算法的高層次描述。
#### 流程圖（Flowchart）
1. 定義：流程圖是一種用視覺圖形表示演算法或系統流程的圖表。它使用不同的圖形符號（如矩形、菱形、箭頭等）表示不同的操作和流程。
2. 特點：流程圖提供了一種直觀的方式，用於展示演算法或流程中不同步驟之間的邏輯和控制流。
3. 用途：流程圖通常用於分析、設計和說明演算法或系統的運行邏輯。它有助於團隊成員理解整個過程。
4. 以視覺化的方式展現演算法或系統的流程。
## 【self practice】
```python
# bubble
# 一種常見的排序算法
def bubble_sort(arr):
n = len(arr)
for i in range(n): # 遍歷所有陣列元素
for j in range(0, n-i-1): # 最後i個元素已經在正確的位置，不需要再比較
if arr[j] > arr[j+1]: # 如果元素大於下一個元素，則交換它們
arr[j], arr[j+1] = arr[j+1], arr[j]
# 示範用法
if __name__ == "__main__":
array_to_sort = [64, 34, 25, 12, 22, 11, 90] # 測試資料
bubble_sort(array_to_sort) # 呼叫冒泡排序函數
print("排序後的陣列:", array_to_sort) # 輸出排序後的陣列
```
排序後的陣列: [11, 12, 22, 25, 34, 64, 90]
Sign in with Wallet
Connect another wallet