###### tags: `資訊科技`
# 程式設計(使用Python)
## 零、評分方式
1. 上課基本練習
2. 自學 (3選1)
- [Teach Python 3 and web design with 200+ exercises - Learn Python 3 - Snakify](https://snakify.org/en/) (解題數*2)
- [SoloLearn Python 3 Tutorial](https://www.sololearn.com/) (XP/4)
:lollipop: 全部學完可拿到[證書](https://i.imgur.com/0yAAPlB.jpg) 。
- [Joy of Code - VPhysics 前5課](http://coding.nutc.edu.tw/student/lessons/E/) (完成課數*20)
## 一、基本使用
1. ### 編輯軟體
- [Thonny](https://thonny.org/)
* 安裝套件： Tools/Manage plug-ins
- [Google Colaboratory](https://colab.research.google.com/)
* 學習歷程檔案筆記
* [用Markdown做筆記](http://moocs.nccu.edu.tw/media/17832)
- [repl.it](https://repl.it/)
- Jupyter Notebook
* [Anaconda](https://www.anaconda.com/)
- [Anaconda Spider](https://www.anaconda.com/)
- 學習歷程檔案
* 最後一週上課結束前如果認證完成，學期總成績加分。
* 檔案下載後(File / Download .ipynb)，以Jupyter Notebook打開，存成HTML檔(File／Download as / HTML)，再以[PDF24 Tools](https://tools.pdf24.org/zh/)轉成PDF。
* 如果要將PDF插入到Word中，可用同一網站將PDF轉圖像再插入。
2. ### 參考文件
- [官方文件](https://docs.python.org/3/)
- [Python3入門基礎教程](http://tw.gitbook.net/t/python3.html)
- [廖雪峰 Python 教程](https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000)
- [菜鳥教程 Python 3](http://www.runoob.com/python3/python3-tutorial.html)
- [資安深耕研習營 HappyPythonDay](https://github.com/MyDearGreatTeacher/HappyPythonDay)
- [Joy of Code - 用程式解數學問題(尤拉計畫)](http://coding.nutc.edu.tw/student/lessons/C/)
- [Python-基本範例(46 練習題)](http://kh-coding.blogspot.com/p/python-46.html)
- [Python 100例](http://www.runoob.com/python/python-100-examples.html)
- [Python 之旅](http://funhacks.net/explore-python/)
- [彭彭老師python入門教學課程](https://www.youtube.com/watch?v=wqRlKVRUV_k&list=PL-g0fdC5RMboYEyt6QS2iLb_1m7QcgfHk)
- [莫煩Python3基礎教程](https://morvanzhou.github.io/tutorials/python-basic/basic/)
3. ### 變數與資料型態
- 變數：存放資料的記憶體空間(名稱自訂)
- 數值型態：int(整數)、float(浮點數、小數)、bool(True、False)
- 字串型態：' ' 或 " " 中的文字
- 容器型態：
* list：有順序、可變動的資料集合
* tuple：有順序、不可變動的資料集合
* set：無順序的資料集合
* dict：鍵值對(key-value)的集合
- 資料型態轉換：int()、float()、str()
4. ### 輸入輸出
- 變數=input(\[提示字串\])
- print(項目1\[,項目2,...\])
* 字串要加 ' ' 或 " "
* 可用 + 將字串連接
- print('A=%d B=%d C=%d' %(A,B,C))
* [Python 3 print 函数用法总结](http://www.runoob.com/w3cnote/python3-print-func-b.html)
- print('A={} B={} C={}'.format(A, B, C))
* {} 的位置會被後方 format 所帶的參數所取代，預設會依照順序輸出。
* [Python Format String 字串格式化整理](https://blog.jaycetyle.com/2018/01/python-format-string/)
- print(f'A={A} B={B} C={C}')
* [f-string 是 Python 3.6 才有的方法](https://steam.oxxostudio.tw/category/python/basic/format.html#a3/)
:::info
EX_01：輸入三角形三邊長，以[海龍公式](http://www2.chsh.chc.edu.tw/bee/1050206/heron%20formula.pdf)求三角形面積。
:::
``` javascript=
a = input('請輸入邊長1:') # 輸入為字串型態
a = float(a) # 將a字串轉成浮點數存回a
b = ........
c = ........
s = ........
area = ........ # 開根號 **0.5
print('三角形面積為%10.2f' %area)
print('三角形面積為{:10.2f}'.format(area))
print(f'三角形面積為{area:10.2f}')
# %10.2f 固定印出10個字元(含小數點)，小數點固定印出2位
# a=5,b=6,c=7,area=14.70
```
<br />
## 二、運算子
1. ### 算數運算子
| 算數運算子 | 意義 | 備註|
|:-------- |:------ |:-------|
| + | 加 | |
| - | 減 | |
| * | 乘 | |
| / | 除 |17/5 為 3.4 |
| // | 取商數 |17//5 為 3 |
| % | 取餘數 |17%5 為 2 |
| ** | 次方 | 5**2 為 25 |
2. ### 關係運算子
| 關係運算子 | 意義 | 備註|
|:-------- |:------ |:-------|
| == | 等於 | =是指派，==才是判斷是否相等 |
| != | 不等於 ||
| > | 大於 ||
| >= | 大於等於 ||
| < | 小於 ||
| <= | 小於等於 ||
- x < y < z 為 合法條件
3. ### 邏輯運算子
| 邏輯運算子 | 意義 | 備註|
|:-------- |:-----|:---|
| and | 而且 ||
| or | 或者 ||
| not | 否 ||
4. ### 複合指定運算子
- i+=3 表示 i=i+3
<br />
## 三、選擇
1. ### if 條件式語法
``` javascript
if 條件:
條件「成立」時的程式碼
```
2. ### if~else 語法：
``` javascript
if 條件:
條件「成立」時的程式碼
else:
條件「不成立」時的程式碼
```
:mega: 以冒號及縮排(1個Tab或4個空白)來表示程式區塊。
:::info
EX_02：承EX_01，先判斷三邊長是否可以構成三角形。如果可以，求三角形面積；如果不行，輸出錯誤。
Tip：每邊長要大於0，且任兩邊之和要大於第三邊。
:::
``` javascript=
a = ........ input('請輸入邊長1:')
b = ........
c = ........
if a > 0 and ........ and a + b > c and ........ :
s = ........
area = ........ # 開根號 **0.5
print('三角形面積為%10.2f' %area)
else:
print('不能構成三角形')
# 程式執行完向使用者Say Goodbye
```
3. ### 巢狀 if 語法
``` javascript
if 條件1:
if 條件2:
條件1「成立」，且條件2「成立」時的程式碼
else:
條件1「成立」，且條件2「不成立」時的程式碼
else:
條件1「不成立」時程式碼
```
:mega: if或else內，都可再增加條件式。
:::info
EX_03：驗證登入帳號、密碼。
:::
``` javascript=
user = input('請輸入帳號：')
pwd = input('請輸入密碼：')
if ........ : # 帳號等於'admin' 而且 密碼等於'1234'，判斷是否相等「==」
print('Welcome')
else:
print('帳號或密碼輸入錯誤')
```
``` javascript=
user = input('請輸入帳號：')
pwd = input('請輸入密碼：')
if ........ :
print('Welcome')
else:
........ : # 不等於「!=」
print('帳號錯誤')
........ :
print('密碼錯誤')
# Q：帳號、密碼都錯時會顯示？如何顯示帳號錯誤，密碼錯誤？
```
4. ### 多重選擇 if~else if~else 語法
``` javascript
if 條件1:
條件1「成立」時程式碼區塊
elif 條件2:
條件1「不成立」，且條件2「成立」時的程式碼
elif 條件3:
條件1、2「不成立」，且條件3「成立」時的程式碼
....
else:
上述條件都「不成立」時的程式碼
```
:mega: elif 可視需要增加。
:::info
EX_04：將成績轉換成等級制。
80以上 A，70 ~ 80 B，60 ~ 70 C，60以下 D，其它「錯誤」。
:::
``` javascript=
score = int(input('請輸入成績：'))
if score >= 80:
print('A')
........ : # 70~80
........
........ : # 60~70
........
........ : # 0~60
........
else:
print('輸入錯誤！')
```
``` javascript=
score = int(input('請輸入成績：'))
if ........ # 成績大於100 或者 小於0
print('輸入錯誤！')
else:
if score >= 80:
print('A')
........ : # 70~80
........
........ : # 60~70
........
........ : # 0~60
........
```
:::info
EX_02~04 (Bonus)：輸入平面三角形的三個內角(假設均為正整數)，[判斷其為何種三角形](https://zh.wikipedia.org/wiki/%E4%B8%89%E8%A7%92%E5%BD%A2)。
Tip：先判斷是否為三角形(內角總和180度，且沒有一個角為180度)，再繼續判斷種類。
測試資料：30 60 90 直角三角形
92 44 44 鈍角三角形
60 60 60 銳角三角形
90 90 90 不是三角形
180 0 0 不是三角形
``` javascript=
a,b,c = map(int,input("請輸入三角形的三個內角(空白隔開)： ").split())
```
:::
<br />
## 四、迴圈
1. ### range 函式
- 串列變數=range(整數)
* 產生0~「整數-1」的串列
- 串列變數=range(起始值,終止值)
* 產生起始值~「終止值-1」的串列
- 串列變數=range(起始值,終止值,間隔值)
* 產生：起始值, 起始值+間隔值, 起始值+間隔值*2, ...
:mega: [Python range() 函数用法](http://www.runoob.com/python/python-func-range.html)
2. ### for 迴圈語法
``` javascript
for 變數 in range(重複次數):
程式碼
```
``` javascript
for 變數 in 串列:
程式碼
```
``` javascript
for 變數 in 字典: # 變數會儲存字典的key
程式碼
```
``` javascript
break：強制跳出「整個」迴圈
continue：強制跳出「此次」 迴圈，繼續進入下一次圈
```
``` javascript
for 變數 in 串列或字串:
程式碼
else:
迴圈正常結束，執行此區塊程式碼。(break不會執行)
```
:::info
EX_05_1：印出10~50的偶數。
:::
``` javascript=
for i in range(...., ...., ....):
print(...., end=' ')
```
:::info
EX_05_2：計算1+2+...+n。
:::
``` javascript=
n = ....(input('請輸入正整數：'))
sum = ........ # sum初值設為0
for ........ : # 讓 i 從 1~n
........ # 每次迴圈 sum=sum+i
print('1 到 {} 的整數和為 .... '.format(n, ....)) # 只需輸出一次
Q：將程式改為計算n!
```
3. ### 巢狀迴圈語法
``` javascript
for 變數1 in range(重複次數):
for 變數2 in range(重複次數):
程式碼
```
:::info
EX_06：畫出一個螺旋正方形後，更改i的範圍，每次畫的長度，轉的角度，畫出一個你覺得最炫的圖形。
:::
``` javascript=
import turtle
# turtle.speed(0) 讓海龜暴走
# turtle.delay(0)
........ : # 畫200次
turtle.forward(2*i) # 試試改變長度為i、4*i或其它
turtle.right(90) # 試試改變角度為91、100、151或其它
turtle.done()
turtle.bye()
# 100000 0.001*i i**2
# 100000 0.0002*i i**0.94
# 10**1000 80%(3**i) 15*i%(7.874**i)
# 2020 100*math.sin(i) 50*i*i*i
# 8000 0.00228*i i**4
# 10000 0.01*i+i**0.1 1+2*i+3*i**2+4*i**3
# 10000 i/800 math.atan(i)*10+i**2
```
:mega: Colab 上使用 Turtle
``` javascript=
!pip3 install ColabTurtle
```
``` javascript=
from ColabTurtle.Turtle import *
initializeTurtle()
# speed(10) 讓海龜暴走
........ : # 畫200次
forward(2*i) # 試試改變長度為i、4*i或其它
right(90) # 試試改變角度為91、100、151或其它
```
:::info
EX_07_1：貝殼紋(先畫出一個正方形)。
:::
``` javascript=
import turtle
num = 60 # 正方形數量
len = 180 # 線條長度
dec = 3 # 下一個正方形邊長減少長度
....... : # 1個正方形4條線
........ # 往前畫出線條長度
........ # 右轉90度
turtle.done()
turtle.bye()
```
:::info
EX_07_2：貝殼紋。
:::
``` javascript==
import turtle
iNum = 60 # 正方形數量
jNum = 4 # 正方形有四個邊
len = 180 # 線條長度
angle = 90 # 每次轉90度
more = 10 # 下一個正方形多轉10度
dec = 3 # 下一個正方形邊長減少長度
........ # 先轉10度
for ........ : # 正方形數量
for ........ : # 1個正方形4條線
turtle.forward(len)
turtle.right(angle)
........ # 下一個正方形多轉10度
........ # 下一個正方形長度少dec
turtle.done()
turtle.bye()
# 900 4 180 90 60 0.1
# 525 4 500 90 1.618 10
# 180 3 360 120 61 2
# 1000 4 100 60 30 1
# 40 36 20 10 10 0 # HomePod mini
```
3. ### while 迴圈語法
``` javascript
while 條件判斷: # 條件為「真」的時候繼續執行
程式碼
```
:::info
EX_08：while 存錢買手機。
:::
``` javascript
i = 1
........ # sum 初值為 0
while ........ : # 存款金額小於 25000
money = int(input('請輸入第 ' + str(i) + ' 個月的存款： '))
........ # 把 money 加到 sum
........ # i+1
print('存了 {} 個月，總共 {} '.format(i-1, sum))
```
:::info
EX_09：小算盤開根號。
:::
``` javascript=
sol = False
n = int(input('請輸入正整數：'))
for ........ : # 只需檢測到 n/2，//取商
if ........ : # 如果i的平方等於n
print(i)
........ # sol設為True，表示找到根
........ # 跳出迴圈
if ........ : # 沒有解 (not)
print('只能求完全平方數的平方根！')
Q：4不行？
```
:::info
EX_10：小算盤開根號(以二分搜尋法實作)。
P.S. [科學記號表示法](https://chusiang.gitbooks.io/using-python/Numbers.html)
:::
:mega: [常用運算子的優先順序](https://itw01.com/V2HWOE4.html)
``` javascript=
n = int(input('請輸入正整數：'))
lower, upper = 1, n-1
# Q2
while ........ : # 上下界限的差 > 10^-15(數學寫法)，就繼續逼進
mid = ........ # mid 為上下界限的中間
# Q2
if mid**2 > n: # 如果中間數的平方 > n，解在lower~mid間
........ # 將上限調為 mid
elif ........ : # 如果中間數的平方 < n，解在mid~upper間
........ # 將下限調為 mid
else:
break
print(mid)
Q1：2不行？
Q2：新增一個變數cnt，記錄總共做了幾次運算得解
print('經過了 {} 次運算，根號 {} 為 {} ' ........ )
```
:::info
EX_10 (Bonus)：小算盤開根號([以牛頓法實作](http://mathcenter.ck.tp.edu.tw/Resources/Ctrl/ePaper/ePaperOpenFileX.ashx?autoKey=55))。
<br />
```javascript=
n = int(input('請輸入正整數：'))
cnt = 0
........ # 取任一點為 a
while ........ : # 當b*b和n的誤差>1e-13時，繼續逼進
........ # 挑出的第1個近似值a之後，作一切線，切線和x軸的交點為b
........ # 下一次以此次的b繼續求切線和x軸的交點
cnt+=1
print('經過了 {} 次運算，根號 {} 為 {} '.format(cnt, n, a))
```
[:grimacing: 偷看解答](http://cs.cysh.cy.edu.tw/computer_concept_108/sqrt_newton.html)
:::
<br />
## 五、複合式資料型態
1. ### [list(串列)](https://www.twblogs.net/a/5cd7d860bd9eee67a77f8884)
- 串列變數 = [ 元素1, 元素2, .... ]
* 類似「陣列」，但元素可以是不同型態。
* lst = [1, 2, 3, 4, 5]
- 列表對「+」和「$*$」的操作與字串相似。「+」用予組合列表，「$*$」用於重複列表。
| 串列運算 | 範列 |
|:-------- |:-------------- |
| + |[1, 2]+[3, 4]為[1, 2, 3, 4]|
| $*$ |[1, 2]*3為[1, 2, 1, 2, 1, 2]|
| x in lst |判斷x是否在串列, 3 in [1, 2, 3]為True |
| == |判斷兩串列是否相等, [1, 2]==[1, 2, 3]為False|
- 運用 [] 取值，可以使用 index(索引值從0開始)、slice 來存取陣列裡的資料。假設lst,lst2為串列變數，常用的運算和方法如下表
| slice運算 | 意義 |
|:------------ |:-------------- |
| lst[i] | 取出索引值i的元素 |
| lst[-1] | 取出最後一個元素 |
| lst[i:j] | 取出索引值i~j-1的元素 |
| lst[i:j:k] | 取出索引值i~j-1的，間隔為k的元素 |
| lst[i:j]=lst2| 把索引值i~j-1的元素換成lst2的元素 |
| del lst[i:j] | 刪除索引值i~j-1的元素 |
| 串列函式 | 意義 |
|:------------ |:-------------- |
| lst=list() 或 lst=[] |宣告空的串列|
| len(lst) | 回傳串列個數 |
| max(lst) | 回傳串列中的最大值 |
| min(lst) | 回傳串列中的最小值 |
| list('abc') | 將'abc'拆成'a','b','c'加入串列 |
| 串列方法(函式) | 意義 |
|:---------------|:-------------- |
| lst.append(x) | 將x附加到串列後面 |
| lst.insert(i,x)| 將x插入到索引值i的位置 |
| lst.extend(x) | 將串列x中的所有元素，附加到串列後面|
| lst.remove(x) | 刪除串列中的第一個x |
| lst.pop(i) | 回傳索引值i的元素，並將其刪除。如果沒有i，則傳回最後一個元素並刪除 |
| lst.index(x) | 回傳第一次出現x的索引值 |
| lst.count(x) | 計算出現x的次數 |
| lst.sort() | 將串列中的元素小->大排序，大->小則加入參數reverse=True |
| lst.reverse() | 將串列中的元素反轉 |
| lst2=lst.copy()| copy串列 |
| lst.clear() | 清除串列內所有元素 |
- 多維list
* 直接建立
``` javascript
lst = [ [1, 2, 3], [4, 5, 6] ]
```
* 使用[列表生成式(List Comprehensions)](https://www.liaoxuefeng.com/wiki/1016959663602400/1017317609699776)建立， 類似數學集合的表示法
$\{ 2n+1 \mid n \in \{0, 1, 2, 3, 4\} \} \rightarrow \{1,3,5,7,9\}$
``` javascript
lst = [2*n+1 for n in range(5)]
```
``` javascript
a=[1,2,3,4,6,7,13,21]
lst = [ n for n in a if n%2==0] # lst=[2, 4, 6]
lst = [ [0 for i in range(3)] for j in range(2) ] # lst=[[0, 0, 0], [0, 0, 0]]
```
* 使用numpy模組建立
``` javascript
import numpy as np
lst = np.zeros((2, 3), dtype=np.int)
```
- =、copy()、deepcopy()的區別
* = 只是建立指標指向原串列。
* 使用a.copy()可以得到一個新的串列，但如果串列中含有串列，只有使用copy.deepcopy(a)才是完全複製。
``` javascript=
a=[1, 2, 3]
b=a
b[0]=555
print(a, b) # a=[555, 2, 3] b=[555, 2, 3]
# id(a)
# id(b)
a=[1, 2, 3]
c=a.copy()
c[0]=555
print(a, c) # a=[1, 2, 3] c=[555, 2, 3]
a=[1, 2, [3, 4]]
c=a.copy()
c[2][0]=555
print(a,c) # a=[1, 2, [555, 4]] c=[1, 2, [555, 4]]
import copy
a=[1, 2, [3, 4]]
d=copy.deepcopy(a)
d[2][0]=555
print(a, d) # a=[1, 2, [3, 4]] d=[1, 2, [555, 4]]
```
2. ### tuple(元組)
- 元組變數 = ( 元素1, 元素2, .... )
- 類似 list，但元素個數及元素值不能改變，執行效能較好。
- 列表使用 []，而元組使用 ()。
- 元組內的元素不可被新增、刪除，但可以重新定義整個元組的資料。
``` python
ct = ('台北', '台中', '高雄')
print(ct)
ct = ('台北市', '台中市', '高雄市')
print(ct)
```
- 元組可與串列互換
``` python
ct＿lst = ["台北", "台中", "高雄"]
ct_tpl = tuple(ct_lst)
print(ct_tpl)
ct_tpl = ("台北市", "台中市", "高雄市")
ct_lst = list(ct_tpl)
print(ct_lst)
```
3. ### set(集合)
- 集合變數 = { 元素1, 元素2, .... }
* 串列: []
元組: ()
集合: {}
- 在set裡面存放的是一群無順序且唯一的元素，可以是不同的型態。
``` javascript
lst1 = [ 1, 2, 3, 1, 2, 3 ]
st = set(lst1) # { 1, 2, 3 }
lst2 = list(st) # [ 1, 2, 3 ]
```
- 集合沒有索引值，集合不能用索引(index)與切片(slicing)取得內含的資料。
- 假設s、t為集合變數，常用的方法如下表
| 集合方法(函式) | 意義 |
|:--------------------|:---------- |
| s=set() | 建立空的集合 |
| s.add(x) | 將x加入集合 |
| s.update(lst) | 將lst內的元素加入集合s |
| s.discard(x) | 將x自集合中刪除，x不存在不會報錯 |
| s.remove(x) | 將x自集合中刪除，x不存在會報錯 |
| s.clear() | 將集合清空 |
| len(s) | 回傳集合的元素數量 |
| x in s | x 是否在集合 |
| x not in s | x 是否不在集合|
| s.issubset(t) | s 是否為 t 子集|
| s.issuperset(t) | s 是否包含 t|
| s.intersection(t) |交集 & |
| s.union(t) |聯集 \| |
| s.difference(t) |差集 - |
4. ### dict(字典)
- 字典變數 = { 鍵1:值1, 鍵2:值3, .... }
``` javascript
color = { 'red': [255, 0, 0], 'green': [0, 255, 0], 'blue': [0, 0, 255] }
dt = { 'a': 1, 'b': 98, 'c': 99 }
dt['a'] = 97 # 修改
dt['d'] = 100 # 新增
```
- dict(字典)類似C++ map，儲存的資料為「key(鍵)」與「value(值)」，可以快速取出對應值。
- 字典的操作與串列大同小異，最大的差別在於串列透過數字索引值，字典為鍵值。
- dict(字典)資料沒有順序的觀念，list(串列)用於儲存有順序性的資料。
- 假設dt、dt2為字典變數，key為鍵，val為值，常用的方法如下表
| 字典方法(函式) | 意義 |
|:-------------|:------------ |
| dt=dict() 或 dt={} |宣告空的字典|
| dt.clear() | 清除字典所有內容 |
| dt.fromkeys(lst[, val]) | 建立新字典，以lst序列中的元素為鍵，val為所有鍵對應的初始值|
| dt.get(key) | 透過key取得相對應的val |
| del dt['key']| 刪除鍵為'key'的元素 |
| 'key' in dt | 判斷key是否存在於dt |
| dt.keys() | 取得所有鍵 |
| dt.values() | 取得所有值 |
| dt.items() | 取得所有鍵值對，將(key,val)組成一個tuple |
| dt.update(dt2)| 使用 dt2 的值去更新 dt 內相同鍵的值|
| len(dt) | 回傳字典的元素數量|
:::info
EX_11_1：大樂透電腦選號。
:::
``` javascript=
import random as rnd
rnd.seed() # rnd.seed(2)會重複
........ # 建立一個空串列
for i in range(6):
num. ........ (rnd.randint(1, 49)) # 隨機產生1~49的整數放入串列
........: # 用for迴圈把串列中的數字印出
print(n, end=' ') # for i in range(6):
# print(num[i],end=' ')
```
:::info
EX_11_2：大樂透電腦選號(解決數字重複的問題)。
:::
``` javascript=
import random as rnd
rnd.seed(2)
........ # 建立一個空的集合
while ........ : # 集合長度 < 6
s. ........(rnd.randint(1, 49)) # 集合的元素不會重複
'''
while ........ : # 串列長度 < 6
r=rnd.randint(1,49)
if ........ : # r不在串列中
num.append(r)
'''
print('大樂透中獎號碼：', s)
```
:::info
EX_11_3：大樂透電腦選號(將數字排序顯示)。
:::
``` javascript=
import random as rnd
rnd.seed()
s = set() # 建立一個空的集合
while len(s) < 6: # 集合長度 < 6
s.add(rnd.randint(1, 49)) # 集合的元素不會重複
........ # 用集合的元素建立一個串列
........ # 用sort方法，將串列中的元素排序
print('大樂透中獎號碼：', ....)
```
:::info
EX_11_4：以bubble sort 實作 num.sort()。
:mega: 其它排序演算法
(1) [插入排序法(Insertion Sort)](https://jason-chen-1992.weebly.com/home/-insertion-shell-sort)、[選擇排序(Selection Sort)](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E5%85%A5%E9%96%80-%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F%E8%88%87%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-23d4bc7085ff)
(2) [Sorting Algorithms Animations](https://www.toptal.com/developers/sorting-algorithms)
:::
``` javascript=
# 以rnd.seed(0) 測試
........ : # 6個數字排序只需5個循環
........ : # 每次比較索引值 0 1、 1 2、 2 3、 3 4、 4 5的數字
if num[....] > num[....]: # 如果左邊比右邊大
........ # num[j]和num[j+1]交換。num[j], num[j+1] = num[j+1], num[j]
........
........
```
:::info
EX_12：求學測總級分和平均。
:::
``` javascript=
score = [[12,13,15,10,12,0,0],[15,13,15,15,14,0,0],[14,14,12,15,13,0,0],[11,10,12,12,10,0,0]]
for i in range(....): # 4個人，列
........ # 計算每人總分之前，要先歸0
for j in range(....): # 5科，欄
sum += score[....][....]
score[i][5] = sum
score[....][....] = sum/5
'''
for i in range(4):
score[i][5] = sum(score[i])
score[i][6] = score[i][5]/5
'''
for i in range(4):
print(score[i])
```
:::info
EX_12 (Bonus)：多加一個欄位求名次。
Hint：類似bubble sort的寫法。若此位同學的總分<p位同學，名次為p+1。
:::
``` javascript=
score = [[12,13,15,10,12,0,0,0],[15,13,15,15,14,0,0,0],[14,14,12,15,13,0,0,0],[11,10,12,12,10,0,0,0]]
for ........ # 對第i個人求名次
p=0 # 計算成績大於第i個人的人數
for ........ # 從頭比較每個人的總分
if score[...][....] < score[....][....]:
p+=1
........ # 記錄第i個人的名次
```
:::info
EX_13：字典操作練習。
:::
``` python=
# 1.宣告
ascii = {'a':1, 'b':98, 'c':99 }
color = {'red':[255, 0, 0], 'green':[0, 255, 0], 'blue':[0, 0, 255]}
type(color)
# 2.取值
print(~) 印出紅色的RGB
# 3.修改
~ # 將 'a' 的 ascii 改為 97
print(ascii)
# 4.新增
~ # 新增 'd' 的 ascii 改為 100
print(ascii)
# 5.刪除
~ # 刪除 'a' 的資料
print(ascii)
# 6.取得color字典的所有鍵 keys()
print(~)
for key in color.keys():
print(key)
[key for key in color.keys()]
# 7.取得color字典的所有值 values()
print(~)
# 8.取得color字典的所有鍵值對 items()
print(~)
for ~ in color.items(): # 將鍵值對的key指定到color_name，value指定到rgb後列印出來
print(f'{color_name:6} 的 RGB 為 {rgb}')
```
<br />
## 六、函式
+ 將會重複使用的程式碼聚集在同一個區塊，透過呼叫函式名執行。
1. ### 內建函式庫
- 不需要任何引入動作，就可以直接使用，最基本、核心的函式庫。
- [常用內建函式庫]( https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/372961/)
- [Python Built in Functions](https://www.w3schools.com/python/python_ref_functions.asp)
| 函式 | 意義 |
|:---------------|:------ |
| abs(x) |x的絕對值|
| pow(x,y) |x的y次方|
| round(x,n) |將x四捨五入到小數點後n位|
| max(x1,x2,...) |傳回最大值|
| min(x1,x2,...) |傳回最小值|
| sorted(串列) |將串列排序|
| sum(串列) |傳回串列元素和|
- 字串(string)相關函式
* [Python 字串操作(string替換、刪除、擷取、複製、連線、比較、查詢、包含、大小寫轉換、分割等)](https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/358746/)
* [RUNOOB Python 字符串](http://www.runoob.com/python/python-strings.html)
<br />
| 字串相關函式 | 意義 |
|:----------------|:------ |
| str(n) |將變數n轉為字串型態|
| len(s) |計算變數s的長度|
| str.lower() |將字串中的字母轉成小寫|
| str.upper() |將字串中的字母轉成大寫|
| str.islower() |判斷字串中的字母是否皆為小寫|
| str.isupper() |判斷字串中的字母是否皆為大寫|
| str.find('abc') |尋找字串中'abc'的位置|
| str.count('abc')|計算字串中'abc'出現的次數|
| str.replace(舊子字串,新子字串)|將字串中的舊子字串用新子字串取代|
| str.split()|將字串分割成數個子字串(以空白區分)|
| str.join(sequence)| 指定字符(str)連接串列(sequence)中的元素後，生成新字串 |
| 'ab' in 'abcd' | 判斷'ab'是否在'abcd' |
| str[::-1] | 將字串反轉 |
| [] | 操作同list |
:::info
EX_14：多元選修系統將選課名單匯出成[CSV檔](https://zh.wikipedia.org/wiki/%E9%80%97%E5%8F%B7%E5%88%86%E9%9A%94%E5%80%BC)，請幫老師將名單變成點名表(依字母排序且名字的第一個字母大寫)。
+ [python多個變數的for迴圈](https://www.itread01.com/content/1544266142.html)
+ [Python zip()函數](http://www.runoob.com/python3/python3-func-zip.html)
+ [Python enumerate() 函数](http://www.runoob.com/python/python-func-enumerate.html)
:::
``` javascript=
str = 'john, arno, eden, charles, steve, david, joe, adam, ben, haley '
lst = ~ # 使用split函式，將str以「,」為分隔分割
for i in ~ : # lst裏的每個名字，以replace函式去除空白
lst[i] = ~
'''
不可以用下面的程式，Why？
for name in lst:
name = name.replace...
'''
lst.sort()
for name in lst:
print(name[~].upper() + name[~]) # 字串的索引值從「0」開始，名字的第「0」個字母變大寫。取字串內部字元的方法同list
# 在名字前印出座號，使用 zip() 示範
num = range(~)
for no, name in zip(~, ~):
print(no,name[0].upper()+name[1:])
# Bonus：使用 enumerate()
```
``` javascript=
# zip 範例
a = [1,2,3]
b = [4,5,6]
zipped = zip(a,b) # 返回iterator
c = list(zipped) # list()轉為列表，[(1, 4), (2, 5), (3, 6)]
a1, b1 = zip(*c) # 「*」將序列分解成多個獨立的元素(不在賦值語句中使用*號) a1->(1, 2, 3)、b1->(4, 5, 6)
# P.S. 在賦值語句中使用*號
a, *b = (1, 2, 3, 4) # a->1、b->[2, 3, 4]
```
2. ### 標準函式庫
- [Python 標準函式庫 (Standard Library)](https://python-doc-tw.github.io/library/index.html)
- 使用前需先將該函式的套件匯入，套件匯入方法
* from 套件名稱 import 模組名稱
``` javascript
from math import gcd, pow
```
* from 套件名稱 import *
:mega: 如果在不同套件中有相同的函式名稱，易造成混亂，不易除錯，==不推薦使用全部匯入的方式==。
``` javascript
from random import *
randint(1, 10) # 使用時不用輸入套件名稱
```
``` javascript
from random import *
for i in range(20):
print(randint(1, 10), end=', ') # 產生 1~10 的亂數
print('\n')
from numpy.random import *
for i in range(20):
print(randint(1, 10), end=', ') # 產生 1~9 的亂數，同名函式造成混亂
```
* import 套件名稱
``` javascript
import random # random套件中的所有函式均匯入
random.randint(1, 10) # 套件名稱.函式名稱
```
* import 套件名稱 as 別名
``` javascript
import random as rnd
rnd.randint(1, 10) # 別名.函式名稱
```
3. ### 第三方套件(外部函式庫)
- 不要重造輪子
- [Python Package Index(幾乎包含所有主流套件)](https://pypi.python.org/pypi)
- 使用前需要先行安裝的函式庫
- 使用Anaconda Prompt管理套件
* 顯示已安裝套件：conda list
* 安裝套件：conda install 套件名稱
* 更新套件：conda update 套件名稱
* 更新所有套件：conda update -–all
- 使用pip指令管理套件
* 顯示已安裝套件：pip list
* 安裝套件：pip install 套件名稱
* 更新套件：pip install –U '套件名稱'
* 移除套件：pip uninstall套件名稱
* 顯示套件資訊：pip show 套件名稱
``` javascript
import requests
resp = requests.get('http://cs.cysh.cy.edu.tw')
print(resp.text)
```
4. ### 自訂函式
``` javascript
def 函式名稱([參數1, 參數2, ....]):
程式碼
[return 回傳值1, 回傳值2, ....] # 函數可以同時返回多個值(一個tuple)
```
``` javascript
def 函式名稱([參數1=預設值, 參數2, ....]):
程式碼
[return 回傳值1, 回傳值2, ....] # 函數可以同時返回多個值(一個tuple)
```
``` javascript
def 函式名稱(*參數): #參數數量不定，以tuple儲存
程式碼
[return 回傳值1, 回傳值2, ....]
```
:::info
EX_15：[ZeroJudge b112: 5. 高中運動會](https://zerojudge.tw/ShowProblem?problemid=b112)。
以輾轉相除法求兩數的最大公因數(寫成函式)，並用之來求4數的最大公因數。
[輾轉相除法](http://www.mathland.idv.tw/fun/euclidean.htm)
[短除法找三數的最大公因數(數學作法)](https://www.junyiacademy.org/junyi-math/m4n/m4nyb-/mjnfs7b/v/XK_gpcahyTE)
:::
``` javascript=
def gcd(a, b):
r = a % b # r 為 a 除 b 的餘數
while ........: # 當 ？ 不為 0 時繼續做
........ # 下一次的 a 為 ？
........ # 下一次的 b 為 ？
........ # 計算 a 除以 b 的餘數
return .... # 回傳 a,b 的最大公因數，a? b? r?
# g=gcd(12,16) 函式除錯(Step into)
a, b, c, d = 400, 200, 150, 625
g = gcd(a, b) # g 為 a,b 的最大公因數
........ # g 再和 c 求最大公因數
........ # g 再和 d 求最大公因數
print(g)
```
:::info
EX_16 (Bonus)：寫一函式可以計算n!，並以之求 $C(n,k)=\frac{n!}{(n-k)! * k!}$，例如C(4,2)=6。
```javascript=
def f(n):
........ # 計算 n!
n,k = map(int,input("請輸入n、k(空白隔開)： ").split())
ans = ........
print(ans)
```
:::
5. ### 遞迴
:mega: 在函式之中呼叫函式自己本身，要有終止條件，不然會無窮遞迴下去。
:::info
EX_17：95數學學測填充題G
用黑、白兩種顏色的正方形地磚依照如下的規律拼成若干圖形：
拼第95個圖需用到幾塊白色地磚。(478)
:::
:::info
EX_18 (Bonus)：求費式數列第n項。
[費式數列遞迴式](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97)
:::
``` javascript=
........ : # 函式宣告，名稱為fib，參數n
if n == 0: # n==0 時終止，回傳 0
return 0
elif ........ : # n==1 時終止，回傳 1
........
else:
........ # 遞迴呼叫
n = int(input('輸入n：'))
print(f'費式數列第 {n} 項為 {fib(n)}')
```
:::info
EX_19：以遞迴改寫 EX_14 高中運動會中的gcd函式。
:::
``` javascript=
........ : # 函式宣告，名稱為gcd，參數a,b
if ........ :
return ........
else:
return ........
lst = [400, 200, 150, 625, 600, 100]
g = gcd(lst[0], lst[1])
for ........ : # 從lst[2]開始，都和g求gcd
g = gcd(g, n) # for i in range(2,6):
# g=gcd(g,lst[i])
print(g)
```
:::info
EX_20：以遞迴函式計算 n 層香檳塔，總共有幾個杯子。
遞迴式 : f(n)=1 ,if n==1
f(n)=？ ,if n>1
:::
``` javascript=
def f(n):
........
n = int(input('請輸入 n : '))
print(f(n))
```
:::info
EX_21 (Bonus)：計算 n 層「三角錐形」香檳塔，總共有幾個杯子。
( 第1層1個、2->3、3->6、4->10、5->15、第n層->？個杯子 )
[2017的世界紀錄總共杯子數量為50116](https://kknews.cc/zh-tw/food/3j4y43y.html)，疊了幾層？
:::
:::info
EX_22：以遞迴繪製簡單碎形樹，試試不同參數。
:::
``` javascript=
import turtle
turtle.speed(0) # turtle.tracer(0)
turtle.delay(0) # turtle.update()
theta = 20 # 展開角度
scale = 0.75 # 長度縮小比例
depth = 10 # 深度
def draw_tree(len,depth): # draw_tree函式宣告，len、depth為參數
if depth >= 1:
turtle.forward(len) # 往前畫長len的直線
........ # 右轉角度 θ
........ # 遞迴呼叫，畫右分枝，長度依比例縮小。深度-1
........ # 左轉角度 2θ
........ # 遞迴呼叫，畫左分枝，長度依比例縮小。深度-1
turtle.right(theta) # 右轉角度 θ，回到中間
turtle.backward(len) # 退回起點
turtle.left(90) # 預設座標原點為畫布中心，烏龜朝x軸正方向
turtle.penup()
turtle.goto(0, -200) # 將畫筆移動到座標為(0,-200)的位置，中心點往下200畫素
turtle.pendown()
draw_tree(120, depth)
```
6. ### 區域變數 vs. 全域變數
- 在函式中的變數為區域變數，在函式外的變數為全域變數。
``` javascript=
def fun():
a = 10 # 此處的 a 為區域變數
a = 5 # 此處的 a 為全域變數
fun()
print(a) # a 印出5
```
``` javascript=
def fun():
global a # 使用全域變數 a
a = 10
a = 5
fun()
print(a) # a 被函式改變，印出 10
```
``` javascript=
def fun():
print(a) # 可以使用全域變數 a，印出 5
a = 5 # 此處的 a 為全域變數
fun()
```
7. ### lambda(匿名函式)
``` javascript
lambda 參數1, 參數2, ... : 運算式
即
def func( 參數1, 參數2, ... ) :
return 運算式
```
``` javascript=
def multiply(x,y):
return x*y
print(multiply(5,6))
```
``` javascript=
multiply = lambda x,y: x*y
print(multiply(5,6))
```
``` javascript=
def square(x):
return x**2
lst1=list( map(square, [1,2,3,4,5]) ) # map會把函式依次作用到list的每個元素上，map的結果需要轉成串列才能看到。[1, 4, 9, 16, 25]
lst2=list( map(lambda x: x**2, [1, 2, 3, 4, 5]) ) # 使用 lambda 匿名函式。[1, 4, 9, 16, 25]
lst3=list( filter(lambda x: x%2==0, [1, 2, 3, 4, 5]) ) # filter會檢查list的每個元素是否符合函式(輸出為布林值)，只保留回傳結果為True的元素。[2, 4]
```
<br />
## 七、物件導向
1. ### 類別
- 封裝在類別中的變數或函式，稱為類別的屬性。
``` javascript
class 類別名稱：
變數宣告
def 方法名稱(self): # 函式宣告
程式碼
```
``` javascript=
class Staff:
bonus = 5000
def salary(self): # 呼叫函式的時候，至少會自動傳遞一個參數(staff類別自己本身，透過self操作實體物件的屬性)
return 30000
john = Staff()
print(john.bonus)
print(john.salary())
```
``` javascript=
class Staff:
bonus = 5000
def salary(self):
return 30000+self.bonus
```
2. ### 初始設定
``` javascript
class 類別名稱：
def __init__(self, 參數, ....):
self.變數初始設定=參數
要預先執行的動作
def 方法名稱(self):
程式碼
```
``` javascript=
class Human:
def __init__(self,h,w):
self.height=h
self.weight=w
def BMI(self):
return self.weight / (self.height/100)**2
john = Human(180,70) # 類別實體化時，將180,70指派給self.height、self.weight
print(john.height)
print(john.weight)
print(john.BMI())
```
3. ### 繼承
``` javascript
class 類別名稱(父類別名稱)：
變數宣告
def 方法名稱(self):
程式碼
```
``` javascript=
class AnimalClass:
legs = 4
def walk(self):
print('走動')
def cry(self):
print('啊嗚')
def getLegsNum(self):
print(........) # 腳的數量
class BirdClass(AnimalClass):
........ # 初始設定
print('我是小鳥')
doggy = AnimalClass()
doggy.walk()
doggy.cry()
doggy.getLegsNum()
jiujiu = BirdClass()
jiujiu.walk()
jiujiu.cry()
jiujiu.getLegsNum()
```
:mega: 覆寫(Override)：如果子類別中的方法和父類別的方法同名，從子類別呼叫此方法時，會優先使用子類別的方法。
:::info
EX_23：改寫class BirdClass(AnimalClass)，讓小鳥腳的數量為2，且發出啾啾聲。
:::
``` javascript=
class BirdClass(AnimalClass):
def __init__(self,num):
........ # 設定腳的數量
print('我是小鳥')
........: # 覆寫 cry 函式
........
jiujiu = BirdClass(2)
```
<br />
## 八、檔案存取
1. ### 檔案操作流程
- 開啟檔案->讀取或寫入->關閉檔案
2. ### 開啟檔案
``` javascript
檔案物件=open(檔案路徑, mode=開啟模式)
檔案物件=open(檔案路徑, mode=開啟模式, encoding='utf-8') # 中文如果出現亂碼，加上編碼方式
```
- 開啟模式
| 模式 | 開啟模式代號 |
|:-------|:------: |
| 讀取| r |
| 寫入| w |
| 讀寫| r+ |
| 續寫| a |
3. ### 讀檔
- 讀取全部文字
``` javascript
檔案物件.read()
```
- 一次讀一行
``` javascript
檔案物件.readline()
```
``` javascript
for line in 檔案物件: # 從檔案依序讀取一行到line變數
處理一行的程式碼
```
- 讀取所有行(將每一行結果儲在list中)
``` javascript
檔案物件.readlines()
```
4. ### 寫入
``` javascript
檔案物件.write(字串)
```
5. ### 關閉檔案
``` javascript
檔案物件.close()
```
6. ### 自動、安全的關閉檔案(不需再寫close)
``` javascript
with open(檔案路徑,mode=開啟模式) as 檔案物件：
讀取或寫入檔案程式碼
```
``` javascript=
# 寫入檔案
file=open('test.txt', mode='w')
file.write('Hello World!\nSecond Line')
file.close()
with open('test.txt', mode='w') as file:
file.write('Hello World!\nSecond Line')
# 讀取檔案
with open('test.txt', mode='r') as file:
data=file.read() # 讀取全部
print(data)
with open('test.txt', mode='r') as file:
for line in file: # 一次讀一行
print(line)
```
:::info
EX_24_1：讀入[三國演義txt檔](https://drive.google.com/file/d/1_Y4w8lkK7bQIexjh_CD1ZS2nPStPf8PZ/view?usp=sharing)及[主角名字txt檔](https://drive.google.com/open?id=15betQXxU2EySl96TJoUwOkDmiadim4Fa)，統計主角名字出現的次數。
讀入[兵器txt檔](https://drive.google.com/open?id=1NOe-hgYESXARt3Z4_vaP3Xi4_ygtA64O)，統計各兵器出現的次數。
:::
``` javascript=
with open('three_kingdoms_name.txt',mode='r',encoding='utf-8') as file:
data1=file.read()
names=data1.split('|')
with open('three_kingdoms.txt',mode='r',encoding='utf-8') as file:
data2=file.read()
name_dict={}
for name in names:
name_dict[name]=data2.count(name)
print(sorted(name_dict.items(), key = lambda d:d[1], reverse = True) )
```
:::info
EX_24_2：讀入[兵器txt檔](https://drive.google.com/open?id=1NOe-hgYESXARt3Z4_vaP3Xi4_ygtA64O)，統計各兵器出現的次數。
換行：'\n'
:::
Sign in with Wallet
Connect another wallet