递归与分治策略
1、递归的总体思想:
对于一个大规模的问题无法直接求解,可以把这个大问题划分成k个小问题,如果小问题也无法求解时,继续划分,直到问题规模足够小,很容易求出解为止。然后把求出小规模问题的解合并为一个更大规模的问题的解,至底向上逐步求出原来问题的解。
2.分治思想:
将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便于各个击破,分而治之。
废话少说看实例
例1、阶乘函数
算法:
int fac(int x){ if(x==1){ return x; }else{ return fac(x-1)*x; } }
2、递归全排列问题:n个元素进行全排列。
设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。
设R={r1,r2,…,rn}是要进行排列的n个元素,Ri=R-{ri}。
集合X中元素的全排列记为perm(X)。
(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下:
当n=1时,perm(R)=(r),其中r是集合R中唯一的元素;
当n>1时,perm(R)由(r1)perm(R1),(r2)perm(R2),…,(rn)perm(Rn)构成。
public class Order { /** * 递归全排序 */ public static void main(String[] args) { int[] a={1,2,3}; pai(a,0,a.length); } public static void pai(int[] a,int start ,int end){ if(start ==end){ for(int i=0;i<end;i++){ //输出语句 System.out.print(a[i]); } System.out.println(); } else{ for(int j=start;j<end;j++){ int b=a[start]; a[start] =a[j]; //交换位置 a[j] =b; pai(a,start+1,end); b=a[start]; a[start] =a[j]; //返回到原来的样子 a[j] =b; } } } }
待续........
相关推荐
ACM培训基础算法之递归PPT详解 包括递归的一些基础思想和一些经典例题
数据结构与算法之递归,深入浅出,很深刻,很透彻。
.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法
递归算法详解递归算法详解递归算法详解递归算法详解
NULL 博文链接:https://wangweiwei358.iteye.com/blog/1485477
18.递归算法与递归算法应用.ppt
数据结构和算法学习之递归
5!递归算法和非递归算法,面试专用,适合新手
牛顿迭代算法与递归算法的概念和区别 很有帮助
快速选择非递归与递归算法实现
VC对磁盘文件遍历搜索的递归算法和非递归算法 里面的文档是讲解递归算法和递归算法的 里面还有一个Vc工程文件,是我自己写的,关于非递归算法,其实里面那些被注释掉的部分是递归算法,大家仔细看看就知道了,
使用C++,请给出此题的递归算法及非递归算法。
acm递归算法总结acm递归算法总结!!!!!!!!!!!!!!!!!!!!!!!
递归算法转为非递归算法。方法、过程,用栈的原理
应用于java中的算法 递归算法:是一种直接或者间接地调用自身的算法。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。
本篇文章主要介绍了ios使用OC写算法之递归实现八皇后,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
【GA-ELMAN回归预测】基于遗传算法优化递归神经网络神经网络实现数据预测 【GA-ELMAN回归预测】基于遗传算法优化递归神经网络神经网络实现数据预测 【GA-ELMAN回归预测】基于遗传算法优化递归神经网络神经网络实现...
计算机算法与分析试验递归调用快速排序 全排列仅供参考
这是一个相当齐全的算法课件 里面包含了很多的内容和实例 使我们上课时老师的课件 希望对大家有帮助
1.5.递归算法.wmv 1.4.枚举(穷举)算法.wmv 3.2.网状关系:图(2).wmv 3.2.网状关系:图(1).wmv 3.1.层次关系结构:树(3).wmv 3.1.层次关系结构:树(2).wmv 3.1.层次关系结构:树(1).wmv 2.3.后进先出结构:栈.wmv 2.1...