遞歸與二分法
- 2020 年 1 月 20 日
- 筆記
遞歸
自己調用自己
遞歸的入口(參數)和出口(return)
樹狀結構的遍歷
import os def func(lujing, n): # "d:/a/" lst = os.listdir(lujing) # 打開文件夾. 列出該文件夾內的所有文件名 for el in lst: # el是文件的名字. b, c path = os.path.join(lujing, el) # 還原文件路徑"d:/a/b" if os.path.isdir(path): # 判斷路徑是否是文件夾 print("..." * n,el) # 顯示文件夾的名字 func(path, n + 1) # 在來一次 else: print("t" * n,el) # 顯示文件 func("d:/a", 0)
二分法
掐頭結尾取中間
查找效率非常的高
不使用遞歸進行二分法
lst = [1,3,5,7,12,36,68,79,132,345,567] n = int(input("請輸入一個數")) left = 0 right = len(lst) - 1 while left <= right: mid = (left + right)//2 if n > lst[mid]: left = mid + 1 elif n < lst[mid]: right = mid - 1 else: print("存在") break else: print("不存在")
用遞歸進行二分法的兩種方法
1)第一種
def func(n, lst): left = 0 right = len(lst) - 1 if lst != []: mid = (left + right)//2 if n > lst[mid]: func(n, lst[mid+1:]) # 改變列表 elif n < lst[mid]: func(n, lst[:mid]) else: print("找到了") return else: print("沒找到") return n = int(input("請輸入你要查找的數:")) func(n, [1,3,5,7,12,36,54,68,79,85,92,106])
2)第二種
def func(n, lst, left, right): if left <= right: mid = (left + right) // 2 if n > lst[mid]: left = mid + 1 return func(n, lst, left, right) elif n < lst[mid]: right = mid - 1 return func(n, lst, left, right) # 遞歸如果有返回值. 所有調用遞歸的地方必須寫return else: print("找到了") return mid # 返回上一個調用函數的值 else: print("找不到") return False n = int(input("請輸入你要查找的數:")) lst = lst = [1,3,5,7,12,36,68,79,125,343,485,875,1948] ret = func(n, lst, 0, len(lst)-1) print(ret)
