遞歸相關知識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);
    }
}

時間複雜度,空間複雜度同時提升

public class yanghuisanjiao2 {
/*
優化2·使用二組數組記憶法
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 print2(int n){
       int[]row=new int[n];
        for (int i = 0; i < n; i++) {//行
      /*      triangle[i]=new int[i+1];*/
         /*   printSpace(n,i);*/
            createRow(row,i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d",row[j]);
            }
            System.out.println();
        }
    }
    private static void createRow(int[]row,int i){
        if(i==0){
            row[0]=1;
            return;
        }
        for (int j = i; j >0 ; j--) {
            row[j]=row[j]+row[j-1];
        }
    }

    public static void main(String[] args) {
      /*  System.out.println(element(4,2));*/
        print2(5);
    }
}

數據結構素數實現

class FuShu{
    int real; //實部real、虛部image；
    int image;
    FuShu(int real, int image) { //構造方法：賦初值；
        this.real = real;
        this.image = image;
    }

    FuShu add(FuShu s1) { // 加法運算 FuShu add(FuShu s1)；
        FuShu tmp = new FuShu(real + s1.real, image + s1.image);
        return tmp;
    }
}

public class xubu {
    public static void main(String[] args) { //兩個複數相加，輸出結果
        FuShu s1 = new FuShu(1, 2);
        FuShu s2 = new FuShu(2, 3);
        FuShu s3 = s2.add(s1);
        System.out.println(s3.real + " + " + s3.image + "i");
    }

}