下载文档原格式
递归与分治算法心得
递归与分治算法是算法设计中常见的两种方法，它们在解决问题时都采用了“分而治之”的思想，将问题分解成更小的子问题，然后通过递归调用或者合并子问题的解来得到原问题的解。
通过我的学习和实践，我深刻认识到了递归与分治算法的重要性和优势。
首先，递归算法可以使问题的描述更加简单明了。
通过将问题转化为自身的子问题，我们可以建立起更为简洁优美的数学模型。
其次，递归算法可以使问题的解决过程更加自然。
在递归过程中，我们可以利用已知的子问题解决同类问题，实现代码的复用和模块化。
此外，递归算法还可以解决一些重要的数学问题，如斐波那契数列和二分查找等。
分治算法则更加注重问题的分解和合并。
它将问题划分成若干个规模相同或相近的子问题，然后将子问题的解合并起来得到原问题的解。
这种方法在解决某些复杂问题时具有很大的优势。
例如，在排序算法中，归并排序采用了分治算法的思想，将待排序的序列分成两个长度相等的子序列，然后递归地对子序列排序，最后将子序列合并成有序序列。
这种算法具有较高的稳定性和灵活性，常常被应用于海量数据的排序任务中。
总之，递归与分治算法是算法设计中不可或缺的两种方法。
在解决问题时，我们应该根据具体情况选择合适的算法，并在实践中不断探索、总结和优化。
只有这样，我们才能更好地应对日益复杂多变的计算机科学挑战。
递归和分治法摘要：一、递归和分治法简介1.递归2.分治法二、递归和分治法的应用1.递归在编程中的应用2.分治法在编程中的应用三、递归和分治法的优缺点1.递归的优缺点2.分治法的优缺点四、递归和分治法在实际问题中的应用案例1.递归在实际问题中的应用案例2.分治法在实际问题中的应用案例五、递归和分治法在我国教育领域的应用1.递归在我国教育领域的应用2.分治法在我国教育领域的应用六、递归和分治法在未来的发展前景1.递归在未来的发展前景2.分治法在未来的发展前景正文：递归和分治法是计算机科学中两种解决问题的方法，它们都具有广泛的应用。
递归是一种函数调用自身的技术，通常用于解决具有相似子问题的复杂问题。
分治法是一种将大问题分解成小问题，然后逐个解决小问题的方法，最后将小问题的解合并得到大问题的解。
递归在编程中有广泛的应用，例如计算阶乘、快速排序等。
递归的优点是可以简洁地表示复杂问题，但缺点是可能会导致栈溢出，因此需要合理设计递归函数。
分治法在编程中也有广泛的应用，例如归并排序、大整数乘法等。
分治法的优点是可以有效地处理大规模问题，但缺点是可能会导致过多的子问题，增加计算复杂度。
在实际问题中，递归和分治法都有许多应用案例。
例如，在图像处理中，快速傅里叶变换（FFT）算法利用了递归和分治法来高效地计算离散傅里叶变换。
在我国教育领域，递归和分治法被广泛应用于计算机科学教育，帮助学生理解和掌握基本的算法思想。
未来，递归和分治法仍将在计算机科学领域发挥重要作用。
随着科技的进步，递归和分治法将应用于更复杂的问题，如人工智能、大数据处理等领域。
算法分析(第二章)：递归与分治法一、递归的概念知识再现：等比数列求和公式：1、定义：直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
2、与分治法的关系：由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。
3、递推方程：(1)定义：设序列01,....na a a简记为{na}，把n a与某些个()ia i n<联系起来的等式叫做关于该序列的递推方程。
(2)求解：给定关于序列{n a}的递推方程和若干初值，计算n a。
4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序5、优缺点：优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
二、递归算法改进：1、迭代法：(1)不断用递推方程的右部替代左部(2)每一次替换，随着n的降低在和式中多出一项(3)直到出现初值以后停止迭代(4)将初值代入并对和式求和(5)可用数学归纳法验证解的正确性2、举例：-----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1(1)1T n T nT=−+=()(1)1W n W n nW=−+−（1）=021n-23()2(1)12[2(2)1]12(2)21...2++2 (121)n n n T n T n T n T n T −−=−+=−++=−++==++=−（1）2 ()(1)1((n-2)+11)1(2)(2)(1)...(1)12...(2)(1)(1)/2W n W n n W n n W n n n W n n n n =−+−=−−+−=−+−+−==++++−+−=−3、换元迭代：(1)将对n 的递推式换成对其他变元k 的递推式 (2)对k 进行迭代(3)将解（关于k 的函数）转换成关于n 的函数4、举例：---------------二分归并排序---------------()2(/2)1W n W n n W =+−（1）=0（1）换元：假设2kn =，递推方程如下()2(/2)1W n W n n W =+−（1）=0 → 1(2)2(2)21k k k W W W−=+−（0）=0（2）迭代求解：12122222321332133212()2(2)212(2(2)21)212(2)22212(2)2*2212(2(2)21)2212(2)222212(2)3*2221...2(0)*2(22...21)22k k k k k k k k k k k k k k k k k k k k k k k k W n W W W W W W W W k k −−−−−−−+−+−−−=+−=+−+−=+−+−=+−−=+−+−−=+−+−−=+−−−==+−++++=−1log 1n n n +=−+（3）解的正确性—归纳验证： 证明递推方程的解是()(1)/2W n n n =−()(1)1W n W n n W =−+−（1）=0,(n 1)=n +n=n(n-1)/2+n =n[(n-1)/2+1]=n(n+1)/2n W W +方法：数学归纳法证 n=1,W(1)=1*(1-1)/2=0假设对于解满足方程，则（）---------------快速排序--------------------->>>平均工作量：假设首元素排好序在每个位置是等概率的112()()()(1)0n i T n T i O n n T −==+=∑ >>>对于高阶方程应该先化简，然后迭代(1)差消化简：利用两个方程相减，将右边的项尽可能消去，以达到降阶的目的。
![[理学]算法设计与分析课件 第2章 递归与分治_OK](https://uimg.taocdn.com/359bd9ff4a7302768f99395b.webp)
递归和分治法
摘要：
递归和分治法
1.递归和分治法的概念
2.递归的应用领域
3.分治法的应用领域
4.递归和分治法的优缺点
5.递归和分治法在实际问题中的应用举例
正文：
递归和分治法
递归和分治法是两种解决问题的方法，它们都广泛应用于计算机科学和数学中。
尽管它们有相似之处，但也有很大的不同。
递归是一种函数调用自身的技术，它通常用于解决需要重复执行相同或类似操作的问题。
递归的优势在于可以将复杂的问题分解成更简单的子问题，从而更容易地解决问题。
递归的缺点是它可能会导致栈溢出，特别是在处理大规模数据时。
分治法是一种将问题分解成更小、更简单的子问题的方法，然后递归地解决这些子问题，最后将解决方案组合起来以解决原始问题。
分治法的优势在于可以处理大规模数据，因为它可以减少栈空间的使用。
分治法的缺点是它需要更多的内存来存储中间结果。
递归和分治法都广泛应用于计算机科学和数学中，例如，递归可以用于计
算阶乘和递归遍历树，而分治法可以用于计算最大公约数和快速排序。
在实际问题中，递归和分治法都可以用来解决复杂的问题。
例如，递归可以用来解决八皇后问题，而分治法可以用来解决背包问题。
总的来说，递归和分治法都是非常有用的解决问题的方法，它们可以用于解决各种规模的问题。
C++递归与分治算法原理⽰例详解⽬录1. 汉诺塔问题2. 全排列问题3. 利⽤递归与分治策略寻找最⼤值4. 归并排序5. 快速排序6. 棋盘覆盖问题1. 汉诺塔问题递归算法，分为 3 步：将 n 个 a 上的盘⼦借助 c 移动到 b① 将 n-1 个 a 上的盘⼦借助 b 移动到 c② 将 a 上的盘⼦移动到 b③ 将 c 上的 n-1 个盘⼦借助 a 移动到 b所有盘⼦都移动到 b 上了12345678910void hanoi(int n,char a,char b,char c)//将n 个碟⼦从a 借助c 移到b{if(n==0)return; else {hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a); ｝｝2. 全排列问题问题描述：设R={r1,r2,…,rn}是要进⾏排列的n 个元素，求R 的全排列Perm(R)。
算法思路：① 从 n 个数中取出数列的第⼀个数，然后不断将数列中剩余的数与第⼀个数进⾏交换，计算剩余 n-1 个数的全排列。
② 对 n - 1 个数进⾏同样的递归操作，当交换的第⼀个数的下标 k 和 序列末尾的 m 相同时，说明前置所有数都已经交换完成，进⾏输出。
③ 递归结束后进⾏状态回调，保证不影响下⼀次递归的进⾏。
1234567891011121314151617void Perm(int list[], int k, int m){ if(k==m){for(int i=0;i<m;i++）{cout<<list[i]; } cout<<endl; return;}for(int i=k;i<m;i++){ swap(list[k], list[i]) Perm(list, k+1, m) swap(list[k], list[i])}}3. 利⽤递归与分治策略寻找最⼤值123456789101112131415161718#include <bits/stdc++.h>using namespace std;int find_max(int a[], int from, int to){ if(from>=to) return a[from]; int mid = (from + to)/2; int v1 = find_max(a, from, mid); int v2 = find_max(a, mid+1, to); if(v1<=v2) return v2; else return v1;}int main(){ int n, a[100000]; cin>>n;for(int i=0;i<n;i++){cin>>a[i];}cout<<find_max(a, 0, n-1);}4. 归并排序1234567891011#include <bits/stdc++.h>using namespace std; void merge_array(int a[], int from, int mid, int to){ int tmp[100000], idx_tmp=0; int i,j; for(i=from, j=mid+1; i<=mid && j<=to;){ if(a[i]<=a[j]) tmp[idx_tmp++] = a[i++];121314151617181920212223242526272829303132333435else tmp[idx_tmp++] = a[j++];}while(i<=mid) tmp[idx_tmp++]=a[i++];while(j<=to) tmp[idx_tmp++]=a[j++]; for(int i=from,j=0; i<=to;i++) a[i] = tmp[j++];} void merge_sort(int a[], int from, int to){ if(from < to){int mid = (from + to)/2;merge_sort(a, from, mid);merge_sort(a, mid+1, to);merge_array(a, from, mid, to); }}int main(){int n, a[100000];cin>>n;for(int i=0;i<n;i++){cin>>a[i]; } merge_sort(a, 0, n-1); for(int i=0;i<n;i++){ printf("%d ", a[i]);}}5. 快速排序图解快速排序：递归 + 交换法123456789101112131415161718192021222324252627#include <bits/stdc++.h>using namespace std;int sort_array(int a[], int from, int to){ int base = a[from]; int i,j; for(i=from, j=to; i<j;){while(a[j]>=base && i<j) j--;while(a[i]<=base && i<j) i++; //function swap() if(i<j){int t=a[i];a[i]=a[j];a[j]=t;} } a[from]=a[i]; a[i]=base;return i;}void quick_sort(int a[], int from, int to){ if(from>=to) return; int i = sort_array(a, from, to); quick_sort(a, from, i-1); quick_sort(a, i+1, to);}293031323334353637383940int main(){int n, a[100000];cin>>n;for(int i=0;i<n;i++){ cin>>a[i]; } quick_sort(a, 0, n-1);for(int i=0;i<n;i++){printf("%d ", a[i]);}}6. 棋盘覆盖问题1234567891011121314151617181920212223242526272829303132333435363738394041#include <bits/stdc++.h>using namespace std;int num=0;int a[1000][1000];void make_chess(int px, int py, int tx, int ty, int sze){ if(sze==1) return; num++; sze/=2;//左上if(px<tx+sze && py<ty+sze){ a[tx+sze-1][ty+sze]=num; a[tx+sze][ty+sze-1]=num;a[tx+sze][ty+sze]=num;}//右上 if(px<tx+sze && py>=ty+sze) { a[tx+sze-1][ty+sze-1]=num;a[tx+sze][ty+sze-1]=num;a[tx+sze][ty+sze]=num; } //左下 if(px>=tx+sze && py<ty+sze){a[tx+sze-1][ty+sze-1]=num; a[tx+sze-1][ty+sze]=num; a[tx+sze][ty+sze]=num; }//右下if(px>=tx+sze && py>=ty+sze){ a[tx+sze-1][ty+sze-1]=num; a[tx+sze-1][ty+sze]=num;a[tx+sze][ty+sze-1]=num;}//左上 if(px<tx+sze && py<ty+sze) make_chess(px, py, tx, ty, sze); else make_chess(tx+sze-1, ty+sze-1, tx, ty, sze);43444546474849505152535455565758596061626364656667686970//右上if(px<tx+sze && py>=ty+sze) make_chess(px, py, tx, ty+sze,sze); else make_chess(tx+sze-1, ty+sze, tx, ty+sze,sze);//左下 if(px>=tx+sze && py<ty+sze) make_chess(px, py, tx+sze, ty,sze); else make_chess(tx+sze, ty+sze-1, tx+sze, ty, sze); //右下if(px>=tx+sze && py>=ty+sze) make_chess(px, py, tx+sze, ty+sze, sze); else make_chess(tx+sze, ty+sze, tx+sze, ty+sze, sze);}int main(){ int k, px, py; int tx=0, ty=0; cin>>k>>px>>py; make_chess(px-1, py-1, tx, ty, k); for(int i=0; i<k; i++){for(int j=0; j<k; j++){printf("%2d ", a[i][j]);}cout<<endl; }}以上就是C++递归与分治算法原理⽰例详解的详细内容，更多关于C++递归与分治算法的资料请关注其它相关⽂章！。
递归与分治算法
递归和分治算法是计算机科学中两种常见的算法设计技术。
递归是一种直接或间接调用自身函数或者方法的算法。
在递归算法中，函数在其定义中使用了函数自身的调用。
递归算法通常用于解决需要重复执行相同任务的问题，例如遍历树结构、递归搜索等。
递归算法的优点是代码简洁、易于理解，但需要注意递归深度的限制以及可能引发栈溢出的问题。
分治算法是一种将问题分解为多个子问题，并分别解决子问题的算法。
分治算法通过将大问题分解为小问题，并将小问题的解合并成大问题的解来解决问题。
分治算法通常用于排序、查找、矩阵乘法等问题。
分治算法的优点是可以将复杂问题分解为简单问题，降低问题的复杂度，但需要注意分解的子问题必须是相互独立的。
在实际应用中，递归和分治算法通常结合使用。
例如，快速排序算法就是一种典型的分治算法，它通过选择一个基准元素，将数组分为两个子数组，并对每个子数组递归地进行排序，最终合并两个有序子数组得到排序后的数组。
总之，递归和分治算法是计算机科学中重要的算法设计技术，它们可以有效地解决许多复杂的问题。
在实际应用中，需要根据问题的特点选择合适的算法，并注意算法的时间复杂度和空间复杂度。
实验一分治与递归（4学时）一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。
三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。
四、程序代码五、实验结果首先按照提示输入数字：按回车键，得到此数划分的个数：此时您可以接着计算另一个数的划分个数：若要退出，请输入一个小于等于零的数：六、结果分析及程序功能经过和其它同学的实验数据对比，初步认定此程序基本正确，然而不足之处是只能得到划分的个数，而不能列出每个划分的详细情况。
一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题盘覆盖问题：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
三、程序代码四、实验结果按照提示输入特殊方格的行号和列号（起始行列号为0）：按回车键，得到一个矩阵，数字相同区域为一个L型骨牌覆盖：五、结果分析及程序功能得到的16*16棋盘覆盖结果正确，此程序的不足之处：只能设定特殊方格的行列号，而不能设定棋盘的大小。
实验二动态规划算法(4学时)一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。
例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
《算法设计与分析》实验指导书曹严元计算机与信息科学学院2007年5月目录实验一递归算法与非递归算法 (2)实验二分治算法 ................................................... 错误！未定义书签。
实验三贪心算法 (3)实验四动态规划 (2)实验五回溯法 (3)实验六分枝—限界算法 (4)实验七课程设计 (4)实验一递归与分治算法实验目的1.了解并掌握递归的概念，掌握递归算法的基本思想；2.掌握分治法的基本思想方法；3.了解适用于用递归与分治求解的问题类型，并能设计相应递归与分治算法；4.掌握递归与分治算法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。
实验二动态规划实验目的1.掌握动态规划的基本思想方法；2.了解适用于用动态规划方法求解的问题类型，并能设计相应动态规划算法；3.掌握动态规划算法复杂性分析方法。
实验三贪心算法实验目的1.掌握贪心法的基本思想方法；2.了解适用于用贪心法求解的问题类型，并能设计相应贪心法算法；3.掌握贪心算法复杂性分析方法分析问题复杂性。
实验五回溯法实验目的1.掌握回溯法的基本思想方法；2.了解适用于用回溯法求解的问题类型，并能设计相应回溯法算法；3.掌握回溯法算法复杂性分析方法，分析问题复杂性。
实验六 分枝—限界算法实验目的1. 掌握分枝—限界的基本思想方法；2. 了解适用于用分枝—限界方法求解的问题类型，并能设计相应动态规划算法；3. 掌握分枝—限界算法复杂性分析方法，分析问题复杂性。
实验七 课程设计实验目的1. 在已学的算法基本设计方法的基础上，理解算法设计的基本思想方法；2. 掌握对写出的算法的复杂性分析的方法，理解算法效率的重要性；3. 能运用所学的基本算法设计方法对问题设计相应算法，分析其效率，并建立对算法进行改进，提高效率的思想意识。
预习与实验要求1. 预习实验指导书及教材的有关内容，回顾所学过的算法的基本思想；2. 严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3. 认真听讲，服从安排，独立思考并完成实验。
南京信息工程大学 实验（实习）报告
实验（实习）名称 递归与分治算法编程 实验（实习）日期 5.9 得分 指导教师
院 计软 专业 软工 年级 2013 班次 3 姓名 吴礼俊 学号
20131344082
1．实验目的：
1）掌握递归与分治策略的基本思想
2）掌握递归算法在阶乘函数、Ackerman函数、整数划分等问题上的应用
3）掌握二分查找、合并排序、快速排序等问题的分治算法实现
4）熟悉MyEclipse或Eclipse等Java开发工具的使用。
2．实验内容：
1）采用MyEclipse或Eclipse编程实现基于分治策略的二分查找算法。
2）采用MyEclipse或Eclipse编程实现基于分治策略的合并排序算法。
3）采用MyEclipse或Eclipse编程实现基于分治策略的合并排序算法。
3．实验步骤
二分查找
public class Sorting {
public static int BinarySearch(int [] a,int x, int n){
int left=0;int right = n-1;
while(left<=right){
int middle = (left+right)/2;
if(x==a[middle]) return middle;
if(x>a[middle]) left=middle+1;
else right = middle-1;
}
return -1;
}
public static void main(String args[]){
int x,n;
int a[]={1,3,4,5,6,13,25};
x=6;
n=7;
int s;
s=BinarySearch(a,x,n);
System.out.println(s);
合并排序
public class Mergesort {
public static void mergeSort(int []a ){
int [] b = new int[a.length];
int s=1;
while(s
s+=s;
mergePass(b,a,s);
s+=s;
}
}
public static void mergePass(int []x,int []y,int s){
int i=0;
while(i<=x.length-2*s){
merge(x,y,i,i+s-1,i+2*s-1);
i=i+2*s;
}
if(i+s
else
for(int j=i;j
}
public static void merge(int []c,int []d,int l,int m,int r){
int i=1,j=m+1,k=1;
while((i<=m)&&(j<=r))
if(c[i]-(c[j])<=0)
d[k++]=c[i++];
else d[k++]=c[j++];
if(i>m)
for(int q=j;q<=r;q++)
d[k++]=c[q];
else
for(int q=i;q<=m;q++)
d[k++]=c[q];
}
public static void main(String args[]){
int a[]={1,7,2,6,4,5,8,3};
mergeSort(a);
for(int i=0;i<8;i++)
System.out.print(a[i]);
}
}
快速排序
public class QSort {
private static void qSort(int a[],int p,int r)
{
if(p < r){
int q = partition(a,p,r);
qSort(a,p,q-1);
qSort(a,q+1,r);
}
}
private static int partition(int a[],int p,int r)
{
int i=p;
int j= r + 1;
int x=a[p];
int temp;
while(true){
while((a[++i]-x)<0&&i
if(i>=j) break;
temp=a[i];
a[i]=a[j];
a[j]=temp;
// MyMath.swap(a,i,j);
}
a[p]=a[j];
a[j]=x;
return j;
}
public static void main(String[] args) {
int a[]={4,2,7,9,1};
qSort(a,0,4);
for(int i =0;;i++)
{
System.out.println(a[i]);
}
}
}
4．实验分析和总结
掌握了递归与分治策略的基本思想
掌握了递归算法在阶乘函数、Ackerman函数、整数划分等问题上的应用
掌握了二分查找、合并排序、快速排序等问题的分治算法实现
熟悉了MyEclipse或Eclipse等Java开发工具的使用。
