算法
二分查找
def binary_search(list,item):
low =0
high = len(list)-1
while(low<=high):
mid = (low + high)//2
guess = list[mid]
if guess == item:
return mid
if guess < item:
high = mid-1
else:
low = mid+1
return None
l = [2,4,6,8,10]
x = binary_search(l,6)
if x==None:
print("列表中無此數(shù)")
else:
print('此數(shù)在列表中的第%s位'%x)
運行結(jié)果
此數(shù)在列表中的第2位
選擇排序
#選擇排序
def findSmallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1, len(arr)):
if arr[i]<smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
l = [6,8,7,9,0,1,3,2,4,5]
print(selectionSort(l))
運行結(jié)果
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
快速排序
def quicksort(arr):
if len(arr)<2:
return arr
left = []
right =[]
pivot = arr[0]
for i in range(1,len(arr)):
if arr[i]<pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quicksort(left) + [pivot] +quicksort(right)
a = quicksort([6,8,7,9,0,1,3,2,4,5])
print(a)
def quicksort(arr):
if len(arr) < 2:
return arr
else:
pivot = arr[0]
less = [i for i in arr[1:] if i <=pivot]
greater = [i for i in arr[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
運行結(jié)果
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
廣度優(yōu)先搜索
#實現(xiàn)圖
graph = {}
graph["you"] = ["alice","bob","claire"]
graph["bob"] = ["anuj","peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom","jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
#創(chuàng)建一個隊列
from collections import deque
search_queue = deque() #創(chuàng)建一個隊列
search_queue +=graph["you"] #將你的鄰居都加入到這個搜索隊列中
#廣度優(yōu)先搜索
def bfsearch(name):
search_queue = deque()
search_queue += graph[name]
searched = [] #該列表用于記錄檢查過的人
while search_queue:
person = search_queue.popleft()
if not person in searched: #僅當這個人沒檢查過時才檢查
if person_is_seller(person):
print(person + " is a mango seller!")
return True
else:
search_queue += graph[person]
searched.append(person) #將這個人標記為檢查過
return False
def person_is_seller(name):
return name[-1] == 'm'
bfsearch("you")
運行結(jié)果
thom is a mango seller!
深度優(yōu)先搜索
#圖
graph = {}
graph["you"] = ["alice","bob","claire"]
graph["bob"] = ["anuj","peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom","jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
#棧類
class SStack(): #基于順序表技術(shù)實現(xiàn)的棧類
def __init__(self): #用list對象_elems存儲棧中元素
self._elems = []
def is_empty(self):
return self._elems == []
def top(self):
if self._elems == []:
print("棧為空")
return self._elems[-1]
def push(self,elem):
self._elems.append(elem)
def pop(self):
if self._elems == []:
print("棧為空")
return self._elems.pop()
st1 = SStack()
#深度優(yōu)先搜索
def person_is_seller(name):
return name[-1] == 'm'
def dfsearch(name):
st = SStack()
searched = []
if graph[name]!=[]:
for i in graph[name]:
st.push(i)
while not st.is_empty():
person = st.pop()
if not person in searched:
if person_is_seller(person):
print(person + " is a mango seller!")
return True
searched.append(person)
if graph[person]!=[]:
for j in graph[person]:
st.push(j)
return False
dfsearch("you")
#棧實現(xiàn)深度優(yōu)先遍歷
def dfsearch1(name):
st = SStack()
searched = []
print(name)
if graph[name]!=[]:
for i in graph[name]:
st.push(i)
while not st.is_empty():
person = st.pop()
if not person in searched:
print(person)
searched.append(person)
if graph[person]!=[]:
for j in graph[person]:
st.push(j)
dfsearch1("you")
運行結(jié)果
thom is a mango seller!
you
claire
jonny
thom
bob
peggy
anuj
alice
狄克斯特拉算法
#狄克斯特拉算法
#表示整個圖的散列表
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = {}
#創(chuàng)建開銷表
infinity = float('inf')
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
#創(chuàng)建存儲父節(jié)點的散列表
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
#存儲處理過的節(jié)點
processed = []
def find_lowest_cost_node(costs):
lowest_cost = float('inf')
lowest_cost_node = None
for node in costs: #遍歷所有節(jié)點
cost = costs[node]
if cost < lowest_cost and node not in processed: #如果當前節(jié)點的開銷更低且位處理過
lowest_cost = cost #就將其視為開銷最低的節(jié)點
lowest_cost_node = node
return lowest_cost_node
node = find_lowest_cost_node(costs) #在未處理的節(jié)點中找出開銷最小的節(jié)點
while node is not None:
print(node)
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys(): #遍歷當前節(jié)點的所有鄰居
new_cost = cost + neighbors[n]
if costs[n]>new_cost: #如果經(jīng)當前節(jié)點千萬該鄰居更近
costs[n]=new_cost #就更新該鄰居的開銷
parents[n]=node #同時將該鄰居的父節(jié)點設(shè)置為當前節(jié)點
processed.append(node) #將當前節(jié)點標記為處理過
node = find_lowest_cost_node(costs) #找出接下來要處理的節(jié)點，并循環(huán)
運行結(jié)果
b
a
fin
貪婪算法
#創(chuàng)建一個列表，其中包含要覆蓋的州
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca","az"]) #轉(zhuǎn)換成集合
#可供選擇地廣播臺清單
stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])
#創(chuàng)建一個集合來存儲最終選擇地廣播臺
final_stations = set()
while states_needed:
best_station = None
states_covered = set() #包含該廣播臺覆蓋的所有未覆蓋的州
for station, states_for_station in stations.items():
covered = states_needed & states_for_station #計算交集
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
states_needed -= states_covered
final_stations.add(best_station)
print(final_stations)
運行結(jié)果
{'kfive', 'kthree', 'ktwo', 'kone'}
