首页 > > 网络编程 > 其它 >

python之递归与二分法

2018-12-13 08:57:09来源：博客园阅读 ()

1. 递归
自己调用自己
递归的入口(参数) 和出口(return)
树形结构的遍历

import os
def func(lujing, n):
    lst = os.listdir(lujing) # 打开文件夹,列出所有文件
    for el in lst: # el 每一个文件
        path = os.path.join(lujing, el) # 还原路径
        if os.path.isdir(path): # 判断是否是文件夹
            print('\t'*n ,el)
            func(path, n + 1)
        else:
            print('\t' * n, el)
func(r'E:\python_workspace_s18', 0)

2. 二分法
掐头结尾取中间
查找效率非常的高

# 二分法
lst = [1, 3, 5, 7, 13, 15, 17, 19, 21, 23, 27, 29, 31, 33, 39, 41, 43, 47, 49]
left = 0
right = len(lst) - 1
count = 1
n = int(input("请输入一个数:"))
while left <=right:
    middle = (left + right) // 2
    if n > lst[middle]:
        left = middle + 1
    elif n < lst[middle]:
        right = middle - 1
    else:
        print('找到了')
        print('循环次数为:%s' % count)
        break
    count += 1
else:
    print('不存在')

# 递归实现:
lst = [1, 3, 5, 7, 13, 15, 17, 19, 21, 23, 27, 29, 31, 33, 39, 41, 43, 47, 49]
def func(s, lst):
    left = 0
    right = len(lst) - 1
    if lst != []:
        middle = (left + right) //2
        if n > lst[middle]:
            left = middle + 1
            lst = lst[left:]
            func(s, lst)
        elif n < lst[middle]:
            right = middle -1
            lst = lst[:right]
            func(s, lst)
        else:
            print('找到了')
            return
    else:
        print('没有找到')
        return

n = int(input('请输入一个数:'))
func(n, lst)
# 递归二
lst = [1, 3, 5, 7, 13, 15, 17, 19, 21, 23, 27, 29, 31, 33, 39, 41, 43, 47, 49]
def func(n, lst, left, right):
    if left <= right:
        middle = (left + right) // 2
        if n > lst[middle]:
            left = middle + 1
            return func(n, lst, left, right)
        elif n < lst[middle]:
            right = middle - 1
            return func(n, lst, left, right) # 递归如果有返回值. 所有调用递归的地方必须写return
        else:
            print("找到了")
            return middle
    else:
        print('没有找到')
        return -1
n = int(input('请输入一个数:'))
func(n,lst,0,len(lst)-1)