一、遞回
遞回特點：1、呼叫自己 2、結束條件
代碼示例
1 # 先遞回后列印，會先列印最底層的數
2 def func(x):
3 if x>0:
4 func(x - 1)
5 print(x)
6 func(3)
7 # 先列印后遞回，先列印最外層的數
8 def func2(x):
9 if x>0:
10 print(x)
11 func2(x - 1)
12 func2(3)
運行截圖
1、遞回案例——漢諾塔
代碼
1 # 假設有n個盤子，把除了底下最大的盤子之外的盤子視為n-1個
2 # 1、把n-1個盤子從a經過c移動到b
3 # 2、把第n個盤子從a移動到c
4 # 3、把n-1個盤子從b經過a移動到c
5
6 # 移動次數遞推式 h(x)=2h(x-1)+1
7 def hanoi(n,a,b,c):
8 if n>0:
9 hanoi(n-1,a,c,b)
10 print("move from %s to %s"%(a,c))
11 hanoi(n-1,b,a,c)
12 hanoi(3,'A','B','C')
運行截圖
二、順序（線性）查找
代碼示例
1 # li表示要查找的串列，va表示所要查找的值
2 # 利用enumerate列舉函式列出串列li的每個元素下標key，值val
3 # 如果值val與所要查找的值va相等則把下標key加到new_li陣列中，沒有就回傳空陣列
4 def linear_search(li,va):
5 new_li=[]
6 for key,val in enumerate(li):
7 if val==va:
8 new_li.append(key)
9 return new_li
10 li=[12,23,34,56,45,67,13,32,13,48]
11 print(linear_search(li,13))
運行截圖
三、二分查找
代碼
1 def binary_search(li,va): # li為待查找的串列（已經排好順序），va為待查找的值
2 left=0 # 左邊界
3 right=len(li)-1 # 右邊界
4 while left<=right: # 候選區有值就回圈
5 mid=(left+right)//2
6 if li[mid]==va: # 中間值與待查找的值相等，則直接回傳中間值下標
7 return mid
8 elif li[mid]>va: # 中間值比待查找的值大，則把中間值下標減1賦值給右邊界
9 right=mid-1
10 else: # li[mid]<va 中間值比待查找的值小，則把中間值下標加1賦值給左邊界
11 left=mid+1
12 else:
13 return None # 找不到值回傳None
14 li=[1,2,3,4,5,6,7,8,9]
15 print(binary_search(li,3))
運行截圖
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/469841.html
標籤：其他