{%hackmd @themes/orangeheart %}
## wk13_1130_CH8演算法,排序與搜尋
### 醫放三 B1003210 應雨岑
1. 8.1 認識演算法
2. 8.2 排序
- 泡沫排序
- 追蹤泡沫排序過程
3. 8.3 搜尋
- 循序搜尋
- 二分搜尋
4. 專案
## 今日課程內容
<pre>
1. 認識演算法--解決問題的方法
2. 泡沫排序--為一個個比較大小而放入對應的位置
3. 維基網站查詢
</pre>
## NOTE
<pre>
認識演算法--解決問題的方法
泡沫排序--為一個個比較大小而放入對應的位置
url=requests.get("https://zh.wikipedia.org/wiki/Special:Random") #打開隨機的WIKI網頁
</pre>

## [ INCLASS PRACTICE ]

#由小排到大排序 \<bubble>
def switch(i):
    datas[i],datas[i+1]=datas[i+1],datas[i]

datas=[3,5,2,1]
print("排序前",datas)
n=len(datas)
for i in range(0,n):
    for j in range(0,n-1):
        print(f"i={i},j={j}")
        if datas[j]>datas[j+1]:
            print(f"{datas[j]} {datas[j+1]}, 互換後",end=" ")
            switch(j)
        print(datas)
            
print("排序後",datas,end=" ")

排序前 [3, 5, 2, 1]
i=0,j=0
[3, 5, 2, 1]
i=0,j=1
5 2, 互換後 [3, 2, 5, 1]
i=0,j=2
5 1, 互換後 [3, 2, 1, 5]
i=1,j=0
3 2, 互換後 [2, 3, 1, 5]
i=1,j=1
3 1, 互換後 [2, 1, 3, 5]
i=1,j=2
[2, 1, 3, 5]
i=2,j=0
2 1, 互換後 [1, 2, 3, 5]
i=2,j=1
[1, 2, 3, 5]
i=2,j=2
[1, 2, 3, 5]
i=3,j=0
[1, 2, 3, 5]
i=3,j=1
[1, 2, 3, 5]
i=3,j=2
[1, 2, 3, 5]
排序後 [1, 2, 3, 5]

! pip install requests beautifulSoup4

Requirement already satisfied: requests in c:\users\user\anaconda3\lib\site-packages (2.31.0)
Requirement already satisfied: beautifulSoup4 in c:\users\user\anaconda3\lib\site-packages (4.12.2)
Requirement already satisfied: charset-normalizer<4,>=2 in c:\users\user\anaconda3\lib\site-packages (from requests) (2.0.4)
Requirement already satisfied: idna<4,>=2.5 in c:\users\user\anaconda3\lib\site-packages (from requests) (3.4)
Requirement already satisfied: urllib3<3,>=1.21.1 in c:\users\user\anaconda3\lib\site-packages (from requests) (1.26.16)
Requirement already satisfied: certifi>=2017.4.17 in c:\users\user\anaconda3\lib\site-packages (from requests) (2023.7.22)
Requirement already satisfied: soupsieve>1.2 in c:\users\user\anaconda3\lib\site-packages (from beautifulSoup4) (2.4)

import requests  #跟維基百科送出請求要抓資料
from bs4 import BeautifulSoup  #取得內容
import webbrowser   #開啟一個新分頁

while True:
    url=requests.get("https://zh.wikipedia.org/wiki/Special:Random")  #打開隨機的WIKI網頁
    soup=BeautifulSoup(url.content,"html.parser")
    title=soup.find(class_="firstHeading").text
    
    print(f"{title}\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

常琬
想要看這篇文章嗎?
n
Try Again
威斯特摩兰站
想要看這篇文章嗎?
y

## 全部的note
<pre>

W1
計算符號之間可以加空白鍵 <br>
** : 幾次方<br>
sep="." : 分隔符號為.
end="/" : 結束用/結束

在print內寫入%d : 放入參數答案 (最後在答案要加%)
%s : 放入的答案為字串
%f : 放入的答案包含全部小數點
%.1f : 包含 1位小數點
%.3f : 包含 3位小數點
寫法如下- print("身高為%d cm，體重為%d kg，BMI為%.1f " % (height,weight,bmi))

print("顯示的文字",參數名字)<br>
my_height = input("請輸入身高(cm)") : 可以輸入文字進去對話框
使用者輸入的文字要轉換成"int" ()<br>

W2
print("姓名 成績")
print("%3s %3d"%(name1,score1)) #按照字元數進行規則排列出一格表格格式

W3
**次方
//整除的數
/除以
%餘數
and 放在兩個運算子中間，判斷True or False，當兩個都為True才會是True
or 放在兩個運算子中間，判斷True or False，當兩個都為False才會是False

W4
if,else,elif需使用冒號:還有縮排來寫code
.upper可以讓程式不用判斷大小寫

W5
串列list用中括弧括起來
for和其他語法一樣，他同樣也是需要用到:還有縮排來寫程式

W6
break會跳出這個迴圈
continue跳出執行這個code 繼續執行下一個i的程式
None 為一個什麼都沒有的數字，但是他可以做加減乘除的運算

W7
串列名稱=[1,2,3,...] #可以放字串、數字等等的
另外也可以宣告空的串列list=[]
多為變數的宣告
list=[["1"],["1,2"],["1,2,3"]]
如果想要顯示第二個串列的第一個內容:print(list[1][0]))
# 0表示第一個資料，1表示第二個-意思是程式計算的方式是由0開始數
若想檢索特定的元素可以使用list[起始索引,終止索引,間隔]的方式進行
也可以索引-值，表示從最後一個開始數list[-1]
len(list)可以計算元素數量
max(list)可以找到元素內最大值
list.index(...)可以找...在清單中第幾個
.count 可以數...出現幾次
.append 插入一個元素在最後
.insert(3,8)插入8某一個位置(第三個)
.pop 移除最後一個元素

W8
divmod(7,3) #答案為(2,1) 表示(商,餘數)
元組內的元素不能修改，但可以轉換成串列
字典是以大括號呈現{}
由小排到大 score.sort()
由大排到小 score.sort(reverse=True)
反轉是錯誤的則不用反轉，由小排到大 score.sort(reverse=False)

W9
字典語法 dict_血型個性={"A":"穩重","B":"樂觀","O":"堅強","AB":"自然"}

W10
下載code的md檔案--用於期末的hackMd筆記
自訂一個函式 def sayhello():
呼叫這個sayhello程式 sayhello()
沒有設預設值 def sayhello2(name): #不會出現東西，因為沒有寫預設是什麼
有設定預設值 def sayhello2(name= "my friend"): #沒有特別寫name是什麼，就會使用預設值
如果有一個參數有設預設值另一個沒設，則有設預設值的函數就要放在靠後面
在函式def內設的參數var1=1都是區域變數，如果跳出這個函式後就不存在這個設定，因此如要變成全域函數要用 global var1 \n var1=1

W11
函式模組重點: def,return
只要模組裡面有程式區塊就需要使用return
把time的模組匯成t --> import time as t
匯入time裡面的其他模組，因此在使用時就不需要寫成time.sleep而可直接寫sleep -->from time import sleep,ctime
在python中安裝程式的方法(安裝numpy) --> ! pip install numpy

W12
join 函式可將串列中元素連接組成一個字串
r.sample("123456789",4) #1-9數字當中隨機選4個數字
while True: #對就會一直執行
</pre>

## [ afterclass practice ]

> 1. 綜合演練 選擇題1-10 (需抄題在markdown cell ; 有程式碼的題目要有code cell )
> 2. 名詞解釋 : 演算法、虛擬碼、流程圖
* 綜合演練
### ( C ) 1. 執行下列程式，下列結果何者正確？
<pre>
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)
</pre>
(A) [3,5,2,1] (B) [ 5,3,2,1] (C) [1,2,3,5] (D) [3,5,1,2 ]

#### 因為這個是泡沫排序的方法，可以逐一比較兩者資料，已完成排序工作

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. 執行下列程式，下列顯示結果何者正確？
<pre>
num=[67,12,9,52,91,3]
no=52
for i in range(len(num)):
if (num[i]==no):
break
print(i)
</pre>
(A) 52 (B) i (C) no (D) 3

#### 因為當num內的元素為no(52)時，程式就會停止跑迴圈而印下i值，因為52在序列第3個位置，則i=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) 以上皆是

#### 因為二分搜尋法是先將串列資料排序好在以中央串列元素將串列分成2半，再去比較必較大還是比較小

### ( A ) 4. 有 10000 筆資料時，使用循序搜尋最少需多少次？

(A) 1 (B) 10000 (C) 15 (D) 14

#### 1次，因為有可能第一次就搜尋到了

### ( B ) 5. 有 10000 筆資料時，使用循序搜尋最多需多少次？

(A) 1 (B) 10000 (C) 15 (D) 14

#### 10000次，因為有可能最後一次才搜尋到

### ( D ) 6. 有 10000 筆資料時，使用二分搜尋最多需多少次？

(A) 1 (B) 10000 (C) 15 (D) 14

#### 因為10000-5000-2500-1250-625-...，2^13<10000<2^14，因此搜尋次數最多為14次

### ( A ) 7. 下列那一種搜尋方法效率最好？

(A)二分搜尋 (B)循序搜尋 (C)泡沫搜尋 (D)三者效率相同

#### 因為二分搜尋可以提升速度，雖然城市比較複雜需要先進行排序

### ( D ) 8. 執行下列程式，下列結果何者正確？
<pre>
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))
</pre>
(A) no = 256 (B) IsFound=True (C)共比對 9 次 (D)以上皆非

#### 因為總共比對的次數為8次，no = 100，IsFound=False

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)無此中獎號碼！

#### 因為沒有人中獎，因此程式會跑到最下面的else區段，而印出無此中獎號碼！

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次

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

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

#### 因為他是從第0個元素開始檢查比對，當有成功比對到才會結束，若無，就會比到最後一個，因此為循序搜尋

* ## 名詞解釋 : 演算法、虛擬碼、流程圖
1. 演算法
- 是為了解決一個問題所要採取的方法和步驟
2. 虛擬碼
- 先講演算法用虛擬法的方式呈現，再轉換成特定語言，可幫助我們更好的寫出程式
3. 流程圖
- 如果遇到比較難的問題時，除了用虛擬碼，也會畫製流程圖

## [ self practice ]
* 泡沫排序

"""利用泡沫排序法，在輸入N組數字後將其由大排到小"""
list=[]

while True:
    a= input("請輸入數字，若按enter則表結束")
    if a!="":
        list.append(a)
    else:
        break
print("排序前",list)
l=len(list)
for i in range(l):
    for j in range(l-1):
        if list[j]<list[j+1]:
            list[j],list[j+1]=list[j+1],list[j]
print("數字由大排到小",end=" ")
for i in range(l):
    print(list[i],end=" ")

請輸入數字，若按enter則表結束78
請輸入數字，若按enter則表結束92
請輸入數字，若按enter則表結束53
請輸入數字，若按enter則表結束82
請輸入數字，若按enter則表結束45
請輸入數字，若按enter則表結束
排序前 ['78', '92', '53', '82', '45']
數字由大排到小 92 82 78 53 45