---
title: '資訊選修-Python By Liao-Hsiu-I'
disqus: hackmd
---
資訊選修-Python By Liao-Hsiu-I
===
[TOC]
基礎程式設計-複習(高一)(9/3)(第一堂)
---
### 觀念驗證題
##### 題目1題目敘述:
```python=
classnum=input("班級座號:")
name=input("班級座號:")
num=input("班級座號:")
print("您的資訊為"+classnum+name)
print("密碼設定為:"+num)
```
##### 題目2題目敘述:
每位同學輸入受測者的班級座號、身高、體重
利用多向條件判斷(要求如下)
BMI的標準18.5<=BMI<24
1.當BMI小於18.5，會送出[太瘦了];
2.當BMI太大時，則是送出[該減重了];
3.當BMI在標準值內，則列印出[標準!]。
```python=
classnum=input("班級座號:")
height=(float(input("請輸入身高")))/100
weight=float(input("請輸入體重"))
BMI=weight/(height*height)
if(BMI>24 or BMI==24):
print("減重了")
elif(BMI<18.5):
print("太瘦了")
else:
print("標準")
```
### 延伸題
##### 題目3題目敘述:
讓使用者輸入一個正整數，然後判斷它是3或5的倍數。
若此數值同時為3與5的倍數→顯示[x為3與5的倍數]:
若此數值為3的倍數→顯示[x為3的倍數];
若此數值為5的倍數→顯示[x為5的倍數];
如此數值皆不屬於 3 或 5 的倍數→顯示[x不為3與5的倍數]。
```python=
num=int(input("請輸入數字"))
if(num%3==0):
if(num%3==0):
print("x 為 15 的倍數")
else:
print("x 為 3 的倍數")
elif(num%5==0 and num%3!=0):
print("x 為 5 的倍數")
else:
print("x 不為 3 與 5 的倍數")
```
##### 題目4題目敘述:
請輸入身份證字號進行男女性別與戶籍(北北基)的判斷設定條件:
1. 開頭英文大小寫都可以
2. 臺灣身分證字號長度須為 10
3. 若為男生,則印出”先生您好,您的戶籍地為......”
若為女生,則印出”小姐您好,您的戶籍地為......”
-提示:
A或Y台北市；F新北市；C基隆市；其他不是北北基。
```python=
identity=input("請輸入身分帳字號")
while True:
if(len(identity)==10):
break
else:
print("輸入錯誤")
identity=input("請輸入身分帳字號")
Identity=identity.upper()
if(Identity[1]=="1"):
if(Identity[0]=="A" or Identity[0]=="Y"):
print(" 先生您好，您的戶籍地為台北市")
elif(Identity[0]=="F"):
print(" 先生您好，您的戶籍地為新北市")
elif(Identity[0]=="C"):
print(" 先生您好，您的戶籍地為基隆市")
elif(Identity[1]=="2"):
if(Identity[0]=="A" or Identity[0]=="Y"):
print(" 小姐您好，您的戶籍地為台北市")
elif(Identity[0]=="F"):
print(" 小姐您好，您的戶籍地為新北市")
elif(Identity[0]=="C"):
print(" 小姐您好，您的戶籍地為基隆市")
```
基礎程式設計(高一)(9/10)(第二堂)
---
### 觀念驗證題
##### 題目1題目敘述:
利用while與for迴圈分別撰寫程式，
列印15次自己的班級座號姓名(含目前列印至第幾次)。
```python=
#for迴圈
nameclass=input("請輸入班級座號")
for j in range(15):
print("第"+str(j+1)+"次打印"+nameclass)
#while迴圈
nameclass=input("請輸入班級座號")
count=0
while(count<15):
print("第"+str(count+1)+"次打印"+nameclass)
#0-14共15次
count+=1
```
##### 題目2題目敘述:
利用利用while與for迴圈分別撰寫程式
請輸入1個正整數n的值，則計算1+2+3+......+n
，並呈現在電腦螢幕上。
```python=
#解1
#for迴圈
total=1
number=int(input("請輸入數字"))
for i in range(number):
total+=i
print(total)
#while迴圈
total=0
number=int(input("請輸入數字"))
i=0
while(i<=number):
total+=i
i+=1
print(total)
#解2
#等差級數總和可由等差總和公式n(n+1)/2求得(n為項數)
number=int(input("請輸入數字"))
print(n(n+1)/2)
```
##### 題目3題目敘述:
請撰寫一程式，讓程式不斷列印1~20間的亂數，但亂數遇到5的倍數不列印，遇到11會結束。
```python=
import random
while True:
num=random.randint(1,20)
if(num%5!=0): #num!=0(mod 5)打印
print(num)
if(num==11):
break
```
### 延伸題
##### 題目4題目敘述:
請撰寫一個程式，先亂數取1-100之間的1個
數字(包含1-100)當作密碼，讓使用者不斷的猜
測,直到猜到正確的答案為止。
使用者每猜一個數字，程式會把範圍縮小，界定
出最大與最小值的可猜範圍。
如果使用者猜的數字超出此範圍之外，則會顯示
超出範圍的訊息。
輸入輸出說明:
-遊戲流程:
假定系統亂數定出88為密碼。
-範例輸入:
請輸入1-100間的數字 : (使用者輸入50)
請輸入50-100間的數字 : (使用者輸入25)
猜測數值超過範圍，請輸入50-100間的數字 : (使用者輸入75)
請輸入76-100間的數字 : (使用者輸入90)
...
答對了，密碼為88。
```python=
import random
passcode=random.randint(1,100)
min=1
max=100
while True:
guess=int(input("請輸入"+str(min)+"-"+str(max)+"間的數字 : "))
if(passcode==guess):
print("答對了，密碼為"+str(passcode))
break
elif(guess>passcode and min<=passcode=<max):
max=guess-1
elif(guess<passcode and min<=passcode=<max):
min=guess+1
else:
print("猜測數值超過範圍，"+"請輸入"+str(min)+"-"+str(max)+"間的數字 : ")
```
##### 題目6題目敘述:
以知大樂透號碼由標準號6碼與特別號1碼所組成
請撰寫一程式，讓系統隨機從1~49 中，
開出6個號碼(標準號)、及1個特別號(號碼不可重複)。
-輸出範例:
樂透中獎號碼 : 2 5 25 26 37 42
特別號 : 8
```python=
import random
lotta=[]
for i in range(7):
randi=random.randint(1,49)
if randi not in lotta:
lotta.append(randi)
i-=1
print("樂透中獎號碼 :",end=" ")
for i in range(6):
print(lotta[i],end=" ")
#print(lotta[頭:尾])亦可
print()
print("特別號 : "+str(lotta[6]))
```
基礎程式設計(9/17)(第三堂)
---
### NOTE
①格式
```python=
def 函數名稱 (參數):
內容
函式名稱( ) #呼叫函式
```
②創造函式目的
1.增強程式架構性
2.重複使用時呼叫即可
e.g.:
```python=
def wash(dry): #def before calling
print("加水")
print("加洗衣精")
print("旋轉")
if(dry):
print("烘衣")
wash(True)
```
有參數函數
①當function需要用到外部資料,就設計參數,把資料投進去function裡
②如果function有參數設定,就一定要投東西(除非有預設值)
參數可以不只一個 (多個參數 用 , 隔開)
③投東西的時候是按照參數的順序
④參數可以有”預設值”,就不一定要投東西給參數
⑤投東西給參數時,可以”明確指定”要投給哪一個參數
### 題目們
```python=
#0
def add(x,y):
print(x+y)
add(2)#依序儲存x=2
```
```python=
#1
def power(x,y):
return x**y
number1=int(input("請輸入底數數字"))
number2=int(input("請輸入次方數字"))
result=power(x=number1,y=number2)
print(number1,"的",number2,"次方為",result)
```
```python=
#2
def nroot(x,y):
return x**(1/y)
number1=int(input("請輸入被開方數字"))
number2=int(input("請輸入開方數字"))
result=nroot(x=number1,y=number2)
print(number1,"開",number2,"次方為",result)
```
```python=
#3
def equation(a,b,c):
D=b**2-4*a*c
if(D<0):
return("無解")
if (D==0):
return str((-b/(2*a)))
if (D>0):
m=(-b+(D)**(1/2))/(2*a)
n=((-b-(D)**(1/2))/(2*a))
return str(m)+","+str(n)
number1=int(input("請輸入方程式係數a:"))
number2=int(input("請輸入方程式係數b:"))
number3=int(input("請輸入方程式係數c:"))
p=equation(number1,number2,number3)
print("方程式的解為",p)
```
```python=
#4
shopping_list=[]#[goods][price]
while True:
goods_name=input("請輸入商品名稱")
goods_price=input("請輸入商品名稱")
if(goods_name=="q"):
break
data=[goods_name, goods_price]
shopping_list.append(data)
```
基礎程式設計(9/24)(第四堂)
---
### 觀念驗證題
### 延伸題
基礎程式設計(10/8)(第五堂)
---
### 記帳程式
##### 題目6題目敘述:
```python=
products=[]
while True:
name=input("請輸入商品名稱")
if name=="q":
break
price=int(input("請輸入商品價格:"))
p = [ ]
p.append(name)
p.append(price)
products.append(p)
print(products)
for p in products:
print(p[0],"價格是",p[1])
with open("products.csv","w") as f:
#with(結束後自動關閉) open("檔案名稱.格式","模式",encording="編碼方式") as file
f.write("名稱"+","+"價格"+"\n")#write寫入,write要是長串文字不可"a","b"
for p in products:
f.write(p[0]+","+str(p[1])+"\n")
```
基礎程式設計(10/15)(第六堂)
---
### 記帳程式(有檔案之情況)
```python=
products=[]
with open("products.csv","r",encoding="utf-8") as f: #"r"=read
for line in f:
if "商品,價格" in line:
continue
name, price=line.strip().split(",")
print([name,price])
products.append([name,price])
while True:
name=input("請輸入商品名稱")
if name=="q":
break
price=int(input("請輸入商品價格:"))
p = [ ]
p.append(name)
p.append(price)
products.append(p)
print(products)
for p in products:
print(p[0],"價格是",p[1])
with open("products.csv","w",encoding="utf-8") as f: ##"w"=write
#with(結束後自動關閉) open("檔案名稱.格式","模式",encording="編碼方式") as file
f.write("商品"+","+"價格"+"\n")#write寫入,write要是長串文字不可"a","b"
for p in products:
f.write(p[0]+","+str(p[1])+"\n")
```
### 記帳程式(任何情況)
```python=
import os
products=[]
if os.path.isfile("products.csv"): #檢查有無舊有檔案
print("我找到檔案了")
with open("products.csv","r",encoding="utf-8") as f: #"r"=read
for line in f:
if "商品,價格" in line:
continue#跳過此回合
name, price=line.strip().split(",")#strip去除多餘空白/換行
print([name,price])
products.append([name,price])
else:
print("找不到檔案")
while True:
name=input("請輸入商品名稱")
if name=="q":
break
price=int(input("請輸入商品價格:"))
p = [ ]
p.append(name)
p.append(price)
products.append(p)
print(products)
for p in products:
print(p[0],"價格是",p[1])
with open("products.csv","w",encoding="utf-8") as f: ##"w"=write
#with(結束後自動關閉) open("檔案名稱.格式","模式",encording="編碼方式") as file
f.write("商品"+","+"價格"+"\n")#write寫入,write要是長串文字不可"a","b"
for p in products:
f.write(p[0]+","+str(p[1])+"\n")
```
## 基礎程式設計(10/22)(第七堂)
### 記帳程式函式寫法
```python=
import os
products=[]
def check_file(file_name):
if os.path.isfile(file_name): #檢查有無舊有檔案
print("我找到檔案了")
with open((file_name),"r",encoding="utf-8") as f: #"r"=read
for line in f:
if "商品,價格" in line:
continue#跳過此回合
name, price=line.strip().split(",")#strip去除多餘空白/換行
print([name,price])
products.append([name,price])
else:
print("找不到檔案")
return products
def user_input(products):
while True:
name=input("請輸入商品名稱")
if name=="q":
break
price=int(input("請輸入商品價格:"))
products.append([name,price])
return products #不知道=>傳入更改=>return
def print_list(products):
for p in products:
print(p[0],"價格是",p[1])
def write_file(file_name,products):
with open(file_name,"w",encoding="utf-8") as f:
##"w"=write
#with(結束後自動關閉) open("檔案名稱.格式","模式",encording="編碼方式") as file
f.write("商品"+","+"價格"+"\n")#write寫入,write要是長串文字不可"a","b"
for p in products:
f.write(p[0]+","+str(p[1])+"\n")
products=check_file("products.csv")
products=user_input(products)
print_list(products)
write_file("products.csv",products)
```
## 基礎程式設計(10/29)(第八堂)
### NOTE
#### 演算法特性
①輸入:>=0個輸入值
②輸出:經過演算法處理後,至少有一個輸出結果
③明確性:演算法的每一個步驟都要有明確的定義
④有限性:在有限的步驟或時間內結束
⑤有效性:有效且具體可行
輸入+演算法=輸出(如同x經f(x)映射後的結果)
#### 時間複雜度
以O(BIG O)表示 e.g.:O(n^2),O(1),O(log n)...
時間複雜度並非以執行時間做為計算，而是以步驟次數作為計算(取最差的情況)
愛你N次
```python=
n=int(input(""))
for i in range(1,n+1):
print("愛你",i,"次")
```
### 給定索引(座號)找名字
```python=
import os
name_list=[]
with open("name.csv","r",encoding="utf-8-sig") as f: #"r"=read
for line in f:
if "姓名" in line:
continue#跳過此回合
else:
name_list.append(line.strip())
n=input("請輸入姓名") #輸入名字=>編號
print( name_list.index(n)+2)
ind=int(input("請輸入編號") )#輸入編號=>名字
print( name_list[ind-2])
```
## 基礎程式設計(11/5)(第九堂)
### 循序搜尋1---數字查找(線性搜尋)
```python=
num_list=[6,1,5,7,3,9,4,2,8]
num=int(input("請輸入要找哪個數字") )#輸入數字
num_google=False
for i in num_list:
if(num==i):
num_google=True
print("我找到了")
print("在索引",num_list.index(num),"位置找到","花了",num_list.index(num)+1,"次搜尋")
break
if(num_google==False):
print("查無此號碼")
```
### 循序搜尋2---數字查找
```python=
import os
name_list=[]
with open("name.csv","r",encoding="utf-8-sig") as f: #"r"=read
for line in f:
if "姓名" in line:
continue#跳過此回合
else:
name_list.append(line.strip())
name_google=False
name=input("請輸入姓名") #輸入名字=>編號
for i in name_list:
if(name==i):
name_google=True
print("我找到了")
print("在索引",name_list.index(name),"位置找到","花了",name_list.index(name)+1,"次搜尋")
break
if(name_google==False):
print("查無此人")
```
### 循序搜尋3---名單持續更改(修改2))
```python=
import os
name_list=[]
with open("name.csv","r",encoding="utf-8-sig") as f: #"r"=read
for line in f:
if "姓名" in line:
continue#跳過此回合
else:
name_list.append(line.strip())
while True:
name_google=False
name=input("請輸入姓名") #輸入數字
if(name=="q"):
break
for i in name_list:
if(name==i):
name_google=True
print("我找到了")
print("在索引",name_list.index(name),"位置找到","花了",name_list.index(name)+1,"次搜尋")
break
if(name_google==False):
print("查無此人")
```
## 基礎程式設計(11/12)(第十堂)
### 二分搜尋
題目①:
有1數字空list,依序輸入數值資料如下:
16,2,81,34,67,47,53 共7個數字
請輸入一個數值,判斷此數值是否有在上
方數字數列中
狀況:
1.若數值有在數列中,請問數值在數字清
單中的哪個索引位置?並花了幾個步驟才
找到此數值。
2.若數值不在數列中,請列印查無此號碼
```csharp=
list_num=[16,2,81,34,67,47,53]
list_num.sort()
num=int(input("請輸入數值"))
left_index=0
right_index=len(list_num)-1
count=0
index=-1
print(list_num)
while(left_index<=right_index):
count+=1
mid=(left_index+right_index)//2
if(num==list_num[mid]):
index=mid
break
elif(num<list_num[mid]):
right_index=mid-1
elif(num>list_num[mid]):
left_index=mid+1
if(index==-1):
print("查無此號碼")
else:
print("找到了")
print("在索引",index,"位置找到")
print("共找了",count,"次")
```
題目②:
百貨公司舉辦周年抽獎活動,將顧客的
抽獎編號與姓名分別存在list中,使用者
輸入編號,程式會搜尋出該編號的姓名
並顯示,若查詢不到也會顯示無此編號
的訊息。
請以2分搜尋法進行中獎人查詢。
狀況:
1.若編號有在名單中,請問此人在清單
中的哪個索引位置?並花了幾個步驟才
找到此數值。
2.若人員不在名單中,請列印查無此人
```csharp=
num_name_list=[[256, 'A'], [731, 'B'], [943, 'c'], [389, 'D'], [142, 'E'], [645, 'F'], [829, 'G'], [945, 'H'], [371, 'I'], [418, 'j']]
num_name_list.sort()
no=int(input("請輸入中獎號碼"))
left_index=0
right_index=len(num_name_list)-1
count=0
index=-1
print(num_name_list)
while(left_index<=right_index):
count+=1
mid=(left_index+right_index)//2
if(no==num_name_list[mid][0]):
index=mid
break
elif(no<num_name_list[mid][0]):
right_index=mid-1
elif(no>num_name_list[mid][0]):
left_index=mid+1
if(index==-1):
print("查無此人")
else:
print("找到了")
print("在索引",index,"位置找到")
print("共找了",count,"次")
```
## 基礎程式設計(11/26)(第十一堂)
### Bubble Sort
```python=
list_num=[16,2,81,34,67,47,53]
list_sorted=[16,2,81,34,67,47,53]
print(sorted(list_sorted))
for i in range(0,len(list_sorted)):
maxi_index=i
mini_index=i
for j in range(i,len(list_sorted)):
if(list_sorted[j]>list_sorted[maxi_index]):
maxi_index=j
if(list_sorted[j]<list_sorted[mini_index]):
mini_index=j
c=list_sorted[mini_index]
list_sorted[mini_index]=list_sorted[maxi_index]
list_sorted[maxi_index]=c
print(list_sorted)
```
### 改函式
```python=
def new_sort(list_sorted):
for i in range(0,len(list_sorted)):
maxi_index=i
mini_index=i
for j in range(i,len(list_sorted)):
if(list_sorted[j]>list_sorted[maxi_index]):
maxi_index=j
if(list_sorted[j]<list_sorted[mini_index]):
mini_index=j
c=list_sorted[mini_index]
list_sorted[mini_index]=list_sorted[maxi_index]
list_sorted[maxi_index]=c
print("第",i+1,"回合",list_sorted)
list_=[16,2,81,34,67,47,53]
print("排序前",list_)
print("排序後",new_sort(list_))
```
## 基礎程式設計(12/10)(第十二堂)
### NOTE
①概念:
(圖源: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)
②時間複雜度:O(nlogn)
### 選擇排序
題目①:
動物園進行我是大明星的動物票選,票選
結果如下表。
將資料運用2維清單與插入排序進行以下
動作:
狀況:
1.將票數由小至大呈現每個動物的得票狀
況。並將排序前、排序後進行呈現比對。
2.將選擇排序的每次步驟呈現
3.並呈現誰是最高票的明星動物
| 明星候選人 | 票數 |
| ---------- | -------- |
| 長頸鹿 | 105 |
| 河馬 | 73 |
| 兔子 | 124|
| 猴子| 68|
| 獅子| 50|
```python=
vote_animals=[["長頸鹿",105],["河馬",73],["兔子",124],["猴子",68],["獅子",50]]
print("原始資料",vote_animals)
for i in range(len(vote_animals)-1):
mini=i
for j in range(i+1,len(vote_animals)):
if(vote_animals[j][1]<vote_animals[mini][1]):
mini=j
change=vote_animals[i]
vote_animals[i]=vote_animals[mini]
vote_animals[mini]=change
print("這是第%s次排序"%(i+1),vote_animals)
print("最高票動物:",vote_animals)
print("最高票:",vote_animals[-1])
```
題目②:
有1數字list,內部數值資料如下:
16,2,81,34,67,47,53 共7個數字
請利用選擇排序
狀況:
1.將list內的數字由小至大排序。並將排
序前、排序後進行呈現比對。
2.將選擇排序的每次步驟呈現
```python=
num_list=[16,2,81,34,67,47,53]
for i in range(1,len(num_list)):
position=i
while position>0 and num_list[position]<num_list[position-1]:
num_list[position],num_list[position-1]=num_list[position-1],num_list[position]
#ac交換 a,c=c,a
position-=1
print(num_list)
def insert_function(data):
for i in range(1,len(data)):
position=i
while position>0 and data[position]<data[position-1]:
data[position],data[position-1]=data[position-1],data[position]
#ac交換 a,c=c,a
position-=1
return data
num_list=[16,2,81,34,67,47,53]
print("排序前資料:",num_list)
print("排序後資料:",insert_function(num_list))
```
## 基礎程式設計(12/17)(第十三堂)
### 插入排序
### NOTE
①概念:
②時間複雜度:O(n^2)
題目①:
有1數字list,內部數值資料如下:
41,33,17,80,61,5,55 共7個數字
請利用插入排序
狀況:
1.將list內的數字由小至大排序。並將排
序前、排序後進行呈現比對。
2.將選擇排序的每次步驟呈現
```python=
vote_animals=[["長頸鹿",105],["河馬",73],["兔子",124],["猴子",68],["獅子",50]]
for i in range(1,len(vote_animals)):
position=i
while position>0 and vote_animals[position][1]<vote_animals[position-1][1]:
vote_animals[position],vote_animals[position-1]=vote_animals[position-1],vote_animals[position]
#ac交換 a,c=c,a
position-=1
print(vote_animals)
print()
```
題目②:
動物園進行我是大明星的動物票選,票選
結果如下表。
將資料運用2維清單與插入排序進行以下
動作:
狀況:
1.將票數由小至大呈現每個動物的得票狀
況。並將排序前、排序後進行呈現比對。
2.將選擇排序的每次步驟呈現
3.並呈現誰是最高票的明星動物
| 明星候選人 | 票數 |
| ---------- | -------- |
| 長頸鹿 | 105 |
| 河馬 | 73 |
| 兔子 | 124|
| 猴子| 68|
| 獅子| 50|
```python=
vote_animals=[["長頸鹿",105],["河馬",73],["兔子",124],["猴子",68],["獅子",50]]
def insert_function(data):
for i in range(1,len(data)):
position=i
while position>0 and data[position][1]<data[position-1][1]:
data[position],data[position-1]=data[position-1],data[position]
#ac交換 a,c=c,a
position-=1
print("第",i,"回合",data)
return data
print("排序前資料:",vote_animals)
print("排序後資料:",insert_function(vote_animals))
print(vote_animals[-1])
products=[]
with open("products.csv","r",encoding="utf-8") as f: #"r"=read
for line in f:
if "商品,價格" in line:
continue
name, price=line.strip().split(",")
print([name,price])
products.append([name,price])
```
## 基礎程式設計(12/31)(第十四堂)
### 合併排序(寫法1)
### NOTE
①概念:
圖源: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%E9%80%B2%E9%9A%8E-%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F%E6%B3%95-6252651c6f7e
②時間複雜度:O(nlogn)
```python=
def merge(left,right):
output=[]
while (len(left) and len(right)):
if (left[0]<=right[0]):
output.append(left.pop(0))
else:
output.append(right.pop(0))
if (len(left)):
output=output+left
if (len(right)):
output=output+right
print("此次合併狀況",output)
return output
def merge_sort(A):
print("分割數列",A)
if (len(A)<=1):
return A
mid=len(A)//2
left=A[:mid]
right=A[mid:]
left=merge_sort(left)
right=merge_sort(right)
return merge(left,right)
data=[9,7,2,1,3,4,6,8]
print("原始串列",data)
```
## 基礎程式設計(1/7)(第十五堂)
題目:
有1數字list,內部數值資料如下:
9,7,2,1,3,4,6,8 共8個數字
請利用合併排序
狀況:
1.將list內的數字由小至大排序。並將排
序前、排序後進行呈現比對。
2.將選擇排序的每次步驟呈現
### 合併排序(寫法2)
```python=
def merge(left,right):
output=[0]*(len(right)+len(right))
key_right=0
key_left=0
key_output=0
while (len(left)-key_left and len(right)-key_right):
if(left[key_left]>=right[key_right]):
output[key_output]=right[key_right]
key_right+=1
else:
output[key_output]=left[key_left]
key_left+=1
key_output+=1
while(len(left)-key_left):
output[key_output]=left[key_left]
key_left+=1
key_output+=1
while(len(right)-key_right):
output[key_output]=right[key_right]
key_right+=1
key_output+=1
print("此次合併狀況",output)
return output
def merge_sort(A):
print("分割數列",A)
if (len(A)<=1):
return A
mid=len(A)//2
left=A[:mid]
right=A[mid:]
left=merge_sort(left)
right=merge_sort(right)
return merge(left,right)
data=[9,7,2,1,3,4,6,8]
print("原始串列",data)
print("後來串列",merge_sort(data))
```
## 總結
演算法比較
| 演算法 | 時間複雜度 | 空間複雜度 | 概念類型 |
| -------------------------- | ---------- | ---------- | -------- |
| 選擇排序法(Selection Sort)|Ο(n^2)|Ο(1)|選擇|
| 插入排序法(Insertion Sort)|Ο(n^2)|Ο(1)| 插入|
| 氣泡排序法(Bubble Sort |Ο(n^2)|Ο(1)|交換|
| 合併排序法(Merge Sort) |Ο(nlogn) |Ο(n)+Ο(1)|合併|
心得:
我在這堂課學會了許多排序演算法，希望能在課外學得更多演算法
，以利於處理不同類型問題
Sign in with Wallet
Connect another wallet