实验一
实验题目
1、兔子繁殖问题(Fibonacci’s Rabbits)。一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。
（1）请列出兔子繁殖问题的递推公式；
（2）请写出兔子繁殖问题的递归结束的条件；
（3）请编写程序用递归方式实现对兔子繁殖问题的求解，计算输出每个月各有多少只兔子。
（1）
当n = 1时，F(1) = 1
当n = 2时，F(2) = 1
当n > 2时，F(n) = F(n-1) + F(n-2)
（2）
1.当月份n<=0时，递归结束：
n为负数，不存在负数个月份，程序不会运行；n为0，还未开始繁殖，兔子数量为0。（此时一般是输入错误）
2.当月份n1或n2，此时兔子数量为1对，停止繁殖。
（3）
【代码】
def fib(months):
if months == 0:
return 0
elif months == 1:
return 1
else:
return fib(months-1) + fib(months-2)
n = int(input("请输入月份："))
for i in range(n):
rabbit = fib(i)
print("第", i+1, "个月的兔子数量：", rabbit, "只")
2、编程解决如下问题：
（1）建立列表lst，由键盘输入该列表的n个成员，n的大小由录入者控制;
（2）利用匿名函数和filter函数过滤掉其中的偶数，并将奇数保留在列表lst1中;
（3）利用匿名函数和map函数，求出lst1中每一个成员的倒数，并将它们保存到列表lst2中;
（4）分别输出lst，lst1，lst2。
【代码】
n = int(input("input number:"))
lst = []
for i in range(n):
member = int(input('input member:'))
lst.append(member)
lst1 = list(filter(lambda x: x % 2 == 1, lst))
lst2 = list(map(lambda y: 1 / y, lst))
print(lst)
print(lst1)
print(lst2)
【实例】
3、请分别用非递归方法和Fibonacci通项公式求出兔子繁殖问题(Fibonacci’s Rabbits)中第n个月小兔子的数量。要求如下：
（1） 列出Fibonacci通项公式
（2）编程实现题目中的两种算法
（3）在程序中，n由使用者输入，当为负数或0时，报异常，提示用户输入值错误，并允许用户重新输入，直到用户输入正确为止。
（4）此程序允许用户不间断使用，即计算完毕一次询问用户是否继续计算，用户输入“是”，则继续；输入“否”，则退出程序。
（5）将实验题目1中的方法与本题中两种方法进行比较，说出它们的优劣。
（1）
F n = ( φ n − ( 1 − φ ) n ) / √ 5 ( 2 ) Fn = (φ^n - (1-φ)^n) / √5(2) Fn=(φn−(1−φ)n)/√5(2)
φ （黄金分割率） = ( √ 5 + 1 ) / 2 ≈ 1.6180339887 φ （黄金分割率）= (√5 + 1) / 2 ≈ 1.6180339887 φ（黄金分割率）=(√5+1)/2≈1.6180339887
【代码】
import math
def fib_F1(n):
phi = (1 + math.sqrt(5)) / 2
return round((phi ** n - (-phi) ** (-n)) / math.sqrt(5))
def fib_fei(n):
if n <= 0:
raise ValueError("输入值错误")
if n == 1 or n == 2:
return 1
a, b = 1, 1
for _ in range(3, n + 1):
a, b = b, a + b
return b
def main():
while True:
try:
n = int(input("请输入月份 n："))
if n <= 0:
raise ValueError("输入值错误")
except ValueError as e:
print(e)
continue
result1 = fib_F1(n)
result2 = fib_fei(n)
print(f"使用 Fibonacci 通项公式计算结果：{result1}")
print(f"使用非递归方法计算结果：{result2}")
choice = input("是否继续计算？（是/否）")
if choice.lower() == "否":
break
main()
【实例】
（5）
递归方法的优点：
代码简洁易懂，并且不需要额外的数学公式或复杂的迭代逻辑。
递归方法的缺点：会进行大量重复的计算，时间复杂度高；递归可能会导致栈溢出，特别是对于较大的输入值。
非递归方法的优点：
有较低的时间复杂度，避免了重复计算，计算更高效；并且通常只需要保存前两个斐波那契数的值，占用的内存较少。
非递归方法的缺点：
需要使用迭代或循环来计算斐波那契数，可能需要额外变量和逻辑，代码更复杂，
并且不太直观。
Fibonacci 通项公式方法的优点：
Fibonacci 通项公式直接计算第 n 个斐波那契数，不需要逐个相加或进行递归，有较低的时间复杂度；能够得到准确的结果，无需担心误差积累问题。
Fibonacci 通项公式方法的缺点：
公式中包含浮点数运算和开方运算，对于大规模的计算，可能会出现精度问题或计算时间较长；需要数学知识和公式推导，不太直观。
4、修改实验题目2的程序，要求如下：
（1）建立函数inputZ(n)，完成lst的录入，录入时若lst<=0时，报异常，并允许用户重新录入数据,返回值为列表lst。
（2）建立函数eN(lst)，完成偶数过滤，求每个成员的倒数，然后，将所有成员累加求和，并返回和。
（3）编写可以调用上述函数的应用函数,计算列表中每个奇数成员的倒数之和，此函数运行后，可供用户循环使用，直到输入n为止，退出程序。
【代码】
def inputZ(n, lst=None):
if lst is None:
lst = []
temp_lst = []
for i in range(n):
while True:
try:
member = float(input(f"请输入第{i+1}个成员："))
if member <= 0:
raise ValueError("输入值错误")
temp_lst.append(member)
break
except ValueError as e:
print(e)
lst += temp_lst
return lst
def eN(lst):
sum_inverse = 0
for i in lst:
if i % 2 == 0:
sum_inverse += 1 / i
return sum_inverse
def odd(lst):
sum_inverse = 0
for i in lst:
if i % 2 != 0:
sum_inverse += 1 / i
return sum_inverse
def main():
lst = []
while True:
try:
print("请选择功能：")
print("1. 录入列表")
print("2. 完成偶数过滤，求每个偶数成员的倒数，并计算总和")
print("3. 完成奇数过滤，求每个奇数成员的倒数，并计算总和")
print("4. 退出程序")
choice = input("请输入选择：")
if choice == "1":
n = int(input("请输入列表成员的个数："))
if n <= 0:
raise ValueError("输入值错误")
lst = inputZ(n, lst)
print("列表成员：", lst)
elif choice == "2":
if not lst:
print("请先录入列表")
continue
result = eN(lst)
print("列表中每个偶数成员的倒数之和为：", result)
elif choice == "3":
if not lst:
print("请先录入列表")
continue
result = odd(lst)
print("列表中每个奇数成员的倒数之和为：", result)
elif choice == "4":
break
except ValueError as e:
print(e)
continue
main()
【实例】
![[数据结构]———归并排序](https://img-blog.csdnimg.cn/direct/c6d4a450684449d0ac5cf1e14e89cca7.png)
