学习 2020-05-25
• 每次有不同的输入
• 但是每次运算相同
• 必须有停止嵌套的条件(防止死循环)
• 与循环的不同:每次输入数据范围缩小
• 能用嵌套不用循环:好写 好读
• 问题可以分解为相同的小问题(处理的数据范围变小)
• 广泛应用于 树, 图 数据结构中
• 广泛应用于三种问题:
• 分而治之 – Divide and conquer
• 贪婪算法 - Greedy
• 动态编程 – Dynamic programing
理论上是通过LIFO 的 stack 缓存实现:把套娃一个一个拆开先放好(输入数据集的大小就是套娃的大小, 数据集拆分的次数就是套娃的个数),从最小一个套娃开始再一个一个的合上。
实现代码如下:
解析:
嵌套方法数据集排列
要找的数据是3, 所以实际套娃个数是3就够了
如果找的数据是5,那么套娃个数是4
输出结果
当查询数据是5时,输出结果如下:
分析:数据集的变化 n*(n-1) (n > 1)
如果n=5 那么 结果为 5*(4*(3*(2*(1)))),代码如下:
斐波纳契数列(一种整数数列)前两个数是 0,1 后面数字是前面个数字的和。
0,1,1,2,3,5,8…
分析:f(n) = f(n-1) + f(n-2)
• 嵌套可以用循环实现
• Space -- 需要使用stack 空间
• 问题可以分为本质一样的小问题
• 对时间和空间要求不高
• 需要一个快速的解决方案的时候 – 实现简单
• Stack
• Tree
• Sorting: quick sort, merge sort
• Divide and Conquer
• Dynamic programing etc.