博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
python--递归、二分查找算法
阅读量:4592 次
发布时间:2019-06-09

本文共 3616 字,大约阅读时间需要 12 分钟。

                                递归

初识递归

递归的定义——在一个函数里再调用这个函数本身

现在我们已经大概知道刚刚讲的story函数做了什么,就是在一个函数里再调用这个函数本身,这种魔性的使用函数的方式就叫做递归

刚刚我们就已经写了一个最简单的递归函数。

递归的最大深度——997

正如你们刚刚看到的,递归函数如果不受到外力的阻止会一直执行下去。但是我们之前已经说过关于函数调用的问题,每一次函数调用都会产生一个属于它自己的名称空间,如果一直调用下去,就会造成名称空间占用太多内存的问题,于是python为了杜绝此类现象,强制的将递归层数控制在了997(只要997!你买不了吃亏,买不了上当...).

 

 递归函数与三级菜单

 menu = { '北京': { '海淀': { '五道口': { 'soho': {}, '网易': {}, 'google': {} }, '中关村': { '爱奇艺': {}, '汽车之家': {}, 'youku': {}, }, '上地': { '百度': {}, }, }, '昌平': { '沙河': { '老男孩': {}, '北航': {}, }, '天通苑': {}, '回龙观': {}, }, '朝阳': {}, '东城': {}, }, '上海': { '闵行': { "人民广场": { '炸鸡店': {} } }, '闸北': { '火车战': { '携程': {} } }, '浦东': {}, }, '山东': {}, }

 

1 def threeLM(dic):

2 while True:

3 for k in dic:print(k)

4 key = input('input>>').strip()

5 if key == 'b' or key == 'q':return key

6 elif key in dic.keys() and dic[key]:

7 ret = threeLM(dic[key])

8 if ret == 'q': return 'q'

9 elif (not dic.get(key)) or (not dic[key]) :

10 continue

11

12 threeLM(menu)

 

 二分法

 

l = [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]

你观察这个列表,这是不是一个从小到大排序的有序列表呀?

如果这样,假如我要找的数比列表中间的数还大,是不是我直接在列表的后半边找就行了?

 

这就是二分查找算法

贴上两段代码:

一:简单二分法

l = [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]

def func(l,aim):

mid = (len(l)-1)//2

if l:

  if aim > l[mid]:

    func(l[mid+1:],aim)

  elif aim < l[mid]:

    func(l[:mid],aim)

  elif aim == l[mid]:

    print("bingo",mid)

  else: print('找不到')

func(l,66)

func(l,6)

 

二:

  升级版二分法

def func(l, aim,start = 0,end = len(l)-1 ):

  mid = (start+end)//2

  if not l[start:end+1]:

    return

  elif aim > l[mid]:

    return func(l,aim,mid+1,end)

  elif aim < l[mid]:

    return func(l,aim,start,mid-1)

  elif aim == l[mid]:

    print("bingo")

  return mid

index = func(l,68)

print(index)

      

 

 

 

 

 

 

 

 

 

 

#递归解决的问题 #就是通过参数,来控制每一次缩小计算的规模 #适合的场景:数据的规模在减小 解决问题的思路在改变 #总结:结束递归的标志:return #用处:未来遇到很多递归的地方,算法(排序算法,金融类) 9 #递归函数:在一个函数里调用自己 #最大递归层数做了一个限制:997 #最大层数限制是python默认的。可以做修改 #但是不建议修改 #import sys #所以和python相关的设置和放到 # def a(): # print("ff") # a() # a() # # import sys # sys.setrecursionlimit(10000000) # n =1 # def a(): # global n # n += 1 # # print("ff") # print(n) # a() # a() # def age(n): # if n == 1: # return 40 # else: # ret = age(n-1) # return ret + 2 # print(age(5)) # def age(5): # if 5 == 1: # return 40 # else: # ret = 46 # return ret + 2 # # def age(4): # if 5 == 1: # return 40 # else: # ret = 44 # return ret + 2 # # def age(3): # if 5 == 1: # return 40 # else: # ret = 42 # return 44 # # def age(2): # if 5 == 1: # return 40 # else: # ret = 40 # return 42 # # def age(1): # if 5 == 1: # return 40 #age(1) == 40 # # l = [1,2,3,4,5,6,7,8,9,10,11,12,23,45,67,89,100] # def find(l,aim): # mid = len(l)//2 # if l[mid] > aim: # ll=l[:mid] # return find(ll,aim) # elif l[mid] < aim: # ll= l[mid+1:] # return find(ll,aim) # else: # return l.index(aim) # print(find(l,11)) # # def a(num): # if num %2.2 == 0: # num = num // 2 # return a(num) # else: # return num # print(a(8.8)) menu = { '北京': { '海淀': { '五道口': { 'soho': {}, '网易': {}, 'google': {} }, '中关村': { '爱奇艺': {}, '汽车之家': {}, 'youku': {}, }, '上地': { '百度': {}, }, }, '昌平': { '沙河': { '老男孩': {}, '北航': {}, }, '天通苑': {}, '回龙观': {}, }, '朝阳': {}, '东城': {}, }, '上海': { '闵行': { "人民广场": { '炸鸡店': {} } }, '闸北': { '火车战': { '携程': {} } }, '浦东': {}, }, '山东': {},}# def ak(men):# while True:# for key in men:# print(key)# k = input("input>>>")# return ak(men[k])# print(ak(menu))# def ak(men):# # print("大区信息")# while True:# for key in men:# print(key)# k = input("input(quit或者exit退出)>>>")# if k =="quit" or k == "exit":# return k# else:# return ak(men[k])# print(ak(menu))#

转载于:https://www.cnblogs.com/DE_LIU/p/7264959.html

你可能感兴趣的文章
P1382 楼房 set用法小结
查看>>
分类器性能度量
查看>>
docker 基础
查看>>
写一个bat文件,删除文件名符合特定规则,且更改日期在某
查看>>
我的友情链接
查看>>
写Use Case的一种方式,从oracle的tutorial抄来的
查看>>
【C#】protected 变量类型
查看>>
Ubuntu解压
查看>>
爬虫_房多多(设置随机数反爬)
查看>>
藏地密码
查看>>
爬虫去重(只是讲了去重的策略,没有具体讲实现过程,反正就是云里雾里)...
查看>>
react中将px转化为rem或者vw
查看>>
8816
查看>>
avcodec_open2()分析
查看>>
何如获取单选框中某一个选中的值
查看>>
paip.输入法编程----删除双字词简拼
查看>>
QQ悬浮返回顶部
查看>>
MySQL建表语句的一些特殊字段
查看>>
《Unix环境高级编程》读书笔记 第8章-进程控制
查看>>
腾讯前端二面题目详解
查看>>