整合营销的案例,seo快速排名软件网站,江西省城住房和城乡建设厅网站,wordpress中文免费主题目录
一、递归问题
1、斐波那契数列
2、汉诺塔问题
3、全排列问题
4、整数划分问题
二、递归式求解
1、代入法
2、递归树法
3、主定理法
三、 分治问题
1、二分搜索
2、大整数乘法 一、递归问题
1、斐波那契数列 斐波那契数列不用过多介绍#xff0c;斐波那契提出…目录
一、递归问题
1、斐波那契数列
2、汉诺塔问题
3、全排列问题
4、整数划分问题
二、递归式求解
1、代入法
2、递归树法
3、主定理法
三、 分治问题
1、二分搜索
2、大整数乘法 一、递归问题
1、斐波那契数列 斐波那契数列不用过多介绍斐波那契提出的繁殖兔子问题。 斐波那契递推式如下 斐波那契代码
//斐波那契数列
import java.util.Scanner;
public class Fibonacci {public static void main(String [] args){int inputnew Scanner(System.in).nextInt();System.out.println(factorial(input));}public static int factorial(int n){if(n0||n1)return 1;else{return factorial(n-1)factorial(n-2);}}
}2、汉诺塔问题 汉诺塔问题也是一个经典问题。一般分为三个步骤
1把n-1个盘子从A柱移到B柱
2把最底层1个盘子从A柱移到C柱
3把B柱n-1个盘子移到C柱。 完整代码
package RecursionAndDivide;
import java.util.Scanner;
public class Hanoi {public static void main(String[] args){int inputnew Scanner(System.in).nextInt();move(input,A,B,C);} public static void move(int n,char a,char b,char c){if(n1)System.out.println(a-c); //else {move(n-1,a,c,b); //n-1个从a移到bmove(1,a,b,c); //底层1个从a移到cmove(n-1,b,a,c); //n-1个从b移到c}}
}
3、全排列问题 使用递归的方式输出数组中的全排列步骤如下
0判定是否数组中仅有一个数那么输出该排列形式。请注意k作为固定头在每一层进行修改排列顺序的头部
1首先将第一个数与后面的每一个数进行交换这是一个k到m的循环。得到 1,2,3,4,...,n 2,1,3,4,...,n 3,1,2,4,...,n
2计算除第一个数以外后面的全排列。
3交换第一个数与刚刚那个数使数组恢复。 k作为固定头m作为尾一直不改变i作为固定头与循环中交换的数的索引。固定头依赖于第几层递归不同的递归只会改变数组排列的方式不会改变长度而尾不动所以每次输出只需要输出0到m索引的数组数也就是所有数组的数。
完整代码
//全排列问题
public class Permutations {public static void main(String [] args){int []list{1,2,3,4,5};int k0;int mlist.length-1;Perm(list,k,m);} //产生全排列public static void Perm(int []list,int k,int m){if(km) {for(int i0;im;i)System.out.print(list[i]);System.out.println();}else{for(int ik;im;i){swap(list,i,k); Perm(list,k1,m);swap(list,i,k);}}}//交换数组中两个元素public static void swap(int []list,int i,int k){int templist[i];list[i]list[k];list[k]temp;}
}4、整数划分问题 整数划分问题就是把一个正整数拆分成若干个正整数相加的所有方式也可以使用递归来求解。定义p(n)为正整数n的划分总个数q(n,m)为正整数n划分为最大值为m的划分总个数。 有以下递归式成立 完整代码
public class IntegerDivide {public static void main(String[] args){System.out.println(q(6,6));}public static int q(int n, int m){if((n1)||(m1)) //且和或一样或的话出现q(1,2)会执行条件2返回q(1,1)return 1;if(nm)return q(n,n);if(nm)return 1q(n,n-1);return q(n,m-1)q(n-m,m);}
}
二、递归式求解
1、代入法 一般来说如果递归式成倍数下降可以n取指数形式平衡递归式的麻烦。换元求解就是不断回带递归式最后得到T1项忽略其他换元回变量n的项。 2、递归树法 递归树法就是将常数项逐层展开成树叶子结点的形式并将每一层的量相加的总和为递归式的解。如下面这个题根节点就是递归式中的常数项n-1每一层叶子点个数就是子递推式的系数为2叶子结点的量只用n/2换元上一节点的量得到n/2-1以此类推那么递推树如下。 计算递推式每一层的和注意最后一层以1为结束当使用替代时请注意层数变化最后一层是。那么总和如下记得要用n替换k 对于这一类递归树有偏重的题可以参照下面这个做法找到最慢下去的叶节点路线就是大O的复杂度。 3、主定理法 主定理方法有一定局限性最没有局限性的是代入法但是很麻烦。 三、 分治问题
1、二分搜索 二分搜索原理
1初始数组是已经排好序的目的是某个数值是否存在并找到他的索引否则返回-1。
2大循环满足左值小于等于右值每次取中间值判断中间值是否为给定数值若是返回索引。
3判断是否小于中间值若是右值等于mid-1判断是否大于中间值若是左值等于mid1。
4如果不满足循环条件还没有找到给定值那么返回-1。 二分搜索算法的复杂度为Ologn应该建立在已排好序的数组上如果为了搜索而去排序复杂度就大大提升了。
//二分搜索
public static int Search(int arr[],int x,int n){int left0;int rightn-1;while(leftright){int mid(leftright)/2;if(xarr[mid])return mid;if(xarr[mid])leftmid1;else rightmid-1;}return -1;}
2、大整数乘法 由于大整数本身就会出现精度丢失问题另外乘积数过大也会出现数值溢出的问题。所以可以用数组存储大整数进行两个数组之间的乘法。 另外高复杂度Omn也是不能忽视的问题可以通过大整数拆成两段将中间二次计算的环节存入内存来减少复杂度。 比如下图X和Y都为n为二进制整数计算它们的乘积可以拆分成两个相等的n/2位的结构。 根据上面的式子改变BD这一项就重复计算了乘法计算的次数整体不变但是BD可以不用二次计算了这样就可以减少一次乘法计算6次乘法变为5次乘法。 复杂度相比于也有所降低。 相类似的矩阵乘法也可以用这种方式降低时间复杂度成为Strassen矩阵乘法。
