進階程式設計

自訂函數

將經常使用的程式獨立成一個函數，有幾個特色

節省重複撰寫程式的時間
增加可讀性
自訂函數分為兩種，執行完後會回傳結果，或是不回傳結果

從這裡開始，有函數的程式會開始分成數個區塊，所以有幾個重點要釐清

程式的執行流程
參數的傳遞
是否回傳結果

課堂作業：

使用def完成a023 a040，判斷閏年的功能請放到def裡
使用def完成a098，判斷質數的功能請放到def裡
使用def完成a008，計算因數和的功能請放到def裡

不回傳結果

def 函式名稱(參數):

程式碼

主程式

回傳結果

def 函式名稱(參數):

程式碼
return 結果

主程式

不回傳結果-打招呼

def hello(name):

print("hello",name)

x=input()

hello(x)

回傳結果-攝氏轉華氏

def Fahrenheit(c):

f=c*9/5+32
return f

x=int(input())

y=Fahrenheit(x)
print(y)

圖片來源：ccClub

F(4)=4*3*2*1=4*(3*2*1)=4*F(3)
F(3)=3*2*1=3*F(2)
F(2)=2*1=2*F(1)
F(1)=1

遞迴

在函數裡面再呼叫函數，即為遞迴，使用概念如下

大問題拆解成小問題
使用同一個函數解決小問題，即可解決大問題
設計上要注意：何時結束遞迴
多數題目可以用遞迴解題，但也可使用迴圈解題

範例解釋：

N階層、打招呼、費伯納西數列

課堂作業：

使用迴圈完成最大公因數a088
使用遞迴完成最大公因數a088 且最大公因數的功能請放到def裡

自我挑戰：河內塔

打招呼的迴圈寫法與遞迴寫法

迴圈寫法

num=5

while num>0:

print("hello", num)
num=num-1

錯誤的遞迴

def sayhello(num):

print("hello", num)

sayhello(num-1)

#跟5位同學打招呼
sayhello(5)

正確的遞迴

def sayhello(num):

print("hello", num)
#設定終止條件
if num!=1:

sayhello(num-1)

sayhello(5)

費伯納西數列的迴圈寫法與遞迴寫法

迴圈寫法

n=5

front=1

rear=1

result=0

if n==1 or n==2:

print(1)

else:

for i in range(3,n+1):

result=front+rear

front=rear

rear=result

print(result)

遞迴寫法

def fib(n):

if n==1 or n==2:
return 1
else:

return fib(n-1)+fib(n-2)

n=5

result=fib(n)

print(result)

排序

將大量的資訊按照大小排列好，在此介紹兩種基本的排序方法

氣泡排序法 a110
選擇排序法 a111

並且了解排序方法

規則
比較次數：(n-1)+(n-2)+...+1
程式碼

氣泡排序法程式碼

n=input().split()

for run in range(0,len(n)-1):

for i in range(0,len(n)-1-run):

if int(n[i])>int(n[i+1]):

n[i],n[i+1]=n[i+1],n[i]

for item in n:

print(item,end=" ")

氣泡排序法：從最左邊開始兩兩相比，一直比到最後一位，然後再重複數個回合，即可完成

選擇排序法：從左邊開始依序找出最小值，找到之後再與最左邊的人交換位置，以此類推，即可完成

選擇排序法程式碼

n=input().split()

for run in range(0,len(n)):

index=run

for i in range(run,len(n)):

if int(n[index])>int(n[i]):

index=i

n[run],n[index]=n[index],n[run]

for item in n:

print(item,end=" ")

搜尋

在大量的資料內搜尋特定資料，一般來說，資料先排序好再搜尋，會比較有效率，在此介紹兩種基本的搜尋方法

循序搜尋法
二分搜尋法

並且了解排序方法

規則
搜尋次數
1. 循序搜尋法：N次
2. 二分搜尋法：(logN)+1
程式碼

循序搜尋法

n=[6,4,1,9,7,3,2,8]

key=int(input())

found=False

for i in range(len(n)):

if key==n[i]:

print(i+1,"got it")

found=True

break

if not found:

print("failed")

二分搜尋法

n=[2,9,11,15,28,33,40,47,51,64,76,77,82,85,94]

min, max, mid=0, len(n)-1, 0

key=int(input())

found=False

while max>=min:

mid=int((max+min)/2)

if key==n[mid]:

print("got it")

found=True

elif key>n[mid]:

min=mid+1

else:

max=mid-1

if not found:

print("failed")

堆疊Stack

堆疊就像左上圖的玩具，最先放進去的資料，會最晚被拿出來，這個特色稱為先進後出（first in last out），例如在函數裡呼叫函數，最先被呼叫的函數，最後才會完成

佇列Queue

佇列就像排隊，最早排隊的人，最早可以取得服務，這個特色稱為先進先出（first in first out）

使用List實作堆疊概念

新增資料到堆疊

stack=[]

stack.append(1)

stack.append(2)

print(stack)

#資料從下而上：1,2

取得最上方的資料

stack=[1,2]

n=stack.pop()

print(n)

print(stack)

#取得2，堆疊裡剩下1

使用List實作佇列概念

新增資料到佇列

fisrt=0

last=0

queue=[1]

queue.append(2)

last=last+1

queue.append(3)

last=last+1

print(queue)

#資料從左而右：1,2,3

取得最前面的資料

first=0

last=2

queue=[1,2,3]

n=queue.pop(first)

first=first+1

print(n)

print(queue)

#取得1，堆疊裡剩下2,3

其他容器：Set跟Dict

Set：類似清單，但資料不會重複

Dict: 概念類似字典，查詢英文單字顯示中文翻譯，查詢關鍵字顯示相對應的資料（key-value）

課堂作業：a002

Set (集合)

# 建立空的集合
set1 = set()
set2 = {1, 2, 3}
set1.add(1)
set2.remove(2)
# 聯集,交集,差集

print(set1 | set2)

print(setA & setB)

print(setA - setB)

Dict(字典)

book = {"name":"哈利波特", "author":"JK羅琳", "brief":"內容簡介"}

book["publisher"]="某某出版社"

print(book["name"])

print(book)

print(book.keys())

print(book.values())

for key,value in book.items():

print(key,value)

其他

排序搜尋

greedy, dp

建立二元樹（遞迴、回圈）

樹, dfs, bfs，區間（線段樹/binary index tree）

分治

動態規劃 dynamic programming

網路資源：DP by sa072686

Page updated

Google Sites

Report abuse