算法课堂实验报告（⼀）——python递归（fibonacci、全排
列、⼆分查、合并排序。。。
python实现递归算法
⼀、开发环境
开发⼯具：jupyter notebook 并使⽤vscode，cmd命令⾏⼯具协助编程测试算法
编程语⾔：python3.6
⼆、实验内容
问题1，实现 fibonacci 的递归和⾮递归。要求计算F（100）的值，⽐较两种⽅法的性能要求1）有合适的提⽰从键盘输⼊数据；例如“Please input the number to calculate:”2）有输出结果（下同）
Fibonacci⾮常有名，这⾥就不多介绍了，直接实现代码。
⾮递归版本实现的fibonacci数列代码：
# 实现fibonacci的递归算法以及⾮递归算法
# fibonacco数列前⼏项为了检验结果是否正确 1 1 2 3 5 8 13 21 34
# 使⽤⾮递归建⽴fibonacci数列
def fibonacci(n):
a = 1
b = 1
if n==1 or n==2:p
return 1
else:
for i in range(n-2):
a, b = b, a+b
return b
if __name__ == '__main__':
import time
n = int(input("Please input the number to calculate:"))
start = time.time()
print(fibonacci(n))快速排序python实现
end = time.time()
print("⾮递归版本的运⾏时间为", end-start)
利⽤jupyter notebook的运⾏⼯具进⾏运⾏，运⾏的出的结果为：
递归版本实现的fibonacci数列代码（效率低下版本）
# 低效的做法
def fibonacci_recursion(n):
if n<=2:
return 1
else:
return fibonacci_recursion(n-1)+fibonacci_recursion(n-2)
这个版本的代码实现起来⾮常容易，并且⼗分易懂，不过缺点就是效率实在是太低了，当输⼊100的时候，计算了相当长的时间，所以考虑换⼀种思路，按照⾮递归版本的⽅法，从前依推导出后⾯的数据。
递归版本实现的fibonacci数列代码（换思路的版本）
# 使⽤递归建⽴fibonacci数列
def fibonacci_recursion(n, a=1, b=1, c=3):
if n < 3:
return 1
else:
if n==c:
return a+b
else:
return fibonacci_recursion(n, a=b, b=a+b, c=c+1)
if __name__ == '__main__':
import time
n = int(input("Please input the number to calculate:"))
start = time.time()
print(fibonacci_recursion(n))
end = time.time()
print("递归版本的运⾏时间为", end-start)
这⼀版本的代码虽然⽐起上⾯的复杂了点，但是效率还是⾮常快的。
EXTRA
上⾯的版本可以说是挺好的了，然⽽当我输⼊2000的时候，还是报错了
好像说是超过了最⼤递归的深度，爆栈了。
依稀地记得，以前写代码的时候有过这种问题的解决⽅案，于是开始百度。
然⽽尴尬的是了半天，并没有到我上次的那份代码，上次的好像是⽤上了装饰器解决问的，不过查到了另外的解决⽅案，使⽤尾递归优化，并使⽤了python的⽣成器机制。代码如下：
# python 使⽤尾递归优化
import types    # 导⼊types模块
# 如果函数中出现了yield解释器会⾃动将函数当成⽣成器，此时是不会直接⽣成数的
# tramp的作⽤为：使⽣成器不断产⽣下⼀个数据
def tramp(gen, *args, **kwargs):
g = gen(*args, **kwargs)
while isinstance(g, types.GeneratorType):  # 如果g为⽣成器的实例
g=g.__next__()  #
return g
def fibonacci_recursion(n, a=1, b=1, c=3):
if n < 3:
yield 1
else:
if n==c:
yield a+b
else:
yield fibonacci_recursion(n, a=b, b=a+b, c=c+1)
if __name__ == '__main__':
import time
n = int(input("Please input the number to calculate:"))
start = time.time()
print(fibonacci_recursion(n))
end = time.time()
print("递归版本的运⾏时间为", end-start)
⽹上到的代码是py2的版本的，最近都是⽤的py3，版本问题还真是头疼呀，花了点时间改了⼀下。
经过优化的递归函数效果惊⼈,2000以内的都不在是问题啦。
问题2，实现全排列算法
1. 实现前20个奇数的全排列。
2. 实现数字1，3，5，7，9五个数字的全排列
实现对数字1,3,5,7,9五个数字的全排列
# 实现全排列的算法。
# a) 实现数字1，3，5，7，9五个数字的全排列。
# b) 实现前20个奇数的全排列。
# 全排列函数
def full_arrangement(lis):
length = len(lis)
if length < 2:    # 边界条件
return lis
else:
result = []
for i in range(length):
ch = lis[i]    # 取出str中每⼀个字符
rest = lis[0: i] + lis[i+1: length]
for s in full_arrangement(rest):  # 递归
result.append(ch+s) # 将ch与⼦问题的解依次组合
return result
if __name__ == '__main__':
lis = [1, 3, 5, 7, 9]
lis1 = list(map(str, lis))
import time
start = time.time()
print(full_arrangement(lis1))
end = time.time()
print("全排列运⾏时间：", end-start)
对五个数进⾏全排列的运⾏时间：
下⼀个问题：实现前20个奇数的全排列。
测试代码已经写好了，是这个样⼦的
lis2 = list(map(str, [x for x in range(40) if x%2!=0]))
print(lis2)
start = time.time()
print(full_arrangement(lis2))
end = time.time()
print("全排列运⾏时间：", end-start)
然⽽，emmm……，好像运⾏时间太长了点。
当对前10个奇数进⾏全排列的时候，运⾏结果如下图所⽰：
10个数花了13秒的时间，可见前20个奇数所⽤时间⾮常的长，然⽽现在并没有到更好地优化解决⽅案，只能实现到这个地步，感到⾮常抱歉。
问题3，实现⼆分查。
1. 在 1 3 3 4 5 5 7 8 8 9 10 中查得到7，返回其所在的位置。
2. 随机⽣成10000个整数，查数字 2025，返回其所在的位置。
原理：
折半查法也称为⼆分查法，它充分利⽤了元素间的次序关系，采⽤分治策略，可在最坏的情况下⽤O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数⼤致相同的两半，取a[n/2]与欲查的x作⽐较，如果x=a[n/2]则到x，算法终⽌。如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这⾥假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。
要求：
1.必须采⽤顺序存储结构。
2.必须按关键字⼤⼩有序排列。
代码实现：
# 实现⼆分查。
# a) 在 1 3 3 4 5 5 7 8 8 9 10 中查得到7，返回其所在的位置。
# b) 随机⽣成10000个整数，查数字 2025，返回其所在的位置。
import random
# ⼆分查，如果在lis中到n，则返回n的下标，如果不到，则返回-1
def binary_search(lis, n):
length = len(lis)
left = 0
right = length-1
while left <= right:
mid = (left+right)//2
# 注意，注意，注意
# 这⾥要注意，py3使⽤//作为整除，好像程⽼师的书《算法分析与设计》P69页存在这个错误
if lis[mid] == n:
return mid
elif lis[mid] > n:
right = mid-1
elif lis[mid] < n:
left = mid+1
return -1
if __name__ == '__main__':
lis =  [1, 3, 3, 4, 5, 5, 7, 8, 8, 9, 10]
print('数字7的下标为:',binary_search(lis, 7))
# 随机⽣成10000个成递增的数据
x = 0
lis2 = []
for i in range(10000):
lis2.append(x)
x += int(random.random()*10)
find = binary_search(lis2, 2026)
if find == -1:
print('没有到2026！')
else:
print('到2026，位置为', find)
多次运⾏情况：
运⾏one
运⾏two

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。