专用车网站建设价格,平度市城乡建设局网站,如何更快的让百度收录网站,毕业设计代做的网站好编程思想#xff1a;如何利用数学模型#xff0c;来解决对应的需求问题#xff1b;然后利用代码实现对应的数据模
算法#xff1a;使用代码实现对应的数学模型#xff0c;从而解决对应的业务问题
程序 算法 数据结构
在我们经常使用的算法中#xff0c;有两种非常常…编程思想如何利用数学模型来解决对应的需求问题然后利用代码实现对应的数据模
算法使用代码实现对应的数学模型从而解决对应的业务问题
程序 算法 数据结构
在我们经常使用的算法中有两种非常常用的算法递推算法 递归算法专门用于解决一些比较复杂但是拆分后相似度又非常高的程序。
递推算法
递归算法递推算法是一种简单的算法即通过已知条件利用特定条件得出中间推论直至得到结果的算法。递推又分为顺推和逆推。
顺推通过最简单的条件然后逐步推演结果
逆推通过结果找到规律然后推导已知条件 递推算法案例斐波那契数列
1 1 2 3 5 8 13 21 ...
① ② ③ ④ ⑤ ⑥ ...
第1位为1第2位为1第3位为2 1 1第4位为3 2 1依次类推...第n位结果为多少
f(n) f(n-1) f(n-2)
提出问题求斐波那契数列第15位的结果
分析f(15) f(14) f(13)
f(14) f(13) f(12)
f(13) f(12) f(11)
...
f(4) f(3) f(2) 3 1
f(3) f(2) f(1) 2
f(2) 1
f(1) 1
递推算法使用while循环或for循环 # 递推算法根据已知条件求结果或者根据结果求未知条件
def recusive(n): 返回斐波那契数列某一位n1的结果 if n 1 or n 2:return 1# 开始递推f(3) f(2) f(1) f(4) f(3) f(2) ... f(15) f(14) f(13)dict1 {1:1, 2:1}for i in range(3, n1):# f(3) f(2) f(1)# f(i) f(i-1) f(i-2)dict1[i] dict1[i-1] dict1[i-2]return dict1[n]# 函数调用
print(recusive(15)) 什么是递归算法
程序调用自身的编程技巧称为递归 recursion。递归做为一种算法在程序设计语言中广泛应用它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算大大地减少了程序的代码量。
① 简化问题找到最优子问题不能再小 ② 函数自己调用自己 def func():# 自己调用自己func()func() 递归两种重要的元素
递归有两个非常重要的概念
① 递归点找到解决当前问题的等价函数先解决规模比当前问题小一些的函数依次类推最终实现对问题的解决 有递有归
② 递归出口当问题解决的时候已经到达必须存在最优问题不能再次调用函数了
注如果一个递归函数没有递归出口就变成了死循环
编写递归三步走
① 明确你这个函数想要干什么
如求斐波那契数列
② 寻找递归结束条件
如就是在什么情况下递归会停止循环返回结果
③ 找出函数的等价关系式
如斐波那契数列第n位 f(n) f(n-1) f(n-2) 案例1使用递归求斐波那契数列
第一步明确这个函数想要干什么先定义出来明确调用方式 # 斐波那契数列 1 1 2 3 5 8 13 21 ...
def f(n):# 编写递归代码求第n位的结果# 调用函数
print(f(15)) # 610 第二步寻找递归的结束条件 # 斐波那契数列 1 1 2 3 5 8 13 21 ...
def f(n):# 编写递归代码求第n位的结果if n 1 or n 2:return 1# 调用函数
print(f(15)) # 610 第三步找出函数的等价关系式(最关键的一步) # 斐波那契数列 1 1 2 3 5 8 13 21 ...
def f(n):# 编写递归代码求第n位的结果if n 1 or n 2:return 1# 找出与斐波那契数列等价的关系式return f(n-1) f(n-2)# 调用函数
print(f(15)) # 610 案例2使用递归求N的阶乘如n100
阶乘是什么一个正整数的阶乘factorial是所有小于及等于该数的正整数的积如n!1×2×3×...×(n-1)×n
1! 1
2! 1x2 2
3! 1x2x3 6
4! 1x2x3x4 24
...
n!1×2×3×...×(n-1)×n
第一步明确这个函数要做什么以及定义函数以及调用方式 def f(n):# 编写递归条件print(f(100)) 第二步寻找递归的结束条件 def f(n):# 编写递归结束条件if n 2:return n# ...递归等式
print(f(100)) 第三步编写递归等价公式自己要调用自己
等价公式 找规律
1! f(1) 1
2! f(2) 2
3! f(2)x3 6
4! f(3)x4 24
...
n! f(n-1) * n def f(n):# 编写递归结束条件if n 2:return n# ...递归等式return f(n-1) * n
print(f(100)) 案例3面试题 猴子吃桃问题
猴子吃桃问题。猴子第1天摘下若干个桃子当即吃了一半还不过瘾又多吃了一个。第2天早上又将剩下的桃子吃掉一半又多吃了一个。以后每天早上都吃了前一天剩下的一半另加一个。到第10天早上想再吃时就只剩下一个桃子了。求第1天共摘了多少个桃子
第一步确定函数主要要完成什么功能需要传递哪些参数确认调用方式 def f(n): # 编写递归代码 # 调用f函数 print(f(1)) 第二步编写递归的结束条件出口 # 第一步确定函数功能 def f(n): # 第二步编写递归结束条件出口 if n 10: return 1
# 调用函数 print(f(1)) 第三步找出与这个问题相等的等式关系
求桃子的剩余数量假设法假设有10个桃子
第1天10个桃子吃一半10/2 5 1 6
第2天4个桃子吃一半4/2 2 1 3
第3天再想吃剩1个
第n天总剩余桃子的数量 第(n1)天桃子的剩余桃子的数量 1) * 2 # 第一步确定函数功能
def f(n):# 第二步编写递归结束条件出口if n 10:return 1# 第三步寻找与这个问题相似的等价公式return (f(n1) 1) * 2# 调用函数
print(f(8))
