ToB企服应用市场:ToB评测及商务社交产业平台

标题: 递归相关知识2 [打印本页]
作者: 麻花痒    时间: 2023-7-14 20:42
标题: 递归相关知识2
递归相关知识2

多路递归--斐波那契额数列
  1. import java.util.Arrays;
  3. //递归求斐波那契第n项
  4. public class feibonaqie {
  5.     public static int fibonacci(int n){
  6.         int []cache=new int[n+1];
  7.         Arrays.fill(cache,-1);
  8.         cache[0]=0;
  9.         cache[1]=1;//[0,1,-1,-1,-1,-1]
  10.         return f(n,cache);
  11.     }
  13.     public static int f(int n,int[]cache){
  14.      /*   if(n==0){
  15.             return 0;
  16.         }
  17.         if(n==1){
  18.             return 1;
  19.         }*/
  20.         if(cache[n]!=-1){
  21.             return cache[n];
  22.         }
  23.         int x=f(n-1,cache);
  24.         int y=f(n-2,cache);
  25.         cache[n]=x+y;
  26.         return cache[n];
  27.     }
  29.     /*public static void main(String[] args) {
  30.         int f=f(8);
  31.         System.out.println(f);
  32.     }*/
  33. }
复制代码
汉诺塔问题
  1. import java.util.LinkedList;
  3. public class hannuota {
  4.     static LinkedList<Integer> a=new LinkedList<>();//三根柱子
  5.     static LinkedList<Integer> b=new LinkedList<>();
  6.     static LinkedList<Integer> c=new LinkedList<>();
  8.     //3 2 1
  10.     static void init(int n){
  11.         for(int i=n;i>=1;i--){
  12.             a.addLast(i);
  13.         }
  14.     }
  15.      /*
  16.      Params:n-圆席个数
  17. a-源
  18. b-信
  19. c-目
  20.       */
  22.     static void move(int n,LinkedList<Integer> a,LinkedList<Integer> b,
  23.                      LinkedList<Integer> c){
  24.         if(n==0){
  25.             return;
  26.         }
  27.        move(n-1,a,c,b);
  28.         c.addLast(a.removeLast());//中间
  29.         print();
  30.         move(n-1,b,a,c);
  31.     }
  32.     public static void main(String[]args){
  33.         init(3);
  34.       /*  System.out.println(a);
  35.         System.out.println(b);
  36.         System.out.println(c);
  37.         b.addLast(a.removeLast());*/
  38.         print();
  39.         move(3,a,b,c);
  40.     }
  45.     private static void print() {
  46.         System.out.println("----------------------");
  47.         System.out.println(a);
  48.         System.out.println(b);
  49.         System.out.println(c);
  50.     }
  51. }
复制代码
爆栈问题
  1. //递归求和n+n-1+...+1
  2. public class baozhan {
  3.     //f(n)=f(n-2)+n;
  6.     public static long sum(long n){
  7.      if(n==1){
  8.          return 1;
  9.      }
  10.      return sum(n-1)+n;
  11.     }
  13.     public static void main(String[] args) {
  14.        /* System.out.println(sum(15000));*///爆栈
  15.     }
  16. }
复制代码
杨辉三角

第一种,时间复杂度最高,空间复杂度最高
  1. public class yanghuisanjiao {
  3.     private static int element(int i,int j){
  4.         if(j==0||i==j){
  5.             return 1;
  6.         }
  7.         return element(i-1,j-1)+element(i-1,j);
  8.     }
  9. private static void printSpace(int n,int i){
  10.         int num=(n-1-i)*2;
  11.      for (int j = 0; j < num; j++) {
  12.          System.out.print(" ");
  13.      }
  14. }
  15.     public static void print(int n){
  16.         for (int i = 0; i < n; i++) {
  17.             printSpace(n,i);
  18.             for (int j = 0; j <= i; j++) {
  19.                 System.out.printf("%-4d",element(i,j));
  20.             }
  21.             System.out.println();
  22.         }
  23.     }
  24.     public static void main(String[] args) {
  25.       /*  System.out.println(element(4,2));*/
  26.         print(5);
  27.     }
  28. }
复制代码
数据结构素数实现
  1. public class yanghuisanjiao1 {
  2. /*
  3. 优化1·使用二组数组记忆法
  4. Params:triangle-二维数组
  5. i-行坐标
  6. j-列坐标
  7. Returns:该坐标元素值
  8. */
  9.     private static int element1(int[][]triangle,int i,int j){
  10.         if(triangle[i][j]>0){
  11.             return triangle[i][j];
  12.         }
  13.         if(j==0||i==j){
  14.             triangle[i][j]=1;
  15.             return 1;
  16.         }
  17.         triangle[i][j]=element1(triangle,i-1,j-1)+element1(triangle,i-1,j);
  18.         return triangle[i][j];
  19.     }
  20. private static void printSpace(int n,int i){
  21.         int num=(n-1-i)*2;
  22.      for (int j = 0; j < num; j++) {
  23.          System.out.print(" ");
  24.      }
  25. }
  26.     public static void print(int n){
  27.         int[][]triangle=new int[n][];
  28.         for (int i = 0; i < n; i++) {//行
  29.             triangle[i]=new int[i+1];
  30.          /*   printSpace(n,i);*/
  31.             for (int j = 0; j <= i; j++) {
  32.                 System.out.printf("%-4d",element1(triangle,i,j));
  33.             }
  34.             System.out.println();
  35.         }
  36.     }
  37.     public static void main(String[] args) {
  38.       /*  System.out.println(element(4,2));*/
  39.         print(5);
  40.     }
  41. }
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4