--------------------------------------------------1-InsertionSort
lst=[5,2,4,6,1,3]
for i in range(1,len(lst)):
print("第",i,"回合")
for j in range(i-1,-1,-1):
if lst[i]<lst[j]:
lst[i],lst[j]=lst[j],lst[i]
i=j
print(lst)
print()
=========
第 1 回合
[2, 5, 4, 6, 1, 3]
第 2 回合
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
第 3 回合
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
第 4 回合
[2, 4, 5, 1, 6, 3]
[2, 4, 1, 5, 6, 3]
[2, 1, 4, 5, 6, 3]
[1, 2, 4, 5, 6, 3]
第 5 回合
[1, 2, 4, 5, 3, 6]
[1, 2, 4, 3, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
--------------------------------------------------2-mergesort_ex
import math
def Merge(items,l,m,r):
n1=m-l+1
n2=r-m
lstL=[];lstR=[]
for i in range(0,n1):
lstL.append(items[l+i])
for j in range(0,n2):
lstR.append(items[m+j+1])
lstL.append(math.inf)
lstR.append(math.inf)
i=0;j=0
for k in range(l,r+1):
if lstL[i]<=lstR[j]:
items[k]=lstL[i]
i+=1
else:
items[k]=lstR[j]
j+=1
def MergeSort(items,l,r):
if l<r:
m=math.floor((l+r)/2)
MergeSort(items,l,m)
MergeSort(items,m+1,r)
Merge(items,l,m,r)
items=[5,2,4,7,1,3,2,6]
MergeSort(items,0,len(items)-1)
print(items)
=========
[1, 2, 2, 3, 4, 5, 6, 7]
--------------------------------------------------3-binary_search_ex
import math
def binary_search(list, target):
L=0;R=len(list)-1
while L<=R:
M=math.floor((L+R)/2)
if list[M]==target:
return M
elif list[M]<target:
L=M+1
elif list[M]>target:
R=M-1
else:
return "None"
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # => 1
# 'None' means nil in Python. We use to indicate that the item wasn't found.
print(binary_search(my_list, -1)) # => None
=========
1
None
--------------------------------------------------4-Heap_Sort_ex
"""
This is a pure Python implementation of the heap sort algorithm.
"""
def heapify(unsorted, index, heap_size):
largest=index
left_index=2*index+1
right_index=2*index+2
if left_index<heap_size and unsorted[left_index]>unsorted[largest]:
largest=left_index
if right_index<heap_size and unsorted[right_index]>unsorted[largest]:
largest=right_index
if largest!=index:
unsorted[largest],unsorted[index]=unsorted[index],unsorted[largest]
heapify(unsorted, largest, heap_size)
def heap_sort(unsorted):
n=len(unsorted)
for i in range(n//2-1,-1,-1):
heapify(unsorted, i,n)
for i in range(n-1,0,-1):
unsorted[0],unsorted[i]=unsorted[i],unsorted[0]
heapify(unsorted, 0,i)
return unsorted
if __name__ == "__main__":
unsorted = [1, 4, 7, 2, 1, 3, 2, 5, 4, 2]
print(heap_sort(unsorted))
=========
[1, 1, 2, 2, 2, 3, 4, 4, 5, 7]
--------------------------------------------------5-quicksort
def quick_sort(nums,low,high):
if low<high:
pivot=partition(nums,low,high)
quick_sort(nums,low,pivot-1)
quick_sort(nums,pivot+1,high)
def partition(nums,low,high):
i=low-1
for j in range(low,high):
#pivot --> nums[high]
if nums[j]<=nums[high]:
i+=1
nums[j],nums[i]=nums[i],nums[j]
pivot=i+1
nums[pivot],nums[high]=nums[high],nums[pivot]
return pivot
if __name__ == "__main__":
nums = [2,8,7,1,3,5,6,4]
quick_sort(nums, 0, len(nums)-1)
print(nums)
=========
[1, 2, 3, 4, 5, 6, 7, 8]
--------------------------------------------------6-counting_sort
def counting_sort(A, B, k):
print("原來數列:",A)
C=[]
for i in range(k+1):
C.append(0)
for j in range(len(A)):
C[A[j]]=C[A[j]]+1
print("0,1,2,3,4,5。 每個數字出現次數:",C)
for i in range(1,len(C)):
C[i]=C[i]+C[i-1]
print("小於等於每個數字，出現次數累計:",C)
for j in range(len(A)-1,-1,-1):
B[C[A[j]]-1]=A[j]
C[A[j]]=C[A[j]]-1
return B
if __name__ == '__main__':
alist = [2,5,3,0,2,3,0,3]
k = max(alist)
B = [0] * len(alist)
print("排序數列:",counting_sort(alist, B, k))
=========
原來數列: [2, 5, 3, 0, 2, 3, 0, 3]
0,1,2,3,4,5。 每個數字出現次數: [2, 0, 2, 3, 0, 1]
小於等於每個數字，出現次數累計: [2, 2, 4, 7, 7, 8]
排序數列: [0, 0, 2, 2, 3, 3, 3, 5]
--------------------------------------------------7-rod_cutting_ex
def cut_rod(prices, n):
pass
def top_down_cut_rod(prices, n):
pass
def extended_bottom_up_cut_rod(prices, n):
r=[float("-inf") for i in range(n+1)]
s=[0 for i in range(n+1)]
r[0]=0
for j in range(1,n+1):
q=float("-inf")
for i in range(1,j+1):
if q<prices[i-1]+r[j-i]:
q=prices[i-1]+r[j-i]
s[j]=i
r[j]=q
return r[n],s
if __name__ == "__main__":
#prices = [6, 10, 12, 15, 20, 23]
prices = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
n = len(prices)
# print(cut_rod(prices, n))
# print(top_down_cut_rod(prices, n))
print(extended_bottom_up_cut_rod(prices, n))
=========
(30, [0, 1, 2, 3, 2, 2, 6, 1, 2, 3, 10])
--------------------------------------------------8-longest_common_subsequence
def longest_common_subsequence(x: str, y: str):
m=len(x)
n=len(y)
C=[[0]*(n+1) for j in range(m+1)]
B=[[0]*(n+1) for j in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if x[i-1]==y[j-1]:
C[i][j]=C[i-1][j-1]+1
B[i][j]="~"
elif C[i-1][j]>=C[i][j-1]:
C[i][j]=C[i-1][j]
B[i][j]="^"
else:
C[i][j]=C[i][j-1]
B[i][j]="<"
seq=""
i=m;j=n
while i>0 and j>0:
if B[i][j]=="~":
seq=x[i-1]+seq
i=i-1
j=j-1
elif B[i][j]=="^":
i=i-1
elif B[i][j]=="<":
j=j-1
return C[m][n], seq
if __name__ == "__main__":
a = "ABCBDAB"
b = "BDCABA"
# a="AB"
# b="B"
length, subseq = longest_common_subsequence(a, b)
print("len =", length, ", sub-sequence =", subseq)
=========
len = 4 , sub-sequence = BCBA
--------------------------------------------------9-activity_selection
def recursive_activity_selector(s, f, k, n):
m=k+1
while m<n and s[m]<f[k]:
m=m+1
if m<n:
print(m,end=' ')
recursive_activity_selector(s, f, m, n)
else:
return 0
def greedy_acitivty_selector(s, f):
n=len(s)
print(1,end=" ")
k=1
for m in range(2,n):
if s[m]>=f[k]:
print(m,end=" ")
k=m
if __name__ == "__main__":
s = [0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12]
f = [0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
recursive_activity_selector(s, f, 0, len(s))
print()
greedy_acitivty_selector(s, f)
=========
1 4 8 11
1 4 8 11
--------------------------------------------------10-depth_first_search_ex
class Graph:
def __init__(self):
self.vertex = {}
#self.color=""
# for printing the Graph vertices
def printGraph(self):
print(self.vertex)
for i in self.vertex.keys():
print(i, " -> ", " -> ".join([str(j) for j in self.vertex[i]]))
# for adding the edge between two vertices
def addEdge(self, fromVertex, toVertex):
# check if vertex is already present,
if fromVertex in self.vertex.keys():
self.vertex[fromVertex].append(toVertex)
else:
# else make a new vertex
self.vertex[fromVertex] = [toVertex]
def DFS(self):
visited=[False]*len(self.vertex)
for i in range(len(self.vertex)):
if visited[i]==False:
self.DFSRec(i,visited)
def DFSRec(self, startVertex, visited):
visited[startVertex]=True
print(startVertex,end=" ")
for i in self.vertex.keys():
if visited[i]==False:
self.DFSRec(i,visited)
if __name__ == "__main__":
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
g.printGraph()
print("DFS:")
g.DFS()
=========
{0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}
0 -> 1 -> 2
1 -> 2
2 -> 0 -> 3
3 -> 3
DFS:
0 1 2 3
========= 程式設計與資料結構
二維陣列運算
由鍵盤輸入二維陣列整數，求出每一列 (row) 的最小值，再求出各列最小值中的最大值，若輸入為空白鍵，則輸入結束。
程式要求：將整體工作拆為小工作項目，再以方法(副程式)的方式處理各小工作項目。
輸入格式：
a11 a12 a13 … (第一列各元素的值，各數字以一個空白鍵間隔)
a21 a22 a23 a24 … (第二列的數字，各數字以一個空白鍵間隔)
… … … …
… … … …
an1 an2 an3 … (第n 列的數字，各數字以一個空白鍵間隔)
輸出格式：
第1列最小值為 xx
第2列最小值為 yy
… … … …
… … … …
第n列最小值為 zz
各列最小值中的最大值為 mm
輸入範例：
2 5 -1
13 2 6 8
7 7
(空白鍵)
輸出範例：
第1列最小值為 -1
第2列最小值為2
第3列最小值為7
各列最小值中的最大值為7
--------------------------------------------------
#任意個文字列轉成整數列
def StrToIntLst(x):
#x="1 2 3^4 5^6^" ==> strLst[['1', '2', '3'], ['4', '5'], ['6']]
strLst=[]
for i in (x[:-1].split('^')):
strLst.append(i.split(' '))
#strLst[['1', '2', '3'], ['4', '5'], ['6']] ==> [[1, 2, 3], [4, 5], [6]]
intLst=[]
for i in range(len(strLst)):
intLst.append([int(j) for j in strLst[i]])
return intLst
'''輸入任意個文字列'''
tmpS=""
while True:
x=input("數字間隔，空白鍵，Enter換行。只按空白鍵，再Enter離開，請輸入：")
if x==' ':break
tmpS=tmpS+x+'^'
Lst=StrToIntLst(tmpS)
print("輸入原數列:",Lst)
#數列 list 找最大值、最小值使用 python 內建函式 Built In Function
AllMinsLst=[]
for i in range(len(Lst)):
AllMinsLst.append(min(Lst[i]))
print("第 ",i+1," 列最小值為: ",min(Lst[i]))
print("各列最小值中的最大值為: ",max(AllMinsLst) )
=========
數字間隔，空白鍵，Enter換行。只按空白鍵，再Enter離開，請輸入：2 5 -1
數字間隔，空白鍵，Enter換行。只按空白鍵，再Enter離開，請輸入：13 2 6 8
數字間隔，空白鍵，Enter換行。只按空白鍵，再Enter離開，請輸入：7 7
數字間隔，空白鍵，Enter換行。只按空白鍵，再Enter離開，請輸入：
輸入原數列: [[2, 5, -1], [13, 2, 6, 8], [7, 7]]
第 1 列最小值為: -1
第 2 列最小值為: 2
第 3 列最小值為: 7
各列最小值中的最大值為: 7
從 console 中輸入一個目錄，列印出該目錄中所有的檔案與子目錄，
如果該目錄中有子目錄，須進入各個子目錄，依同樣方式遞迴印出結
果，每層子目錄列印時再內縮 3 個空格。如果為目錄，在該目錄後加
上(dir)。
file_arch 的目錄結構壓縮檔請參考老師檔案分享區的 file_arch.rar
註：如果參考老師上課範例，請加上註解。
file_arch 的目錄結構壓縮檔請參考老師檔案分享區的 file_arch.rar
以 D:/file_arch 目錄為例，印出的結果如下；
--------------------------------------------------
import os
def FileArch(x):
for i in os.listdir(x):
if os.path.isdir(x+"/"+i):
'''
如果是目錄，遞迴 Recursive 往下探究是否還有下層
x="D:/file_arch/Dir1"
os.path.abspath(x) ==> 'D:\\file_arch\\Dir1'
os.sep ==> '\\'
os.path.abspath(x+"/"+i).count(os.sep) 統計 '\\' 數量，即此檔案、目錄在第幾層
依題意，從第3層起，依次給予一組3個空白建，再開始 print
'''
print(" "*(os.path.abspath(x+"/"+i).count(os.sep)-2),end='')
print(i,"(dir)")
FileArch(x+"/"+i)
else:
print(" "*(os.path.abspath(x+"/"+i).count(os.sep)-2),end='')
print(i)
strInput=input("輸入查詢的目錄路徑：D:/file_arch") or "D:/file_arch"
Arch=FileArch(strInput)
=========
輸入查詢的目錄路徑：D:/file_arch
A.txt
B.txt
C.txt
Dir1 (dir)
A1.txt
B1.txt
C1.txt
D1.txt
Dir11 (dir)
Dir111 (dir)
A111.txt
B111.txt
Dir2 (dir)
A2.txt
B2.txt
Dir3 (dir)
A3.txt
B3.txt
C3.txt
從 console 中輸入一串整數，整數間以一個空格隔開，最後一個整數
為控制訊號，如果控制訊號
為 1，則輸出該串整數的最小公倍數 LCM (不含最後一個當控制
訊號的整數)
為 2，則輸出該串整數的最大公因數 GCD (不含最後一個當控制
訊號的整數)
範例 1
輸入
2 4 6 12 1
輸出
12
範例 2
輸入
2 4 6 12 2
輸出
2
註：
1、 找最小公倍數及最小值及最大公因數，請分別用二個副程式(方
法/函式)實作。
2、 假設輸入的值都是正確，不須做防錯處理
--------------------------------------------------
def twoGCD(x,y):
if x<y:x,y=y,x
if x%y==0:
return y
else:
return twoGCD(y,x%y)
def moreGCD(x):
tmpG=twoGCD(x[0],x[1])
for i in range (2,len(x)):
tmpG=twoGCD(tmpG,x[i])
return tmpG
#多個數求GCD，兩兩依序找出GCD，最後即所求
def twoLCM(x,y):
return x*y//twoGCD(x,y)
def moreLCM(x):
tmpL=twoLCM(x[0],x[1])
for i in range(2,len(x)):
tmpL=twoLCM(tmpL,x[i])
return tmpL
#多個數求LCM，兩兩依序找出LCM，最後即所求
InputStr=input("<Space>隔開、<Enter>離開。\n最後一碼控制符:\n1:求LCM\n2:求GCD。\n請輸入任意個整數串列：")
Lst=[]
Lst=[int(i) for i in InputStr.split(' ')]
#Lst=[12, 15, 18, 2]
if Lst[-1]==1:
print("LCM:",moreLCM(Lst[:-1]))
elif Lst[-1]==2:
print("GCD:",moreGCD(Lst[:-1]))
#自己測試用
else:
print("LCM:",moreLCM(Lst[:-1]))
print("GCD:",moreGCD(Lst[:-1]))
=========
<Space>隔開、<Enter>離開。
最後一碼控制符:
1:求LCM
2:求GCD。
請輸入任意個整數串列：2 4 6 12 1
LCM: 12
=========
<Space>隔開、<Enter>離開。
最後一碼控制符:
1:求LCM
2:求GCD。
請輸入任意個整數串列：2 4 6 12 2
GCD: 2
使用 Python 的 collections.deque 設計一個 Queue，並從螢幕上輸入
a: 加入目前時間字串到 Queue
r: 移除一個時間字串
c: 清除 Queue 上所有的時間字串
s: 顯示 Queue 裡面的所有物件
q: 離開系統，並出現 bye! 字樣
系統必須具有防呆機制，避免使用者錯誤輸入，例如：Queue 沒有時
間字串，但使用者輸入 r 時，必須有提示機制。
--------------------------------------------------
from collections import deque
from datetime import *
def add(queue, object):
queue.append(object)
print("adding: ", object)
def remove(queue):
print("removing: ", queue.popleft())
# main
queue = deque()
while True:
action = input('key in the action: a: add; r: remove; c: clear; s: show all; q: quit ')
print()
if action == 'a':
add(queue, datetime.now().strftime('%Y-%m-%d %H:%M:%S'))
elif action == 'r':
if (len(queue) == 0):
print('Queue 裡面已經沒有物件了，請先加入一個時間物件')
continue
remove(queue)
elif action == 'c':
queue.clear()
elif action == 's':
for i in queue:
print(i)
elif action == 'q':
print("bye!")
break
=========
key in the action: a: add; r: remove; c: clear; s: show all; q: quit a
adding: 2021-10-26 15:56:45
key in the action: a: add; r: remove; c: clear; s: show all; q: quit a
adding: 2021-10-26 15:56:57
key in the action: a: add; r: remove; c: clear; s: show all; q: quit s
2021-10-26 15:56:45
2021-10-26 15:56:57
key in the action: a: add; r: remove; c: clear; s: show all; q: quit r
removing: 2021-10-26 15:56:45
key in the action: a: add; r: remove; c: clear; s: show all; q: quit s
2021-10-26 15:56:57
key in the action: a: add; r: remove; c: clear; s: show all; q: quit c
key in the action: a: add; r: remove; c: clear; s: show all; q: quit s
key in the action: a: add; r: remove; c: clear; s: show all; q: quit q
bye!
dict
--------------------------------------------------
dic ={'1' :'1', '2': '4', '3':'9'}
k1 = dic.keys()
print('==== keys =======')
for i in k1:
print(i)
v1 = dic.values()
print('==== values =======')
for i in v1:
print(i)
print('==== items =======')
i1 = dic.items()
for i in i1:
print(i)
print('=== is a key in a dict ? ========')
print('1' in dic)
print('2' in dic)
print('3' in dic)
print('4' in dic)
print('9' in dic)
dic2 = {'1':'10000', '4':'16', '5': '25'}
dic.update(dic2)
print('=== update 1: by another dict ====')
i1 = dic.items()
for i in i1:
print(i)
for i in range(6, 11):
dic.update({str(i):str(i*i)})
print('===== update 2: by a for loop ======')
i1 = dic.items()
for i in i1:
print(i)
=========
==== keys =======
1
2
3
==== values =======
1
4
9
==== items =======
('1', '1')
('2', '4')
('3', '9')
=== is a key in a dict ? ========
True
True
True
False
False
=== update 1: by another dict ====
('1', '10000')
('2', '4')
('3', '9')
('4', '16')
('5', '25')
===== update 2: by a for loop ======
('1', '10000')
('2', '4')
('3', '9')
('4', '16')
('5', '25')
('6', '36')
('7', '49')
('8', '64')
('9', '81')
('10', '100')
tulpe
--------------------------------------------------
t = (1, 3, 5, 6, 10, 2)
print(t[1])
for i in t:
print(i)
t1 = tuple([1, 2, 3])
print('---------------')
for i in t1:
print(i)
print('---------------')
t2 = tuple('hello')
for i in t2:
print(i)
# compared with list
print('----- original list ----------')
t3 = list([1, 2, 3, 4])
for i in t3:
print(i)
t3[1] = 5
print('-----after changing the value t3[1] in the list----------')
for i in t3:
print(i)
=========
3
1
3
5
6
10
2
---------------
1
2
3
---------------
h
e
l
l
o
----- original list ----------
1
2
3
4
-----after changing the value t3[1] in the list----------
1
5
3
4
set
--------------------------------------------------
s1 ={1, 2, 3}
s2 = set()
s2= {1, 2, 4}
#s1.add(5)
#s1.add('5')
for i in s1:
print(i)
print('intersection')
s3 = s1.intersection(s2)
for i in s3:
print(i)
print('union')
s4 = s1.union(s2)
for i in s4:
print(i)
print('difference in s1but not in s2')
s5 = s1.difference(s2)
for i in s5:
print(i)
print('difference in s2 but not in s1')
s6 = s2.difference(s1)
for i in s6:
print(i)
=========
1
2
3
intersection
1
2
union
1
2
3
4
difference in s1but not in s2
3
difference in s2 but not in s1
4
recursion1
--------------------------------------------------
# 簡單階乘範例
def factorial(n):
if n <= 1:
return 1
return n * factorial(n-1)
result = factorial(5)
print(result)
=========
120
