mip 网站,武威建设银行网站,用什么做网站方便,公司网站上传图片首先我们要把递归和迭代这两个思想给剖析透彻#xff0c;用最简单的话语来说#xff0c;迭代就是简单的事重复做来完成一件事#xff0c;递归便是把一个大问题分解成若干小问题然后针对于小问题逐步解决从而完成一件事。
##迭代
迭代 是一种重复执行某个任务的控制结构。在…首先我们要把递归和迭代这两个思想给剖析透彻用最简单的话语来说迭代就是简单的事重复做来完成一件事递归便是把一个大问题分解成若干小问题然后针对于小问题逐步解决从而完成一件事。
##迭代
迭代 是一种重复执行某个任务的控制结构。在迭代中程序会在满足一定的条件下重复执行某段代码直到这个条件不再满足。
1.for循环是最常见的迭代形式之一适合预迭代的次数知道时使用
代码示例-详细的解释
def for_loop(n: int):for 循环res 0# 循环求和 1, 2, ..., n-1, nfor i in range(1, n 1):#对于range函数当只有两个参数的时候左闭右开的区间res ireturn res代码运行时的图例 2.while循环-跟for循环一样也是实现迭代的一种方式
在每次while循环下都先要进行条件的判断为真才会继续执行为假则会退出循环。
代码示例
def while_loop(n: int):while 循环res 0i 1 # 初始化条件变量# 循环求和 1, 2, ..., n-1, nwhile i n:res ii 1 # 更新条件变量return res小结总的来说for循环的结构更加紧凑而对于while循环则更加灵活我们则更具具体的需求而进行灵活地选择。
3.嵌套循环-我们在一个循环结构中嵌套另一个循环-for循环为例
代码示例
这里我们需要解释一下这个f-string的用法
f-string亦称为格式化字符串常量formatted string literals是Python3.6新引入的一种字符串格式化方法该方法源于PEP 498 – Literal String Interpolation主要目的是使格式化字符串的操作更加简便。f-string在形式上是以 f 或 F 修饰符引领的字符串fxxx 或 Fxxx以大括号 {} 标明被替换的字段f-string在本质上并不是字符串常量而是一个在运行时运算求值的表达式
1.f-string用大括号 {} 表示被替换字段其中直接填入替换内容
2.f-string的大括号 {} 可以填入表达式或调用函数Python会求出其结果并填入返回的字符串内
3.f-string大括号内所用的引号不能和大括号外的引号定界符冲突可根据情况灵活切换 和 若 和 不足以满足要求还可以使用 和
4.大括号外的引号还可以使用 \ 转义但大括号内不能使用 \ 转义
5.f-string大括号外如果需要显示大括号则应输入连续两个大括号 {{ 和 }}
6.上面提到f-string大括号内不能使用 \ 转义事实上不仅如此f-string大括号内根本就不允许出现 \。如果确实需要 \则应首先将包含 \ 的内容用一个变量表示再在f-string大括号内填入变量名
def nested_for_loop(n: int):双层 for 循环res # 循环 i 1, 2, ..., n-1, nfor i in range(1, n 1):# 循环 j 1, 2, ..., n-1, nfor j in range(1, n 1):res f({i}, {j}), return res对应的数量级根据循环的嵌套的次数呈现出n次的增长一次循环on二层循环on^2三次循环on^3依次按照次方增加。
##递归-通过调用自身函数来解决问题 递程序不断深入地调用自身通常传入更小或更简化的参数直到达到“终止条件”。归触发“终止条件”后程序从最深层的递归函数开始逐层返回汇聚每一层的结果。
而从实现的角度看递归代码主要包含三个要素。
终止条件用于决定什么时候由“递”转“归”。递归调用对应“递”函数调用自身通常输入更小或更简化的参数。返回结果对应“归”将当前递归层级的结果返回至上一层。da代码示例 def recur(n: int):递归# 终止条件if n 1:return 1# 递递归调用res recur(n - 1)# 归返回结果return n res代码的整个过程的示例 ##总结
迭代“自下而上”地解决问题。从最基础的步骤开始然后不断重复或累加这些步骤直到任务完成。--在循环中模拟求和过程从 1 遍历到 n每轮执行求和操作即可求得 fn 。
递归“自上而下”地解决问题。将原问题分解为更小的子问题这些子问题和原问题具有相同的形式。接下来将子问题继续分解为更小的子问题直到基本情况时停止基本情况的解是已知的。--将问题分解为子问题 f(n)nf(n−1) 不断递归地分解下去直至基本情况 f(1)1 时终止。
##关于递归的理解
##尾递归-如果函数在返回前的最后一步才进行递归调用则该函数可以被编译器或解释器优化使其在空间效率上与迭代相当。
尾递归--递归调用是函数返回前的最后一个操作这意味着函数返回到上一层级后无需继续执行其他操作因此系统无需保存上一层函数的上下文。
代码示例
def tail_recur(n, res):尾递归# 终止条件if n 0:return res# 尾递归调用return tail_recur(n - 1, res n)图例 ##递归树--当处理“分治类”问题的时候递归往往比迭代更加容易理解和代码的可读性更好
斐波那契数列为例
代码示例
def fib(n: int):斐波那契数列递归# 终止条件 f(1) 0, f(2) 1if n 1 or n 2:return n - 1# 递归调用 f(n) f(n-1) f(n-2)res fib(n - 1) fib(n - 2)# 返回结果 f(n)return res图例 本质上看递归体现“将问题分解为更小子问题”的思维范式这种分治策略是至关重要的。
##“分治”思想的重要性
1.从算法角度看搜索、排序、回溯、分治、动态规划等许多重要算法策略都直接或间接地应用这种思维方式。
2.从数据结构角度看递归天然适合处理链表、树和图的相关问题因为它们非常适合用分治思想进行分析。
