| 例1： 求第n个斐波拉契的值 | 例2： 一共n级楼梯，每次你只能爬1级或者2级，那么你有多少种爬到楼顶的方法 | 例3：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月每个月又生一对兔子，假设兔子都不死， 计算第十个月兔子的总数？ | |||
| 递归 |
def fib_test(k):
if k==1:
return 0 if k==2: return 1 else: return fib_test(k-2)+fib_test(k-1) |
if n in [1,2]: f(n) =f(n-1)+f(n-2) |
|||
| 二分法： |
非递归方式实现：
test_list = [1,5,8,10,13,15,23,34,40,50,55,65,70,75,80,86,89,90]
def search(data_list,target):
s_list = data_list p_target =0 while True: mid = len(s_list)//2 print ("s_list:", s_list) print ("mid:",mid) if s_list[mid] == target: p_target = data_list.index(s_list[mid]) break elif s_list[mid]>target: s_list = s_list[:mid] elif s_list[mid]<target: s_list = s_list[mid+1:] else: if len(s_list) == 1: print ("not find the target") break return p_target print ("search(data_list, target):", search(test_list, 1)) |
用递归的方式： print ("**************递归二分查找***************************************")
def search2(left,right, data_list, target):
if left > right: return -1 mid = (left+right)//2 if data_list[mid] == target: return mid elif data_list[mid]<target: return search2(mid+1, right,data_list, target) else: return search2(left, mid-1,data_list, target) |
|||
| 汉诺塔 | |||||
| 八皇后问题 | |||||
| 全排列 | |||||
| 数字拆分算法 | |||||