数据结构算法-python实现
一、递推法
1.求斐波那契数列前20项。第0项是1，第一项是1，从第二项开始，每一项为前两项之和。
#使用递推法解决斐波那契数列
fib_list=[]
fib_list.append(1)
fib_list.append(1)
for i in range(2,20):
x=fib_list[i-1]+fib_list[i-2]
fib_list.append(x)
for i in range(0,20):
print(fib_list[i],end=' ')
result:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
2.求步长为2的等差数列前10项和
a=[]
a.append(1)
s=a[0]
for i in range(1,10):
x=a[i-1]+2
a.append(x)
s=s+a[i]
print(s)
result:
100
3.猴子吃桃：猴子第一天摘下若干个桃子，当天吃掉一般，又多吃了一个，第二天早上又将 剩下的桃子吃掉一半，又多吃一个，以后每天早上第一吃掉剩下的桃子吃掉一半，又多一个。 到第10天早上，只剩下1只桃子了，稳猴子第一天共摘了多少个桃子？
peach_list=[0]*11
i=10
peach_list[10]=1
while i>1:
i=i-1
peach_list[i]=2*(peach_list[i+1]+1)
print(peach_list[1])
result:
1534
4.有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后 每个月又生一对兔子，假如兔子都不死，问第10个月的兔子总数为多少？
#月份 兔子对数 1 1 2 1 3 2 4 3 5 5
#原理类似 斐波那契数列 （算兔子对数）
def fib(N):
n, f1, f2 = 1, 0, 1
while n < N: # 第三个月开始赋值操作
f1, f2 = f2, f1 + f2
n = n + 1
print('第%d月兔子的数量为:%d对，共%d只' % (N, f2, f2 * 2))
fib(int(input("输入月份:")))
result:
输入月份:10
第10月兔子的数量为:55对，共110只
二、迭代法
1.求斐波那契数列前20项
a=b=1
i=3
print(a,b,end=' ')
while i<=20:
c=a+b
print(c,end=' ')
a=b
b=c
i=i+1
result:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
2.存款10000元，利率为4%，计算第10年內每年利息和本金
r=0.04
p=10000
for i in range(1,11):
m=p*r
p=p*(1+r)
print(m,p)#输出每年利息本金
result:
400.0 10400.0
416.0 10816.0
432.64 11248.640000000001
449.94560000000007 11698.585600000002
467.9434240000001 12166.529024000003
486.66116096000013 12653.190184960004
506.12760739840013 13159.317792358404
526.3727116943362 13685.690504052742
547.4276201621096 14233.118124214852
569.3247249685941 14802.442849183446
牛顿迭代法，牛顿在17世纪提出的一种实数域和复数域上近似求解方程的方法。 算法思想： 假设函数在某一区间內为单调函数，而且有一个实根。 牛顿迭代法是从初始点x0开始，一步一步迭代，从而找到更接近方程的近似根。
3.用牛顿迭代法求解方程 f(x)=x3-2x2+4x+1=0 在x=0附近的根。
x0=x1=0
n=0
e=0.000001
while((n==0) or abs(x0-x1)>e):
x0=x1
f=x0**3-2*x0**2+4*x0+1
f1=3*x0**2-4*x0+4
x1=x0-f/f1
n=n+1
print(n,x1)
result:
1 -0.25
2 -0.22289156626506024
3 -0.2224945975740195
4 -0.2224945141207901
三、穷举法
穷举法也叫枚举法或列举法， 通过把需要解决的问题的所有可能情况逐一试验来找出符合条件的解的方法。
问题求解思想：根据提出的问题，列举出所有可能的情况，并依据问题中给定的条件检验哪些情况是符合要求的，并将符合要求的情况输出，从而得到问题的全部答案。
解决的问题：常用语解决“是否存在”或“有多少种可能”等类型的问题。比如，不低估方程求解，质数、水仙花数判段等。
1.百钱百鸡问题
x=0
while x<=100:
y=0
while y<=100:
z=0
while z<=100:
m=x+y+z
n=5*x+3*y+z/3
if m==100 and n==100:
print(x,y,z)
z=z+1
y=y+1
x=x+1
#算法运算了100*100*100=100万次
result:
0 25 75
4 18 78
8 11 81
12 4 84
#优化算法1
#公鸡5元/只，x<=20;
#母鸡3元/只，y<=33;
#小鸡1元/只，z<=100
for x in range(0,20+1):
for y in range(0,33+1):
for z in range(0,100+1):
m=x+y+z
n=3*x+5*y+z/3
if m==100 and n ==100:
print(x,y,z)
print("求解结束")
#算法执行20*33*100次=6.6万次
result:
4 12 84
11 8 81
18 4 78
求解结束
#优化算法2
#公鸡5元/只，x<=20;
#母鸡3元/只，y<=33;
#小鸡1元/只，z=100-x-y
for x in range(0,20+1):
for y in range(0,33+1):
z=100-x-y
n=5*x+3*y+z/3
if n==100:
print(x,y,z)
print("求解结束")
#算法执行20*33次=660次
result:
0 25 75
4 18 78
8 11 81
12 4 84
求解结束
2.有36砖，有36人，男人每次可搬4块，女人每次可搬3块，2个小孩每次可以抬一块。 请问：36块砖一次搬完，需要多少男的、女的、小孩？
#男 4块/人,x<=9;
#女 3块/人,，y<=12;
#孩 (1/2)块/人，(36-x-y)/2
for x in range(0,10):
for y in range(0,13):
z=(36-x-y)/2
n=4*x+3*y+z/2
if n==36:
print(x,y,int(z))
print("求解结束")
result:
5 3 14
求解结束
四、排序算法
…
五、查找算法
…
本文地址：https://blog.csdn.net/On_T_nO/article/details/107661652