李文廷

Hot、增能課程錄影檔，感謝佳純老師提供：https://drive.google.com/drive/folders/1-dznGgPunnoTcmdNk88iIwBaZN3R54xV

上課教材區：https://drive.google.com/drive/folders/1NPj8-ZgTSso7JohdEZE9g_uOalfM0vSj?usp=sharing

使用非學校網域Google GMail帳號，無痕模式：https://colab.research.google.com/

OnlineJudge:https://onlinejudge.sdpmlab.org/

1.先安裝OPython: https://www.python.org/downloads/

2.再安裝PyCharm: https://www.jetbrains.com/pycharm/

Pycharm的設定

字體大小：File -> Settings... -> Editor -> Font 內的 Size:

選擇Python執行版本：File -> Settings... -> Project: Pycharm -> Pycharm interpreter

b003 Merge Sort 合併排序

時間複雜度O(n log n)

使用遞迴不斷切割陣列，然後合併陣列。

#輸出BMI取小數點兩位

height = float(input("What is your height? "))

weight = int(input("What is your weight? "))

BMI = weight / (height * height)

name = input("What is your name? ")

print("%s's BMI is %.2f"%(name,BMI)) #C like

print("{}'s BMI is {:.2f}".format(name,BMI)) #大括號法1

print("{name}'s BMI is {BMI:.2f}") #大括號法2

判斷BMI範圍

height = float(input("What is your height? "))

weight = int(input("What is your weight? "))

BMI = weight / (height * height)

name = input("What is your name? ")

print(name + "'s BMI is {:.2f}".format(BMI))

if BMI<18.5:

print("體重過輕")

elif 18.5<=BMI<24:

print("正常範圍")

elif 24 <= BMI < 27:

print("稍重")

elif 27<= BMI <30:

print("輕度肥胖")

elif 30<= BMI < 35:

print("中度肥胖")

else:

print("重度肥胖")

使用while迴圈撰寫Python程式，讓使用者輸入一個整數，並將此整數的每個數字反向輸出，例如輸入123456，程式輸出654321。

number = int(input('請輸入任一整數:'))

print('輸出反向數字為:', end='')

while (number != 0):

print(number%10, end='') #取除10餘數輸出，不換行

number //= 10 #取除以10的商

最大公因數 GCD（Greatest Common Divisor）

窮舉法

a = int(input('輸入第一個數字：'))

b = int(input('輸入第二個數字：'))

x = 1

for i in range(1,a+1):

if a%i==0 and b%i==0:

x=i

print(x)

輾轉相除法

a = int(input('輸入第一個數字：'))

b = int(input('輸入第二個數字：'))

a1=a

b1=b

while a!=b:

if a>b:

a=a-b

else:

b=b-a

print("GCD=",a)

b004 最小公倍數LCM（Lowest Common Multiple）

a = int(input('輸入第一個數字：'))

b = int(input('輸入第二個數字：'))

a1=a

b1=b

while a!=b:

if a>b:

a=a-b

else:

b=b-a

print(int((a1*b1)/a))

b005 重新排序的身高

Input

161,165,166,171,180,191

172

Output

161 165 166 171 172 180 191

程式碼範例：

str = input()

#字串轉整數串列

list1 = [int(item) for item in str.split(',')]

h=int(input())

list1.append(h)

list1.sort()

for i in list1:

print(i,end=' ')

print()

b006 誰的 BMI 最高

colab.research.google.com

Input1

{"John": {"height": 171, "weight": 50}, "Nick": {"height": 175, "weight": 65}}

Output1

Nick

Input2

{"Mary": {"height": 154, "weight": 40}, "Nicolas": {"height": 180, "weight": 85}, "Nei": {"height": 168, "weight": 55}, "Gold": {"height": 175, "weight": 75}}

Output2

Nicolas

範例程式

health = eval(input())

max=0

for key, value in health.items():

h=value['height']/100

bmi=value['weight']/(h*h)

if bmi>max:

max=bmi

name=key

print(name)

助教寫法

BMI_MAX = 0

BMI_dict = eval(input)) #eval會把單引號或雙引號去掉

for i in BMI_dict:

BMI_temp = BMI_dict[i]

BMI = BMI_temp["weight"] / (BMI_temp["height"]/100)**2

if (BMI > BMI_MAX:

BMI_MAX = BMI

people = i

print(people)

OnlineJudge

Input1

John 171 50

Nick 175 65

0 0 0

Output1

Nick

Input2

Mary 154 40

Nicolas 180 85

Nei 168 55

Gold 175 75

0 0 0

Output2

Nicolas

範例程式

health={}

done = False

while not done:

str = input()

list1=[]

list1=str.split()

name=list1[0]

height=int(list1[1])

weight=int(list1[2])

if height+weight==0:

done=True

else:

hw={}

hw['height']=height

hw['weight']=weight

health[name]=hw

max=0

for key,value in health.items():

h=value['height']/100

bmi=value['weight']/(h*h)

if bmi>max:

max=bmi

name=key

print(name)

助教寫法

BMI_MAX = 0

BMI_dict = {}

while (True):

BMI_list = input().split()

if (BMI_list[0]=="0":

break

BMI_dict[BMI_list[0]] = {"height: int(BMI_list[1]), "weight": int(BMI_list[2])}

for i in BMI_dict:

BMI = BMI_dict[i]["weight"] / (BMI_dict[i]["weight"]/100)**2

if BMI > BMI_MAX:

BMI_MAX = BMI

people = i

print(people)

Radix Sort

https://www.programiz.com/dsa/radix-sort

Bucket Sort

動態規劃

四個步驟：

1. Characterize the structure of an optimal soluation.

尋找最佳解的結構

2. Derive recursive formula for computing the values of optimal solution.

推導遞迴公式

3. Compute the value of an optimal solution in a bottom-up fashion (top-down is also applicable).

由下往上計算子問題最佳解的值(由上往下亦可)

4. Construct an optimal solution from computed values.

從子問題計算出的值建構出最佳解