# wk13_1130
wk13_1130 演算法_排序與搜尋
ch08_演算法_排序與搜尋
8.1 認識演算法
8.2 排序
1. 泡沫排序
2. 追蹤泡沫排序過程
8.3 搜尋
1. 循序搜尋
2. 二分搜尋
{綜合演練}
實作2 :
俊民將中獎號碼建立成串列num=[67,12,9,52,91,3]，
讓妹妹輸入三個號碼，再以循序搜尋方法檢查這三個號碼種有幾個中獎，
並顯示其結果。
實作3:
下列名單為本期大樂透的中獎名單name=['David','Lily','Chiou','Bear','Shantel','Chynthia']，
讓使用者輸入一個姓名，輸入的字元大小寫不分，
例如輸入 david、David、DAVID都是同一人，
請以二分搜尋法檢查該名單是否中獎，
並顯示查詢結果。
{範例}
1. 由小排到大排序 \
2. 追蹤泡沫排序法的過程 \
3. 中獎者姓名(循序搜尋) \
4. 二分搜尋 : 中獎者姓名 \

In [22]:
def switch(i):
datas[i],datas[i+1]=datas[i+1],datas[i]
datas=[31,20,10,5]
print(f"排序前:{datas}")
n=len(datas)
for i in range(0,n-1):
for j in range(0,n-1-i):
print(f"i={i},j={j}")
if datas[j]> datas[j+1]:
switch(j)
print(f"{datas[j]},{datas[j+1]}互換後:{datas}")
print(f"排序後:{datas}")
排序前:[31, 20, 10, 5]
i=0,j=0
20,31互換後:[20, 31, 10, 5]
i=0,j=1
10,31互換後:[20, 10, 31, 5]
i=0,j=2
5,31互換後:[20, 10, 5, 31]
i=1,j=0
10,20互換後:[10, 20, 5, 31]
i=1,j=1
5,20互換後:[10, 5, 20, 31]
i=2,j=0
5,10互換後:[5, 10, 20, 31]
排序後:[5, 10, 20, 31]
In [21]:
datas=[3,20,10,5]
print(f"排序前:{datas}")
print(f"排序後:{datas}")
排序前:[3, 20, 10, 5]
排序後:[3, 20, 10, 5]
In [8]:
print(datas[0],datas[1])
x=datas[0]
datas[0]=datas[1]
datas[1]=x
print(datas)
3 20
[20, 3, 10, 5]
In [ ]:
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)")
aqns=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)
【afterclass practice】
1. 綜合演練 選擇題1-10 (需抄題在markdown cell ; 有程式碼的題目要有code cell )
2. 名詞解釋 : 演算法、虛擬碼、流程圖
( 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 ]

In [4]:
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

In [3]:
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)以上皆非

( D ) 9. 同第 8 題，中獎者的姓名為？

(A)錢來多 (B)曾溫柔 (C)鄭美麗 (D)無此中獎號碼！

( B ) 10. 同第 8 題，這個程式是？

(A)二分搜尋 (B)循序搜尋 (C)泡沫搜尋 (D)以上皆非

In [2]:
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次