1、算法
英文名：algorithm，就是计算的方法。
# 是截止到目前，人类发现的针对特定场景的，最优的计算方法。是人类智慧的结晶。
# 人脑是复杂的，电脑其实很简单。比如： 999 * 123 人类会将其变为： 1000 * 123 - 123 这样就好算多了，可是电脑不会如此，只会硬算！
学习算法的目的
# 我们学习的算法 都是过去时
# 了解基础的算法 才能创造出更好的算法
# 不是所有的事情都能套用现成的方法解决的
# 有些时候会用到学过的算法知识来解决新的问题
2、递归
1)、楔子
有如下例子：
从前有座山，山上有个庙；庙里有两个和尚，一个老和尚跟一个小和尚。一天，老和尚跟小和尚讲故事：
"从前有座山，山上有个庙；庙里有两个和尚，一个老和尚跟一个小和尚。一天，老和尚跟小和尚讲故事：
'从前有座山，山上有个庙；庙里有两个和尚，一个老和尚跟一个小和尚。一天，老和尚跟小和尚讲故事：
.............................
# 看到这个例子，有何感想？这不是车轱辘话码，自己说自己！
# 这就对了，我们就正式引入递归！
2）、递归函数的定义
在函数中，自己调用自己的函数，叫递归函数。
depth = 0
def temple_story():
global depth
print('从前有座山，山上有个庙；庙里有两个和尚，一个老和尚跟一个小和尚。一天，老和尚跟小和尚讲故事:')
depth += 1
print(depth)
temple_story() #temple_story() #会报告超过最大递归深度的错误！
# 报错：RecursionError: maximum recursion depth exceeded while calling a Python object # 我们来看看这个深度是多少？添加计数，发现是997次！
# 这个最大递归次数是python定义的，可以改，但建议如此做，因为递归如此多，还解决不了，就说明不适合用递归解决！
import sys
print("最大递归深度是：", sys.getrecursionlimit()) #
sys.setrecursionlimit(50000) #temple_story() # 没有报告错误！执行到3806次就没打印了（并且退出了函数），说明有东西限制了继续递归！
3）、递归的小结
# 如果递归次数太多，就不适合使用递归来解决问题
# 递归的缺点 ： 占内存
# 递归的优点： 会让代码变简单
4）、应用场景1：询问年龄
'''
# alex 多大 n = 1 age(1) = age(2)+2 = age(n+1) + 2
# alex比egon大两岁
# egon多大？ n = 2 age(2) = age(3) + 2 = age(n+1) +2
# egon比tom大两岁
# tom多大 n = 3 age(3) = age(4) + 2 = age(n+1) +2
# tom比king大两岁
# king多大？
# king40了 n = 4 age(4) = 40
'''
def ask_age(n):
'''
问年龄，
:param n:被询问的序号
:return: age
'''
if n == 4:
return 40
elif 0 < n < 4:
return ask_age(n + 1) + 2
print('I am ', ask_age(3)) # # 教你看递归 递的是n，归的是return的值
# def ask_age(1):
# if 1 == 4:
# return 40
# elif 1 > 0 and 1 < 4:
# return 46
#
# def ask_age(2):
# if 2 == 4:
# return 40
# elif 2 >0 and 2 < 4:
# age(3) + 2 None +2
#
# def ask_age(3):
# if 3 == 4:
# return 40
# elif 3 >0 and 3 < 4:
#
#
# def ask_age(4):
# if 4 == 4:
# return 40
# elif n >0 and n < 4:
# age(n+1) + 2
3、二分法 （dichotomy），必须处理有序的列表
# 使用实例：使用二分法查找数列中有没有66，并返回其索引。
num_li = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88] # 没接触二分法之前，我们大概会用for循环遍历数列，判断其中元素是否是66，如果是返回其索引！
# 但是，想一想，如果此数列有几百万个元素，这样遍历会很慢，如何查找最快？答案是：二分法
# 第一次，找到数列最中间的元素，比较它和66的大小，如果大于66，就说明66在它前面，前面的数又组成一个数列num_li_new_1,
# 如果它比66小，则说明66在它的后面，将其后面的数，组成一个新的数列：num_li_new_2
# 第二次，在num_li_new_1或者num_li_new_2中，继续按照第一的方法寻找下去。。。。。。
# 第n次，如果有该元素，一定会找到它，而且只有一个元素了！ #1）、第一次尝试用二分法
def find_num(list, target):
mid_index = len(list)//2
if list[mid_index] == target:
print('Congratunation! You get it!')
return mid_index
elif list[mid_index] > target:
new_list = list[:mid_index]
find_num(new_list, target)
else:
new_list = list[mid_index + 1:]
find_num(new_list, target) res = find_num(num_li, 67)
print(res) # 惊奇的发现，打印的结果是：None
# 分析未得到预想结果的原因: todo:没有接收返回值，也没有返回任何值！ 所以为None
def find_num(list, target): # 第一步：list=num_li target = 67
mid_index = len(list) // 2 # 第二步：mid_index = 24//2 = 12
if list[mid_index] == target: # list[mid_index] = list[12] = 41
print('Congratunation! You get it!')
return mid_index
elif list[ mid_index ] > target:
new_list = list[ :mid_index ]
find_num(new_list, target)
else: #第三步：41 < 67
new_list = list[ mid_index + 1: ] # 第四步：new_list = list[13:] = [42,43,55,56,66,67,69,72,76,82,83,88]
find_num(new_list, target) # 第五步：find_num(new_list, 67)todo:没有接收返回值，也没有返回任何值！ def find_num(list, target): # 第六步：list=new_list target = 67
mid_index = len(list) // 2 # 第七步：mid_index = 12//2 = 6
if list[mid_index] == target: # list[mid_index] = list[6] = 69
print('Congratunation! You get it!')
return mid_index
elif list[ mid_index ] > target: # 第八步：69 > 67
new_list = list[ :mid_index ] # 第九步：new_list = list[:6] = [42,43,55,56,66,67]
find_num(new_list, target) # 第十步：find_num(new_list, 67) todo:没有接收返回值，也没有返回任何值！
else:
new_list = list[ mid_index + 1: ] #
find_num(new_list, target) # def find_num(list, target): # 第十一步：list=new_list target = 67
mid_index = len(list) // 2 # 第十二步：mid_index = 6//2 = 3
if list[mid_index] == target: # list[mid_index] = list[3] = 56
print('Congratunation! You get it!')
return mid_index
elif list[ mid_index ] > target: #
new_list = list[ :mid_index ]
find_num(new_list, target) # 第十步：find_num(new_list, 67)
else: # 第十三步：56 < 67
new_list = list[mid_index + 1:] # 第十四步：new_list = list[4:] = [66,67]
find_num(new_list, target) # 第十五步： find_num(new_list, 67) todo:没有接收返回值，也没有返回任何值！ def find_num(list, target): # 第十六步： list=new_list target = 67
mid_index = len(list)//2 # 第十七步：mid_index = 2//2 = 1
if list[mid_index] == target: # 第十八步：list[mid_index] = list[1] = 67 正好相等！
print('Congratunation! You get it!') # 第十九步：输出Congratunation! You get it!
return mid_index # 第二十步：将mid_index = 1 todo 返回给调用该函数的地方：即第十五步
elif list[mid_index] > target:
new_list = list[:mid_index]
find_num(new_list, target)
else:
new_list = list[mid_index + 1:]
find_num(new_list, target) #2）、第二次尝试用二分法 def find_num(list, target):
mid_index = len(list)//2
if list[mid_index] == target:
print('Congratunation! You get it!')
return mid_index
elif list[mid_index] > target:
new_list = list[:mid_index]
return find_num(new_list, target)
else:
new_list = list[mid_index + 1:]
return find_num(new_list, target) res = find_num(num_li, 67)
print(res) # 继续惊奇的发现，结果是：0，这并不是我们预想的结果！
# 原因分析：索引乱了，我们切分数列后，用的是新的索引！ # 3）、第三次尝试用二分法 #def find_num(list, target, start = 0, end = len(list)): #TypeError: object of type 'type' has no len()
def find_num(list, target, start = 0, end = None):
end = len(list) if end is None else end
# mid_index = len(list)//2 # 有时会报错：IndexError: list index out of range
mid_index = (end - start)//2 + start #
if list[mid_index] < target:
#new_list = list[ mid_index + 1:end ] # 加start和end后，不用传了，否者列表会越界！
return find_num(list, target, start=mid_index + 1, end=end)
elif list[mid_index] > target:
#new_list = list[start:mid_index]
return find_num(list, target, start=start, end=mid_index)
else:
print('Congratunation! You get it!')
return mid_index res = find_num(num_li, 66)
print(res) # 结果是出现了，还发现一个问题，如果查找的数不在列表中，会报错：RecursionError: maximum recursion depth exceeded in comparison # 4、第四次
def find_num(list, target, start = 0, end = None):
end = len(list) if end is None else end
if end > start:
mid_index = (end - start)//2 + start #
if list[mid_index] < target:
return find_num(list, target, start=mid_index + 1, end=end)
elif list[mid_index] > target:
return find_num(list, target, start=start, end=mid_index)
else:
print('Congratunation! You get it!')
return mid_index
else:
return '该数列中没有你找的数！' res = find_num(num_li, 44)
print(res)