递归:
函数自己调用自己
def func():
print("我是递归") #这里了变为死循环
func()
func() # 官方最大1000,你永远跑不到1000, 我实测998
while 1:
print("我不是递归")
树形结构的遍历
假设存在一个文件夹a,放在d盘里面,a里面有文件夹b,c b里面有文件夹d和e c里面有文件f
现在需要打印出所有的文件和文件名,这里的存在就是一个树形结构
import os
def func(lujing, n): # "d:/a/"
lst = os.listdir(lujing) # 打开文件夹. 列出该文件夹内的所有文件名
for el in lst: # el是文件的名字. b, c
# 还原文件路径
path = os.path.join(lujing, el) # "d:/a/b"
if os.path.isdir(path): # 判断路径是否是文件夹
print("..." * n,el) # 显示文件夹的名字
func(path, n + 1) # 在来一次 ################
else:
print(" " * n,el) # 显示文件
func("d:/a", 0)
def func(lujing, n): # d:/a/b
lst = os.listdir(lujing)
for el in lst: # b, c
# 路径
path = os.path.join(lujing, el) # 拼接路径 d:/a/b
# 判断是文件还是文件夹
if os.path.isdir(path):
print(" " * n, el)
func(path, n+1)
else:
f = open(path, mode="wb")
f.write(b'1')
print(" " * n, el)
func("d:/a/", 0)
二分法查找
所谓二分法查找,每次能够排除掉一半的数据,查找的效率非常高,但是局限性非常大,前提必须是有序的序列才能使用二分法
lst = [1,3,5,7,12,36,68,79] # 数据集 百万级数据 只有数据足够多的时候,二分法效率足够高
num = int(input("请输入你要查找的元素信息:"))
for el in lst:
if num == el:
print("存在") #这里循环列表,当数据足够大的时候就不太适合了
break
else:
print("不存在")
len(lst)
0 1 2 3 4 5 6 7
[1,3,5,7,12,36,68,79]
n = 28 # 3
规则. 掐头结尾取中间, 必须是有序序列,
用二分法查找
二分法查找 (需要明白和掌握)
规则. 掐头结尾取中间, 必须是有序序列
lst = [1,3,5,7,12,36,68,79]
n = int(input("请输入一个数"))
left = 0
right = len(lst) - 1
while left <= right:
mid = (left + right)//2
if n > lst[mid]:
left = mid + 1
elif n < lst[mid]:
right = mid - 1
else:
print("存在")
break
else:
print("不存在")
递归 查找法
def func(n, lst):
left = 0
right = len(lst) - 1
if lst != []:
mid = (left + right)//2
if n > lst[mid]:
func(n, lst[mid+1:]) # 改变列表
elif n < lst[mid]:
func(n, lst[:mid])
else:
print("找到了")
return
else:
print("没找到")
return
n = int(input("请输入你要查找的数:"))
func(n, [1,3,5,7,12,36,68,79]) # 78
递归 方法二
递归二 (需要你明白和掌握)
def func(n, lst, left, right): # 递归找到什么是可以变的. 什么是不可以变的
if left <= right:
mid = (left + right) // 2
if n > lst[mid]:
left = mid + 1
return func(n, lst, left, right)
elif n < lst[mid]:
right = mid - 1
return func(n, lst, left, right) # 递归如果有返回值. 所有调用递归的地方必须写return
else:
print("找到了")
return mid # 难点
else:
print("找不到")
return -1
n = int(input("请输入你要查找的数:"))
lst = [1,3,55,98,37,41,2,5,1,4]
ret = func(n, lst, 0, len(lst)-1) # 78
print(ret)
最快的查找方法,因为只做了一次比对
# 最快的查找
lst = [1,3,55,98,37,41,2,5,1,4]
new_lst = []
for i in range(99):
new_lst.append(0)
for i in lst: # 1,3,55,98
new_lst[i] = 1
print(new_lst)
i = int(input('请输入你要找的数据'))
if new_lst[i] == 0: # 1次
print("不存在")
else:
print("存在")