# wk13_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,20,10,54,65465,5,52,5,654]
print(f"排序前:{datas}")
n=len(datas)
for i in range(0,n-1):
for j in range(0,n-i-1):
print(f"i={i}, j={j}")
if(datas[j]>datas[j+1]):
switch(j)
print(f"{datas[j+1]}, {datas[j]}互換後: {datas}")
print(f"排序後:{datas}")
```
排序前:[3, 20, 10, 54, 65465, 5, 52, 5, 654]
i=0, j=0
i=0, j=1
20, 10互換後: [3, 10, 20, 54, 65465, 5, 52, 5, 654]
i=0, j=2
i=0, j=3
i=0, j=4
65465, 5互換後: [3, 10, 20, 54, 5, 65465, 52, 5, 654]
i=0, j=5
65465, 52互換後: [3, 10, 20, 54, 5, 52, 65465, 5, 654]
i=0, j=6
65465, 5互換後: [3, 10, 20, 54, 5, 52, 5, 65465, 654]
i=0, j=7
65465, 654互換後: [3, 10, 20, 54, 5, 52, 5, 654, 65465]
i=1, j=0
i=1, j=1
i=1, j=2
i=1, j=3
54, 5互換後: [3, 10, 20, 5, 54, 52, 5, 654, 65465]
i=1, j=4
54, 52互換後: [3, 10, 20, 5, 52, 54, 5, 654, 65465]
i=1, j=5
54, 5互換後: [3, 10, 20, 5, 52, 5, 54, 654, 65465]
i=1, j=6
i=2, j=0
i=2, j=1
i=2, j=2
20, 5互換後: [3, 10, 5, 20, 52, 5, 54, 654, 65465]
i=2, j=3
i=2, j=4
52, 5互換後: [3, 10, 5, 20, 5, 52, 54, 654, 65465]
i=2, j=5
i=3, j=0
i=3, j=1
10, 5互換後: [3, 5, 10, 20, 5, 52, 54, 654, 65465]
i=3, j=2
i=3, j=3
20, 5互換後: [3, 5, 10, 5, 20, 52, 54, 654, 65465]
i=3, j=4
i=4, j=0
i=4, j=1
i=4, j=2
10, 5互換後: [3, 5, 5, 10, 20, 52, 54, 654, 65465]
i=4, j=3
i=5, j=0
i=5, j=1
i=5, j=2
i=6, j=0
i=6, j=1
i=7, j=0
排序後:[3, 5, 5, 10, 20, 52, 54, 654, 65465]
```python
print(datas[0],datas[1])
datas[0],datas[1]=datas[1],datas[0]
print(datas)
```
3 20
[20, 3, 10, 5]
## 【afterclass practice】
綜合演練 選擇題1-10 (需抄題在markdown cell ; 有程式碼的題目要有code cell )
名詞解釋 : 演算法、虛擬碼、流程圖
### 實作2 :
俊民將中獎號碼建立成串列num=[67,12,9,52,91,3]，讓妹妹輸入三個號碼，再以循序搜尋方法檢查這三個號碼種有幾個中獎，並顯示其結果。
```python
def jackpot(a,b,c,d):
if(a==d or b==d or c==d):
return 1
else:
return 0
num=[67,12,9,52,91,3]
a=int(input("輸入第一個號(只可為正整數): "))
b=int(input("輸入第二個號(只可為正整數): "))
c=int(input("輸入第三個號(只可為正整數): "))
d=0
for i in range(0,len(num)):
d+=jackpot(a,b,c,num[i])
print(f"共有{d}個號碼中獎!")
```
輸入第一個號(只可為正整數): 3
輸入第二個號(只可為正整數): 91
輸入第三個號(只可為正整數): 2
共有2個號碼中獎!
### 實作3:
下列名單為本期大樂透的中獎名單name=['David','Lily','Chiou','Bear','Shantel','Chynthia']，讓使用者輸入一個姓名，輸入的字元大小寫不分，例如輸入 david、David、DAVID都是同一人，請以二分搜尋法檢查該名單是否中獎，並顯示查詢結果。
```python
def f(a):
if(a<2):
if(a%1!=0):
a-=0.5
if(a%1!=0):
a+=0.5
a=int(a)
return a
def switch(i):
name[i],name[i+1]=name[i+1],name[i]
name=['David','Lily','Chiou','Bear','Shantel','Chynthia']
for i in range(0,len(name)-1):
for j in range(0,len(name)-i-1):
if(len(name[j])>len(name[j+1])):
switch(j)
a=input("請輸入人名(大小寫都可): ")
b=0
maxi=len(name)-1
mini=0
mid=int((maxi+mini)/2)
while(a.lower()!=name[mid].lower()):
mid=f((maxi+mini)/2)
if(len(a)>len(name[mid])):
mini=mid
else:
maxi=mid
if(maxi==mini):
if(a.lower()!=name[mini].lower()):
print("查無此人")
break
if(maxi==mini+1):
b+=1
if(b==3):
print("查無此人")
break
if(a.lower()==name[mid].lower()):
print("恭喜",name[mid],"有中獎!!!")
```
請輸入人名(大小寫都可): cHynTHia
恭喜 Chynthia 有中獎!!!
( C ) 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 ]
```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]
( D ) 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
```python
num=[67,12,9,52,91,3]
no=52
for i in range(len(num)):
if (num[i]==no):
break
print(i)
```
3
( B ) 3. 下列那一個排序法，在執行搜尋前必須先將資料排序？
(A) 循序搜尋法 (B) 二分搜尋法 (C) 泡沫搜尋法 (D) 以上皆是
( A ) 4. 有 10000 筆資料時，使用循序搜尋最少需多少次？
(A) 1 (B) 10000 (C) 15 (D) 14
( B ) 5. 有 10000 筆資料時，使用循序搜尋最多需多少次？
(A) 1 (B) 10000 (C) 15 (D) 14
( D ) 6. 有 10000 筆資料時，使用二分搜尋最多需多少次？
(A) 1 (B) 10000 (C) 15 (D) 14
( A ) 7. 下列那一種搜尋方法效率最好？
(A)二分搜尋 (B)循序搜尋 (C)泡沫搜尋 (D)三者效率相同
( D ) 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)無此中獎號碼！
( B ) 10. 同第 8 題，這個程式是？
(A)二分搜尋 (B)循序搜尋 (C)泡沫搜尋 (D)以上皆非
Sign in with Wallet
Connect another wallet