递归与搜索算法

dfss案例DFS（深度优先搜索）是一种用于图遍历或搜索的算法，它以递归的方式遍历或搜索图中的节点。

在本文中，我们将以DFS案例为题，列举一些常见的应用场景和实例，来说明DFS算法的作用和用途。

1. 连通性检测：DFS可以用来检测图中的连通分量。

通过从一个起始节点开始，递归地访问所有相邻节点，可以判断图是否连通，以及得到图中的连通分量。

2. 深度优先生成树：DFS可以生成一棵深度优先生成树，该树用于表示图中的节点之间的关系。

通过递归地遍历图中的节点，可以建立起一棵树，其中每个节点的子节点都是其相邻节点。

3. 拓扑排序：DFS可以用于拓扑排序，即对有向无环图（DAG）中的节点进行排序。

通过从任意一个节点开始进行DFS遍历，并在递归返回时记录节点的顺序，可以得到一个拓扑排序序列。

4. 寻找图中的环：DFS可以用于寻找图中的环。

通过递归地遍历图中的节点，并记录访问过的节点，可以检测到是否存在环。

如果在遍历过程中遇到已经访问过的节点，则说明存在环。

5. 最短路径问题：DFS可以用于解决最短路径问题。

通过递归地遍历图中的节点，并记录路径长度，可以找到从起始节点到目标节点的最短路径。

6. 迷宫求解：DFS可以用于解决迷宫求解问题。

将迷宫表示为图的形式，通过递归地遍历图中的节点，可以找到从起点到终点的路径。

7. 数独求解：DFS可以用于解决数独问题。

通过递归地遍历数独中的格子，并尝试填入数字，可以找到数独的解。

8. 二叉树的遍历：DFS可以用于二叉树的遍历。

通过递归地遍历二叉树的左子树和右子树，可以得到前序遍历、中序遍历和后序遍历的结果。

9. 图的着色问题：DFS可以用于解决图的着色问题。

通过递归地遍历图中的节点，并给节点标记颜色，可以实现对图的着色。

10. 剪枝问题：DFS可以用于解决剪枝问题。

通过递归地遍历搜索树，并在搜索过程中进行剪枝操作，可以减少不必要的搜索。

以上是DFS算法的一些常见应用场景和实例。

必备算法：递归！⽆论你是前端开发，还是后端开发，都需要掌握它！递归是⼀种⾮常重要的算法思想，⽆论你是前端开发，还是后端开发，都需要掌握它。

在⽇常⼯作中，统计⽂件夹⼤⼩，解析xml⽂件等等，都需要⽤到递归算法。

它太基础太重要了，这也是为什么⾯试的时候，⾯试官经常让我们⼿写递归算法。

本⽂呢，将跟⼤家⼀起深⼊挖掘⼀下递归算法~什么是递归？递归，在计算机科学中是指⼀种通过重复将问题分解为同类的⼦问题⽽解决问题的⽅法。

简单来说，递归表现为函数调⽤函数本⾝。

在知乎看到⼀个⽐喻递归的例⼦，个⼈觉得⾮常形象，⼤家看⼀下：❝递归最恰当的⽐喻，就是查词典。

我们使⽤的词典，本⾝就是递归，为了解释⼀个词，需要使⽤更多的词。

当你查⼀个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第⼆个词，可惜，第⼆个词⾥仍然有不懂的词，于是查第三个词，这样查下去，直到有⼀个词的解释是你完全能看懂的，那么递归⾛到了尽头，然后你开始后退，逐个明⽩之前查过的每⼀个词，最终，你明⽩了最开始那个词的意思。

❞来试试⽔，看⼀个递归的代码例⼦吧，如下：递归的特点实际上，递归有两个显著的特征,终⽌条件和⾃⾝调⽤:✿⾃⾝调⽤：原问题可以分解为⼦问题，⼦问题和原问题的求解⽅法是⼀致的，即都是调⽤⾃⾝的同⼀个函数。

✿终⽌条件：递归必须有⼀个终⽌的条件，即不能⽆限循环地调⽤本⾝。

结合以上demo代码例⼦，看下递归的特点：递归与栈的关系其实，递归的过程，可以理解为出⼊栈的过程的，这个⽐喻呢，只是为了⽅便读者朋友更好理解递归哈。

以上代码例⼦计算sum（n=3）的出⼊栈图如下：为了更容易理解⼀些，我们来看⼀下函数sum（n=5）的递归执⾏过程，如下：✿计算sum（5）时，先sum（5）⼊栈，然后原问题sum（5）拆分为⼦问题sum（4），再⼊栈，直到终⽌条件sum（n=1）=1，就开始出栈。

✿ sum（1）出栈后，sum（2）开始出栈，接着sum（3）。

✿最后呢，sum（1）就是后进先出，sum（5）是先进后出，因此递归过程可以理解为栈出⼊过程啦~递归的经典应⽤场景哪些问题我们可以考虑使⽤递归来解决呢？即递归的应⽤场景⼀般有哪些呢？✿阶乘问题✿⼆叉树深度✿汉诺塔问题✿斐波那契数列✿快速排序、归并排序（分治算法体现递归）✿遍历⽂件，解析xml⽂件递归解题思路解决递归问题⼀般就三步曲，分别是：✿第⼀步，定义函数功能✿第⼆步，寻找递归终⽌条件✿第⼆步，递推函数的等价关系式这个递归解题三板斧理解起来有点抽象，我们拿阶乘递归例⼦来喵喵吧~1、定义函数功能定义函数功能，就是说，你这个函数是⼲嘛的，做什么事情，换句话说，你要知道递归原问题是什么呀？⽐如你需要解决阶乘问题，定义的函数功能就是n的阶乘，如下：2、寻找递归终⽌条件递归的⼀个典型特征就是必须有⼀个终⽌的条件，即不能⽆限循环地调⽤本⾝。

递归算法得优缺点：3优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法得正确性，因此它为设计算法、调试程序带来很大方便。

3缺点：递归算法得运行效率较低，无论就是耗费得计算时间还就是占用得存储空间都比非递归算法要多。

边界条件与递归方程就是递归函数得二个要素应用分治法得两个前提就是问题得可分性与解得可归并性以比较为基础得排序算法得最坏倩况时间复杂性下界为0(n I o g2n)。

回溯法以深度优先得方式搜索解空间树T,而分支限界法则以广度优先或以最小耗费优先得方式搜索解空间树T。

舍伍德算法设计得基本思想：设A就是一个确定性算法，当它得输入实例为x时所需得计算时间记为tA(x)。

设Xn就是算法A得输入规模为n得实例得全体，则当问题得输入规模为n时，算法A所需得平均时间为这显然不能排除存在x€Xn使得得可能性。

希望获得一个随机化算法B，使得对问题得输入规模为n得每一个实例均有拉斯维加斯(Las Vegas )算法得基本思想：设p(x)就是对输入x调用拉斯维加斯算法获得问题得一个解得概率。

一个正确得拉斯维加斯算法应该对所有输入x均有p(x)>0。

设t(x)就是算法obst in ate找到具体实例x得一个解所需得平均时间，s(x)与e(x)分别就是算法对于具体实例x求解成功或求解失败所需得平均时间，则有：解此方程可得：蒙特卡罗(Monte Carlo)算法得基本思想：设p就是一个实数，且1/2<p<1。

如果一个蒙特卡罗算法对于问题得任一实例得到正确解得概率不小于p,则称该蒙特卡罗算法就是p正确得，且称p1/2就是该算法得优势。

如果对于同一实例，蒙特卡罗算法不会给出2个不同得正确解答，则称该蒙特卡罗算法就是一致得。

线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。

单纯形算法得特点就是：(1) 只对约束条件得若干组合进行测试，测试得每一步都使目标函数得值增加；(2) 一般经过不大于m或n次迭代就可求得最优解。

dfs算法原理DFS算法原理DFS（Depth First Search）算法是一种用于图遍历的算法，它的基本原理是从一个顶点开始，沿着路径往下一直走到底，然后返回到上一个顶点，继续下一条路径，直到所有路径都被遍历完。

DFS算法采用回溯的思想，通过递归或者栈的方式实现。

DFS算法的过程可以用以下几个步骤来描述：1. 选择一个顶点作为起始点，访问该顶点，并标记为已访问。

2. 从该顶点出发，选择一个邻接顶点，若该邻接顶点未被访问，则继续选择该邻接顶点作为起始点，重复步骤1；若所有邻接顶点都已被访问，则回溯到上一个顶点。

3. 重复步骤2，直到所有顶点都被访问。

DFS算法的实现可以使用递归或者栈来实现。

下面分别介绍两种实现方式。

递归实现DFS算法：递归实现DFS算法的关键在于定义一个递归函数，用来遍历顶点的邻接顶点。

具体步骤如下：1. 选择一个顶点作为起始点，访问该顶点，并标记为已访问。

2. 定义一个递归函数，用来遍历该顶点的邻接顶点。

3. 在递归函数中，选择一个未被访问的邻接顶点，将其标记为已访问，并递归调用该函数。

4. 若所有邻接顶点都已被访问，则返回到上一个顶点。

5. 重复步骤3和步骤4，直到所有顶点都被访问。

递归实现DFS算法的伪代码如下：```function DFS(vertex):访问顶点vertex标记顶点vertex为已访问for each 邻接顶点adj_vertex of vertex:if adj_vertex未被访问:DFS(adj_vertex)```栈实现DFS算法：栈实现DFS算法的关键在于使用栈来保存需要访问的顶点。

具体步骤如下：1. 选择一个顶点作为起始点，将其入栈，并标记为已访问。

2. 当栈不为空时，执行以下操作：a. 弹出栈顶元素，访问该顶点。

b. 遍历该顶点的邻接顶点，若邻接顶点未被访问，则将其入栈，并标记为已访问。

3. 重复步骤2，直到栈为空。

栈实现DFS算法的伪代码如下：```function DFS(vertex):创建一个栈stack将顶点vertex入栈标记顶点vertex为已访问while stack不为空:弹出栈顶元素top_vertex访问顶点top_vertexfor each 邻接顶点adj_vertex of top_vertex:if adj_vertex未被访问:将顶点adj_vertex入栈标记顶点adj_vertex为已访问```DFS算法的时间复杂度和空间复杂度都与图的顶点数和边数相关。

二进制搜索算法的实用技巧和方法二进制搜索算法，也称为二分查找算法，是一种高效的搜索方法，常用于有序数组或列表中查找目标元素的位置。

它通过将目标值与数组中间的元素进行比较，从而将搜索范围缩小一半，直到找到目标元素或确定目标元素不存在。

本文将介绍二进制搜索算法的实用技巧和方法，帮助读者更好地理解和应用该算法。

一、基本原理和步骤二进制搜索算法的基本原理是将目标元素与数组中间位置的元素进行比较，根据比较结果将搜索范围缩小一半。

具体步骤如下：1. 确定搜索范围：初始化左右边界，左边界为数组的第一个元素的索引，右边界为数组的最后一个元素的索引。

2. 计算中间位置：通过左右边界计算中间位置，可以使用以下公式：middle = (left + right) / 2。

3. 比较目标值：将目标值与中间位置的元素进行比较。

4. 调整搜索范围：根据比较结果，将搜索范围缩小一半。

如果目标值小于中间位置的元素，则将右边界调整为middle-1；如果目标值大于中间位置的元素，则将左边界调整为middle+1。

5. 重复执行步骤2至4，直到找到目标元素或确定目标元素不存在。

二、应用技巧和方法1. 确定边界条件：在实际应用中，需要根据具体情况确定搜索的边界条件。

例如，如果数组为空，则搜索范围为0；如果数组长度为1，则搜索范围为0至0。

2. 处理边界情况：在实际应用中，需要考虑目标元素不存在的情况。

当搜索范围缩小至左边界等于右边界时，如果目标值与该位置元素相等，则找到目标元素；否则，目标元素不存在。

3. 处理重复元素：如果数组中存在重复元素，二进制搜索算法可能无法找到目标元素的第一个或最后一个位置。

可以通过修改比较逻辑，使算法能够找到目标元素的第一个或最后一个位置。

4. 递归实现：除了迭代实现外，二进制搜索算法还可以使用递归实现。

递归实现可以简化代码逻辑，但需要注意递归深度过大可能导致栈溢出。

5. 变体问题：二进制搜索算法还可以应用于一些变体问题，如查找第一个大于目标值的元素、查找最后一个小于目标值的元素等。

一、实验目的整数拆分问题是指将一个正整数拆分成若干个正整数之和，且这些正整数的和等于原整数。

本实验旨在通过编程实现整数拆分问题，并分析不同算法的效率。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.73. 开发环境：PyCharm三、实验内容1. 算法实现2. 性能分析3. 算法优化四、实验步骤1. 算法实现（1）递归算法递归算法是一种常用的解决整数拆分问题的方法。

以下是递归算法的Python实现：```pythondef split_integer(n):if n == 1:return [1]result = []for i in range(1, n):for j in split_integer(n - i):result.append(j + [i])return result```（2）动态规划算法动态规划算法是解决整数拆分问题的一种高效方法。

以下是动态规划算法的Python实现：```pythondef split_integer_dp(n):dp = [1] (n + 1)for i in range(2, n + 1):for j in range(1, i):dp[i] = max(dp[i], dp[i - j] + 1)return dp[n]```2. 性能分析（1）递归算法递归算法的时间复杂度为O(2^n)，其中n为输入整数的值。

由于递归算法存在大量重复计算，因此其效率较低。

（2）动态规划算法动态规划算法的时间复杂度为O(n^2)，其中n为输入整数的值。

动态规划算法通过保存已计算的结果，避免了重复计算，从而提高了效率。

3. 算法优化针对递归算法，我们可以通过记忆化搜索（memoization）来优化算法。

记忆化搜索是一种将已计算的结果存储在内存中的技术，可以避免重复计算。

以下是记忆化搜索算法的Python实现：```pythondef split_integer_memo(n, memo={}):if n == 1:return [1]if n in memo:return memo[n]result = []for i in range(1, n):for j in split_integer_memo(n - i, memo):result.append(j + [i])memo[n] = resultreturn result```五、实验结果与分析1. 递归算法与动态规划算法的性能对比在输入整数n=10时，递归算法需要约2.5秒，而动态规划算法需要约0.005秒。

算法：记忆化搜索算法⼀：简述 记忆化搜索实际上是递归来实现的，但是递归的过程中有许多的结果是被反复计算的，这样会⼤⼤降低算法的执⾏效率。

⽽记忆化搜索是在递归的过程中，将已经计算出来的结果保存起来，当之后的计算⽤到的时候直接取出结果，避免重复运算，因此极⼤的提⾼了算法的效率。

⼆：应⽤实例题⽬描述对于⼀个递归函数w(a,b,c)如果 a<=0 or b<=0 or c<=0 就返回值1.如果 a>20 or b>20 or c>20就返回w(20,20,20)如果 a<b并且b<c 就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)其它的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)这是个简单的递归函数，但实现起来可能会有些问题。

当a,b,c均为15时，调⽤的次数将⾮常的多。

你要想个办法才⾏./* absi2011 : ⽐如 w(30,-1,0)既满⾜条件1⼜满⾜条件2这种时候我们就按最上⾯的条件来算所以答案为1*/输⼊输出格式输⼊格式：会有若⼲⾏。

并以-1,-1,-1结束。

保证输⼊的数在[-9223372036854775808,9223372036854775807]之间，并且是整数。

输出格式：输出若⼲⾏，每⼀⾏格式：w(a, b, c) = ans注意空格。

输⼊输出样例输⼊样例#1：1 1 12 2 2-1 -1 -1输出样例#1：w(1, 1, 1) = 2w(2, 2, 2) = 4 这是⼀个⾮常经典的记忆化搜索的题⽬。

拿到这个题，⾸先可以想到的就是递归的⽅法，看上去⽤递归可以轻⽽易举的解决。

但是递归的开销是不⼀般的⼤。

下⾯先给⼤家上⼀个递归的代码，以便和之后的记忆化搜索的进⾏对⽐。

1 #include<iostream>2 #include<cstdio>3 #include <time.h> //⽤来记时4using namespace std;5clock_t start, finish;6double duration;78 typedef long long ll;9 ll f[30][30][30];1011int w(ll a, ll b, ll c){ //递归的函数12if(a<=0||b<=0||c<=0){13return1;14 }15else if(a>20||b>20||c>20){16return w(20,20,20);17 }18else if(a<b&&b<c){19return w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c);20 }21else{22return w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);23 }24}2529 cin >> a >> b >> c;30 start = clock(); //开始计时31if(a==-1&&b==-1&&c==-1) return0;32else{33 printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));34 finish = clock(); //结束记时35 duration = (double)(finish - start) / CLOCKS_PER_SEC; //计算持续时间36 printf( "%f seconds\n", duration );37 }38 }39return0;40 } 运⾏结果记忆化搜索解法 开辟⼀个数组 f[][][]，⽤来存储计算出来的结果。

二进制搜索算法对内存占用的影响及其优化措施在计算机科学领域，算法的设计和优化一直是研究的重点。

其中，二进制搜索算法是一种常用的搜索算法，它能够高效地在有序数组中查找目标元素。

然而，二进制搜索算法在一些情况下可能会占用较多的内存资源。

本文将探讨二进制搜索算法对内存占用的影响，并提出一些优化措施。

一、二进制搜索算法简介二进制搜索算法，也称为折半查找算法，是一种高效的搜索算法。

它的基本思想是将有序数组分成两部分，然后确定目标元素位于哪一部分中，进而缩小搜索范围。

具体步骤如下：1. 将数组的起始位置和结束位置设为左右指针。

2. 计算中间位置的索引。

3. 判断中间位置的元素与目标元素的关系，若相等则找到目标元素，若大于目标元素则将结束位置设为中间位置的前一个位置，若小于目标元素则将起始位置设为中间位置的后一个位置。

4. 重复步骤2和步骤3，直到找到目标元素或起始位置大于结束位置。

二、二进制搜索算法对内存占用的影响二进制搜索算法的内存占用主要体现在两个方面：递归调用和额外的指针。

首先，递归调用是二进制搜索算法中常用的实现方式。

每次递归调用都需要在内存中保存函数的返回地址、参数和局部变量等信息，这会占用一定的内存空间。

而且，递归调用的深度与数组的长度成正比，当数组较大时，递归调用所占用的内存也会增加。

其次，二进制搜索算法需要使用额外的指针来记录数组的起始位置、结束位置和中间位置。

这些指针在算法执行过程中需要不断更新，占用了一定的内存空间。

特别是在递归调用的情况下，每次递归都需要保存这些指针的值，进一步增加了内存的占用。

三、优化措施针对二进制搜索算法对内存占用的问题，可以采取以下优化措施：1. 避免使用递归调用：递归调用虽然简洁，但会占用较多的内存。

可以使用迭代的方式实现二进制搜索算法，通过循环来替代递归，从而减少内存的占用。

2. 优化指针的使用：可以通过使用索引而不是指针来记录数组的起始位置、结束位置和中间位置。

递归经典题目
递归是一种常用的算法技术，它可以用来解决许多经典问题。

以下是一些经典的递归问题：
1. 斐波那契数列：这是一个经典的递归问题，其中每个数字是前两个数字的和。

例如，斐波那契数列的前几个数字是 0、1、1、2、3、5、8、13、21 等。

2. 阶乘函数：这是一个计算一个数的阶乘的递归函数。

例如，5 的阶乘是 5 4 3 2 1 = 120。

3. 汉诺塔问题：这是一个经典的递归问题，其中有一些盘子需要从一根柱子移动到另一根柱子，每次只能移动一个盘子，并且不能将一个较大的盘子放在较小的盘子上面。

4. 二分搜索：这是一个在排序数组中查找特定元素的递归算法。

它首先将数组分成两半，然后根据目标值与中间元素的比较结果，选择另一半继续搜索。

5. 回溯算法：这是一种通过递归搜索所有可能解的算法，通常用于解决约束满足问题。

例如，排列组合问题、八皇后问题等。

6. 分治算法：这是一种将问题分解为更小的子问题，然后递归地解决这些子问题的算法。

例如，归并排序和快速排序等。

7. 动态规划：这是一种使用递归和备忘录（或称为记忆化）的方法，用于解决具有重叠子问题和最优子结构的问题。

例如，背包问题和最短路径问题等。

这些经典的递归问题涵盖了不同的应用领域和算法类型，可以通过学习和解决这些问题来提高自己的编程和算法技能。