递归相关知识2
多路递归--斐波那契额数列
- import java.util.Arrays;
- //递归求斐波那契第n项
- public class feibonaqie {
- public static int fibonacci(int n){
- int []cache=new int[n+1];
- Arrays.fill(cache,-1);
- cache[0]=0;
- cache[1]=1;//[0,1,-1,-1,-1,-1]
- return f(n,cache);
- }
- public static int f(int n,int[]cache){
- /* if(n==0){
- return 0;
- }
- if(n==1){
- return 1;
- }*/
- if(cache[n]!=-1){
- return cache[n];
- }
- int x=f(n-1,cache);
- int y=f(n-2,cache);
- cache[n]=x+y;
- return cache[n];
- }
- /*public static void main(String[] args) {
- int f=f(8);
- System.out.println(f);
- }*/
- }
复制代码 汉诺塔问题
- import java.util.LinkedList;
- public class hannuota {
- static LinkedList<Integer> a=new LinkedList<>();//三根柱子
- static LinkedList<Integer> b=new LinkedList<>();
- static LinkedList<Integer> c=new LinkedList<>();
- //3 2 1
- static void init(int n){
- for(int i=n;i>=1;i--){
- a.addLast(i);
- }
- }
- /*
- Params:n-圆席个数
- a-源
- b-信
- c-目
- */
- static void move(int n,LinkedList<Integer> a,LinkedList<Integer> b,
- LinkedList<Integer> c){
- if(n==0){
- return;
- }
- move(n-1,a,c,b);
- c.addLast(a.removeLast());//中间
- print();
- move(n-1,b,a,c);
- }
- public static void main(String[]args){
- init(3);
- /* System.out.println(a);
- System.out.println(b);
- System.out.println(c);
- b.addLast(a.removeLast());*/
- print();
- move(3,a,b,c);
- }
- private static void print() {
- System.out.println("----------------------");
- System.out.println(a);
- System.out.println(b);
- System.out.println(c);
- }
- }
复制代码 爆栈问题
- //递归求和n+n-1+...+1
- public class baozhan {
- //f(n)=f(n-2)+n;
- public static long sum(long n){
- if(n==1){
- return 1;
- }
- return sum(n-1)+n;
- }
- public static void main(String[] args) {
- /* System.out.println(sum(15000));*///爆栈
- }
- }
复制代码 杨辉三角
第一种,时间复杂度最高,空间复杂度最高
- public class yanghuisanjiao {
- private static int element(int i,int j){
- if(j==0||i==j){
- return 1;
- }
- return element(i-1,j-1)+element(i-1,j);
- }
- private static void printSpace(int n,int i){
- int num=(n-1-i)*2;
- for (int j = 0; j < num; j++) {
- System.out.print(" ");
- }
- }
- public static void print(int n){
- for (int i = 0; i < n; i++) {
- printSpace(n,i);
- for (int j = 0; j <= i; j++) {
- System.out.printf("%-4d",element(i,j));
- }
- System.out.println();
- }
- }
- public static void main(String[] args) {
- /* System.out.println(element(4,2));*/
- print(5);
- }
- }
复制代码 数据结构素数实现
- public class yanghuisanjiao1 {
- /*
- 优化1·使用二组数组记忆法
- Params:triangle-二维数组
- i-行坐标
- j-列坐标
- Returns:该坐标元素值
- */
- private static int element1(int[][]triangle,int i,int j){
- if(triangle[i][j]>0){
- return triangle[i][j];
- }
- if(j==0||i==j){
- triangle[i][j]=1;
- return 1;
- }
- triangle[i][j]=element1(triangle,i-1,j-1)+element1(triangle,i-1,j);
- return triangle[i][j];
- }
- private static void printSpace(int n,int i){
- int num=(n-1-i)*2;
- for (int j = 0; j < num; j++) {
- System.out.print(" ");
- }
- }
- public static void print(int n){
- int[][]triangle=new int[n][];
- for (int i = 0; i < n; i++) {//行
- triangle[i]=new int[i+1];
- /* printSpace(n,i);*/
- for (int j = 0; j <= i; j++) {
- System.out.printf("%-4d",element1(triangle,i,j));
- }
- System.out.println();
- }
- }
- public static void main(String[] args) {
- /* System.out.println(element(4,2));*/
- print(5);
- }
- }
复制代码 免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作! |