返回
前端
分类

看是否与列表中的某个值相等,里调用自身

日期: 2020-01-02 07:50 浏览次数 : 55

day4 递归二分法查找,day4递归二分法查找

    现有一个序列,data=[for i in range(1,5000,3)],现在要求看一个数是否在列表中存在,我们知道,我们可以使用in或__contains__()的方法,判断一个值是否在列表中,但是列表也是一个一个遍历,看是否与列表中的某个值相等,如果不等则返回False;如果在,则返回True。

def binary_search(data,find_n):
    mid_n = int(len(data)/2)
    #递归必须有结束条件,这里的结束条件是,当只有两个长度的时候必须结束
    if mid_n > 1:     #递归的结束条件,如果只有两个元素的时候就没有必要进行再一次判断了
        if data[mid_n] > find_n:         #如果中间值大于查找值,说明在列表的左侧
            print(data[:mid_n])
            binary_search(data[:mid_n],find_n)     #再次进行递归,缩小范围
        elif data[mid_n] < find_n:                 #如果中间值小于查找值,说明在中间值的右侧
            print(data[mid_n:])
            binary_search(data[mid_n:],find_n)     #递归,缩小范围
        elif data[mid_n] == find_n:                #如果中间值等于查找值,说明在列表中
            print("%s在列表data中" %find_n)
    elif mid_n == 1:
        #我们知道,递归结束的时候,有两种情况,第一种是长度等于2,另外一种情况是长度等于3
        print(data)
        if len(data) == 2:                         #如果列表长度等于2,那么就判断是否有一个等于查找值,
            if data[0] == find_n or data[1] == find_n:      
                print("%s在列表data中" % find_n)
            else:
                print("%s不在列表data中" % find_n)
        else:
            #列表长度等于3的时候的情况,逐个进行比较
            if data[0] == find_n or data[1] == find_n or data[2] == find_n:
                print("%s在列表data中" %find_n)
            else:
                print("%s不在列表data中" %find_n)


if __name__ == "__main__":
    data = [i for i in range(1,5008,4)]
    binary_search(data,10)

   必赢备用网址 1

    上面流程图中,详细描述了代码运转的过程,我们知道,如果使用递归,那么遍历列表的时候只有两种情况,要么查找的值在列表中,要么不在列表中,并且,到最后,列表的长度只可能为1和2,这个时候我们要分情况去考虑,上面总共有三种情况出现,(1)遍历过程中中间值正好就是我们要查找的值;(2)列表长度为1,那最后剩下的元素进行比较,这个时候一半就是小于等于最小值或者大于等于最大值;(3)列表的长度为2,这个时候情况也一样,要么大于等于最大值,小于等于最小值;出现列表1和2长度的原因是data原数据的长度有关,因为原数据有长度有单数和偶数之分,因此结果也会出现这两种情况,上述三种情况都要具体分析,不然肯定会报错。有些人可能输入的本来就是列表中的值肯定可以找的到,但如果不是的时候会报错。又或者奇数的时候对,偶数的时候错;偶数的时候对,奇数的时候错。

递归二分法查找,day4递归二分法查找 现有一个序列,data=[for i in range(1,5000,3)],现在要求看一个数是否在列表中存在,我们知道,我们可...

递归

特定:

  递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问题十分有效,它往往是算法的描述简洁而且易于理解。

  递归算法解决问题的特点:

  (1)递归就是在过程或函数里调用自身。

  (2)在使用递归测略时,必须有一个明确的递归结束条件,称为递归出口。

  (3)递归算法解题通常显得很简洁,但递归算法解题的效率较低。所以一般不提倡递归算法设计程序。

  (4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

要求:

  递归算法所体现的“重复”一般有三个要求:

  一是每次调用在规模上都有所缩小(通常是减半);

  二是相邻两次重复之间有密切的联系,前一次要为后一次做准备(通常前一次的输出就作为后一次的输入);

  三是在问题的规模极小时必须用直接给出解答而不再进行递归调用,因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件),无条件递归调用将会成为死循环而不能正常结束。

  下面来看一个简单的递归程序:

  def calc(n):
    print(n)
    if n/2 >1:
      res = calc(n/2)

      #print语句是不会执行的,因为在执行的过程中,一致在调用函数,只有退出的时候return把返回值传递给res才会执行
      print("res:",res)
    print("N:",n)

    #上面递归运算完成之后,把返回值返回给res,递归多少层,退出就有多少层
    return n

  calc(10)

  运行如下:

  10
  5.0
  2.5
  1.25
  N: 1.25
  res: 1.25
  N: 2.5
  res: 2.5
  N: 5.0
  res: 5.0
  N: 10 

  斐波那契数列指的是这样一个数列0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765  ...... 

  def func(arg1,arg2,stop):
必赢备用网址 ,    if arg1 == 0:
      print(arg1,arg2)
    arg3 = arg1 + arg2
    print(arg3)
    if arg3 < stop:

      #把arg2,arg3作为新的参数传递给函数
      func(arg2,arg3,stop)

  func(0,1,30)

  上面代码使用递归算法,每次调用函数并进行后面的数字相加,知道条件不满足位置,func(arg2,arg3,stop)是将arg2,arg3作为新的参数调用函数,此时函数重新执行,调用函数。

算法基础之二分法:

  有一个有序列表,判断一个数是否在列表中,data = list(range(1,6000,3)),现在判断3001是否在列表中。

  1.通过递归实现2分查找

  现有列表primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97],要求二等用最快的方式找出23。请Low B,Low 2B,Low 3B三个同学来回答这个问题。

  Low B:这个问题很简单,直接用data.__contains__(23),语音未落就被老板打了,让你自己实现,不是让你用现成的功能,Low B于是说,那只能从头开始一个一个数了,然后Low B被开除了.....

  Low 2B:因为这个列表是有序的,我们可以把列表从中截取一半,大概如下:

  p1 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,41]

  p2 = [ 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

  然后看p1[-1]也就是41是否比23大,如果比23大就代表肯定在p1里面,否则那就肯定在p2里面。现在我们知道23比41小,所以23肯定在p1里面,但p1里依然有很多元素,怎么找到23呢?很简单,依然按照上一次的方法,把p1分成2部分,如下:

  p1_a = [2, 3, 5, 7, 11, 13,17]

  p1_b = [19, 23, 29, 31, 37,41]

  然后我们发现,23比p1_a最后一个值17大,那代表23肯定在p1_b中,p1_b中依然有很多元素,那就再按之前的方法继续分半,最终用不了几次,肯定就把23找出来了!

  说完,Low BB满有成就感的甩了下头上的头皮屑。

  老板说:很好,确实较Low B的方案强很多。然后转头就问Low 3B,你有更好的想法么?

  Low 3B: 啊。。。噢 ,我。。。我跟Low 2B的想法一样,结果被他说了。

    Low BBB:啊。。。噢 ,我。。。我跟Low 2B的想法一样,结果被他说了。

  Low BBB此时冷汗直冒,因为他根本没思路,但还是硬着头皮去写了。。。。虽然自己没思路,但是会谷歌呀,三个小时过去了,终于憋出了以下代码:

  def binary_search(data_source,find_n):
      mid = int(len(data_source)/2)
      if mid >= 1:
          #递归必须有结束条件,这里的结束条件是当列表只有两个长度的时候运算终止
          if data_source[mid] > find_n: #查找的值在中间值的左边
              print("data in left of [%s]" %data_source[mid])
              #print(data_source[:mid])
              binary_search(data_source[:mid],find_n)
          elif data_source[mid] < find_n:
              print("data in right of [%s]" %data_source[mid])
              #print(data_source[mid:])
              binary_search(data_source[mid:],find_n)
          else:
              print("found find_n: ",data_source[mid])
      else:
          print("cannot finding....")

  if __name__ == '__main__':

      data = list(range(1,6000000,3))
      #print(data)

  binary_search(data,53)

  上面代码中,我们的思想是这样的,如果我们直接23 in data的话,是遍历列表,列表多长就遍历多少次,我们可以使用二分法来解决,由于列表是有序的,我们可以先取中间值data_source[mid],拿这个值与我们要查找的值进行比较,如果data_source[mid]中间值大于查找的值,说明要找的值的范围在中间值的左侧;反之在中间值的右侧,如果与中间值相等,那么这个值就等于中间值,就不需要在查找了。以上过程进行递归反复,就能够找到哦我们所需的结论,我们知道,每次查找的过程中列表的长度都是减半的。递归要有结束条件,我们想,当列表只有两个值的时候就应该停止,没有必要在进行递归了,因为要么等于,要么不等于,如果等于就打印找到了,如果没有就打印找不到。

  运行结果如下:

  data in left of [3000001]
  data in left of [1500001]
  data in left of [375001]
  data in left of [187501]
  data in left of [93751]
  data in left of [46876]
  data in left of [23437]
  data in left of [11719]
  data in left of [5860]
  data in left of [2929]
  data in left of [1465]
  data in left of [733]
  data in left of [367]
  data in left of [184]
  data in left of [91]
  data in right of [46]
  data in left of [67]
  data in left of [55]
  data in right of [49]
  found find_n:  52

    上面代码我们就运行了20次就结束查找了,大大减少了遍历的次数,如果使用in需要遍历6000000次,所以使用一些简单的算法能够大大节约我们的时间。但是上面程序也有一个bug就是查找不到1,为什么呢?因为我们在判断的过程中,一直判断的是data_source[mid]>0,我们知道,那么如果我们要判断1,那么我们知道,没有比1更小的数,而上面代码比较的是data_source[data]大于、等于、小于find_n,如果满足则没有关系,如果不满足则提示查找不到,这是有明显缺陷的,因为没有判断最小的值,因为我们要对data_source[0]进行判断,如何判断呢?就只需要在mid == 1的时候判断即可,我们知道,在mid == 1的时候必然是只剩下两个元素了,只要我们判断两个元素的情况即可,判断data_source[0]和data_source[0]是否与查找的数相等,如果相等则返回查找到了,否则必然是查找不到的情况。修改后的代码如下:

    def binary_search(data_source,find_n):
    mid = int(len(data_source)/2)
    if mid > 1:
    #递归必须有结束条件,这里的结束条件是当列表只有两个长度的时候运算终止

      if data_source[mid] > find_n: #查找的值在中间值的左边

        print("data in left of [%s]" %data_source[mid])
        #print(data_source[:mid])

        binary_search(data_source[:mid],find_n)
      elif data_source[mid] < find_n:
        print("data in right of [%s]" %data_source[mid])
        #print(data_source[mid:])

        binary_search(data_source[mid:],find_n)
      else:
        print("found find_n: ",data_source[mid])
    elif mid == 1:
      if data_source[mid] == find_n or data_source[0] == find_n:
        print("found find_n: ",find_n)
      else:
        print("cannot finding....")
    # else:
      # print("cannot finding....")

  if __name__ == '__main__':

    data = list(range(1,600,3))
    #print(data)

  binary_search(data,4)

 

  上述代码中,我们加入了当mid

1的时候对代码的判断,只要加上这么一个小小的判断就能够避免1查找不到的尴尬,修复了bug.