递归练习

曾经终败给现在 2022-08-18 02:05 288阅读 0赞

# 递归练习 #

在n个球中，任意取m个（不放回），求有多少种不同取法

public class Main {
        //在n个球中，任意取m个（不放回），求有多少种不同取法。
        public static int fun(int n, int m){
            //如果3个球中取4个，返回0
            if(n < m) return 0;
            //如果4个球中取4个，返回0
            if(n == m) return 1;
            //如果4个球中取0个，返回1
            if(m == 0) return 1;
            //假设n个球中有1个特殊球x,取法划分为：包含x和不包含x
            return fun(n-1, m-1) + fun(n-1, m);
        }
        public static void main(String[] args) {
            int sum = fun(10, 3);
            System.out.println(sum);
        }
    }

字符全排列

public class Main { 
     /** * @param data 数组 * @param begin 当前交换位置 */
     public static void fun(char[] data, int begin){
      if(begin == data.length){
       for(int i = 0; i<data.length; i++){
        System.out.print(data[i]);
       }
       System.out.println();
      }
      for(int i = begin; i < data.length; i++){
       {
       char c = data[i]; data[i] = data[begin]; data[begin] = c;}
       fun(data, begin+1);
       {
       char c = data[i]; data[i] = data[begin]; data[begin] = c;}
      }
     }
     public static void main(String[] args) {
      char[] data = "ABCDE".toCharArray();
      fun(data, 0);
     }
    }

两字符串求公共子字符最大个数

public class Main {
     public static int fun(String str1, String str2){
      if(str1.length() == 0 || str2.length() == 0){
       return 0;
      }
      if(str1.charAt(0) == str2.charAt(0)){
       return fun(str1.substring(1), str2.substring(1)) + 1;
      }else{
       return Math.max(fun(str1.substring(1), str2), fun(str1, str2.substring(1)));
      }
    
     }
     public static void main(String[] args) {
      int n = fun("abcd", "bacd");
      System.out.println(n);
     }
    }

翻转串

publiv static void reversrString(String x){
        if(x==null || x.length()<2){
             return x;
        }
        return reversrString(x.subString(1)) + x.charAt(0);
    }

杨辉三角

public class Main {
     //计算第M层的第N个系数的计算方法
     public static int fun(int m, int n){
      //顶点1
      if(m == 0){
       return 1;
      }
      //每行两边的1
      if(n == 0 || n == m){
       return 1;
      }
      //中间位置数
      return fun(m-1, n-1) + fun(m-1, n);
     }
     public static void main(String[] args) {
      for(int i = 0; i<10; i++){
       for(int j = 0; j<=i; j++){
        System.out.print(fun(i, j));
       }
       System.out.println();
      }
     }
    }

字母组合问题

public class Main {
     static int fun(int m, int n){
      if(m == 0 && n == 0){
       return 0;
      }
      if(m == 0 || n == 0){
       return 1;
      }
        //A开头和B开头
      return fun(m-1, n) + fun(m, n-1);
     }
     public static void main(String[] args) {
      System.out.println(fun(10,10));
     }
    }

整数n的加法所有划分

public class Main { 
     /** * @param n * @param a * @param k */
     //数字分解
     static void fun(int n, int[] a, int k){
      if(n <= 0){
       for(int i = 0; i < k; i++){
        if(i == k-1){
         System.out.print(a[i]);
        }else{
         System.out.print(a[i] + "+");
        }
       }
        System.out.println();
       return;
      }
      for(int i = n; i > 0; i--){
       if(k > 0 && i > a[k-1]) continue;
       //将每行的开始数字存入0下标的位置 例如：6,5,4,3,2,1
       a[k] = i;
       //将剩余部分,在进行分解
       fun(n-i, a, k + 1);
      }
     }
     public static void main(String[] args) {
      int[] a = new int[100];
      fun(6, a, 0);
     }
    }

对于长度为5位的一个01串，每一位都可能是0或1，一共有32种可能。它们的前几个是：00000，00001，00010，00011，00100

public class Main {
     public static void fun(String str){
      if(str.length() == 5){
       System.out.println(str);
       return;
      }
      fun(str + "0");
      fun(str + "1");
     }
     public static void main(String[] args) {
      String str = "";
      fun(str);
     }
    }

2的次幂表示  
问题描述  
　　任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。  
　　将这种2进制表示写成2的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：137=2^7+2^3+2^0  
　　现在约定幂次用括号来表示，即a^b表示为a（b）  
　　此时，137可表示为：2（7）+2（3）+2（0）  
　　进一步：7=2^2+2+2^0 （2^1用2表示）  
　　3=2+2^0  
　　所以最后137可表示为：2（2（2）+2+2（0））+2（2+2（0））+2（0）  
　　又如：1315=2^10+2^8+2^5+2+1  
　　所以1315最后可表示为：  
　　2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）

import java.util.Scanner;
    public class Main {
     public static void fun(int n){
      if(n == 0){
       System.out.print("0");
       return;
      }
      String er = Integer.toBinaryString(n);
      char data[] = er.toCharArray();
      boolean flag = false;
      for(int i = 0; i < data.length; i++){
       if(data[i] == '1'){
        if(flag){
         System.out.print("+");
        }
        flag = true;
        if(data.length - i - 1 == 1){
         System.out.print("2");
        }else{
         System.out.print("2");
         System.out.print("(");
         fun(data.length - i - 1 );
         System.out.print(")");
        }
       }
      }
     }
     public static void main(String[] args) {
      Scanner read = new Scanner(System.in);
      int n = read.nextInt();
      boolean flag = false;
      String er = Integer.toBinaryString(n);
      char data[] = er.toCharArray();
      for(int i = 0; i < data.length; i++){
       if(data[i] == '1'){
        if(flag){
         System.out.print("+");
        }
        flag = true;
        if(data.length - i - 1 == 1){
         System.out.print("2");
        }else{
         System.out.print("2");
         System.out.print("(");
         fun(data.length - i - 1 );
         System.out.print(")");
        }
       }
      }
     }
    }