实验一 递归与分治算法
- 格式:doc
- 大小:422.00 KB
- 文档页数:4
递归与分治算法心得
递归与分治算法是算法设计中常见的两种方法,它们在解决问题时都采用了“分而治之”的思想,将问题分解成更小的子问题,然后通过递归调用或者合并子问题的解来得到原问题的解。
通过我的学习和实践,我深刻认识到了递归与分治算法的重要性和优势。
首先,递归算法可以使问题的描述更加简单明了。
通过将问题转化为自身的子问题,我们可以建立起更为简洁优美的数学模型。
其次,递归算法可以使问题的解决过程更加自然。
在递归过程中,我们可以利用已知的子问题解决同类问题,实现代码的复用和模块化。
此外,递归算法还可以解决一些重要的数学问题,如斐波那契数列和二分查找等。
分治算法则更加注重问题的分解和合并。
它将问题划分成若干个规模相同或相近的子问题,然后将子问题的解合并起来得到原问题的解。
这种方法在解决某些复杂问题时具有很大的优势。
例如,在排序算法中,归并排序采用了分治算法的思想,将待排序的序列分成两个长度相等的子序列,然后递归地对子序列排序,最后将子序列合并成有序序列。
这种算法具有较高的稳定性和灵活性,常常被应用于海量数据的排序任务中。
总之,递归与分治算法是算法设计中不可或缺的两种方法。
在解决问题时,我们应该根据具体情况选择合适的算法,并在实践中不断探索、总结和优化。
只有这样,我们才能更好地应对日益复杂多变的计算机科学挑战。
递归和分治法摘要:一、递归和分治法简介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)差消化简:利用两个方程相减,将右边的项尽可能消去,以达到降阶的目的。
递归和分治法
摘要:
递归和分治法
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++递归与分治算法的资料请关注其它相关⽂章!。
递归与分治算法
递归和分治算法是计算机科学中两种常见的算法设计技术。
递归是一种直接或间接调用自身函数或者方法的算法。
在递归算法中,函数在其定义中使用了函数自身的调用。
递归算法通常用于解决需要重复执行相同任务的问题,例如遍历树结构、递归搜索等。
递归算法的优点是代码简洁、易于理解,但需要注意递归深度的限制以及可能引发栈溢出的问题。
分治算法是一种将问题分解为多个子问题,并分别解决子问题的算法。
分治算法通过将大问题分解为小问题,并将小问题的解合并成大问题的解来解决问题。
分治算法通常用于排序、查找、矩阵乘法等问题。
分治算法的优点是可以将复杂问题分解为简单问题,降低问题的复杂度,但需要注意分解的子问题必须是相互独立的。
在实际应用中,递归和分治算法通常结合使用。
例如,快速排序算法就是一种典型的分治算法,它通过选择一个基准元素,将数组分为两个子数组,并对每个子数组递归地进行排序,最终合并两个有序子数组得到排序后的数组。
总之,递归和分治算法是计算机科学中重要的算法设计技术,它们可以有效地解决许多复杂的问题。
在实际应用中,需要根据问题的特点选择合适的算法,并注意算法的时间复杂度和空间复杂度。
南京信息工程大学 实验(实习)报告
实验(实习)名称 递归与分治算法编程 实验(实习)日期 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开发工具的使用。