歡迎加入QQ討論群258996829
麥子學(xué)院 頭像
蘋(píng)果6袋
6
麥子學(xué)院

python函數(shù):遞歸函數(shù)及二分查找算法

發(fā)布時(shí)間:2017-08-04 17:49  回復(fù):0  查看:3031   最后回復(fù):2017-08-04 17:49  

本文和大家分享的主要是python的遞歸函數(shù)及二分查找算法相關(guān)內(nèi)容,一起來(lái)看看吧,希望對(duì)大家學(xué)習(xí)python有所幫助。

  一、遞歸的定義

  def story():

  s = """

  從前有個(gè)山,山里有座廟,廟里老和尚講故事,

  講的什么呢?

  """

  print(s)

  story()

  story()

  老和尚講故事

  遞歸的定義 —— 在一個(gè)函數(shù)里再調(diào)用這個(gè)函數(shù)本身。這種魔性的使用函數(shù)的方式就叫做 遞歸 。

  遞歸的最大深度:997

  1、python遞歸最大層數(shù)限制 997

  2、最大層數(shù)限制是python默認(rèn)的,可以做修改

  3、但是我們不建議你修改

  n = 0def f():

  global n

  n += 1

  print(n)

  f()

  f()

  測(cè)試遞歸最大深度

  如何修改遞歸最大深度:

  import sys #所有和python相關(guān)的設(shè)置和方法

  sys.setrecursionlimit(10000000)

  n = 0def f():

  global n

  n += 1

  print(n)

  f()

  f()

  修改遞歸最大深度

  遞歸的小實(shí)踐:

  1、猜年齡:

  #e的年齡#ed大兩歲#dc大兩歲#cb大兩歲#ba大兩歲 #a 40

  # 1.a  age(1) = 40# 2.b  age(1) + 2# 3.c   age(2) + 2# 4.d  age(3) + 2# 5.e  age(4) + 2

  def age(n):

  if n == 1:

  return 40

  else:

  ret = age(n-1)

  return ret + 2

  age(5)

  猜年齡

  、 一個(gè)數(shù),除2到不能整除2為止:

  #一個(gè)數(shù),除2到不能整除2為止(以8為例)def cal(num):

  if num % 2 == 0:

  num  = num // 2

  return cal(num)

  else:

  return num

  print(cal(8))

  數(shù)字整除類1

  3、整除類2

  #如果一個(gè)數(shù) 可以整除就整除#不能整除就*3+1def func(num):

  print(num)

  if num == 1:

  return

  if num %2 == 0:

  num = num //2

  else:

  num = num * 3 + 1

  func(num)

  func(5)

  數(shù)字整除類2

  遞歸函數(shù)與三級(jí)菜單

  遞歸函數(shù)實(shí)現(xiàn)三級(jí)菜單

  二、二分查找算法

  給你一個(gè)數(shù)列讓你找出其中一個(gè)數(shù)的位置你怎么找?index?這是python給我們的內(nèi)置函數(shù)。那他內(nèi)部是怎么實(shí)現(xiàn)的呢?現(xiàn)在要求我們自己設(shè)計(jì)函數(shù)來(lái)實(shí)現(xiàn)這個(gè)功能。

  數(shù)列例如: 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]

  i = 0for num in l:

  if num == 66:

  print(i)

  i+=1

  是不是感覺(jué)這個(gè)函數(shù)so easy但是我們所用的方法是循環(huán)列表然后一個(gè)一個(gè)對(duì)比。這個(gè)方法固然可以可是也只是適用于小的數(shù)組。如果這個(gè)數(shù)列很長(zhǎng)里面上萬(wàn)甚至更多,一個(gè)一個(gè)找效率太低。必須有一個(gè)新的算法來(lái)解決這個(gè)問(wèn)題。這就引出了今天另一個(gè)知識(shí)點(diǎn) 二分查找

  二分查找算法:

  算法:計(jì)算的方法

  二分查找前提:有序的遞增列表

  圖示:

python函數(shù):遞歸函數(shù)及二分查找算法

這就是二分查找算法

  簡(jiǎn)單二分法:

  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)

  二分法基礎(chǔ)版

  二分法升級(jí):

  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)

  二分法查找升級(jí)版

  小結(jié):

  遞歸解決的問(wèn)題:

  就是通過(guò)參數(shù),來(lái)控制每一次調(diào)用縮小計(jì)算的規(guī)模

  適合的場(chǎng)景:

  數(shù)據(jù)的規(guī)模在減小,但是解決問(wèn)題的思路沒(méi)有改變

  結(jié)束遞歸的標(biāo)志:return

 

 

來(lái)源:博客園

您還未登錄,請(qǐng)先登錄

熱門(mén)帖子

最新帖子

?