递归与递推

递归与递推

-1.
枚举形式：　　　　状态空间规模：　　　　一般遍历方式：
多项式　　　　　　ｎ＾ｋ，ｋ为常数　　　循环（for），递推
指数　　　　　　　k^n, k 为常数　　　　　递归，位运算
排列　　　　　　　 n!　　　　　　　　　　递归，permutation
组合　　　　　　　　　　　　　　　　　　递归+剪枝
===============================================
-2.3个操作：
1.缩小
2.求解
3.扩展

===============================================

1· 递归实现指数型枚举（92 进阶指南）

• 解题思路：
  这是一道在1~n中随机选取多个数，输出有可能的选择方案。 这等价于每个整数可以选或不选，所有可能的方案总数共有2^n 种。这道题可以进行一次循环，利用位运算来列举所有的选择方案（位运算+ queue
  ）。在这里使用递归求解，在每次递归中分别尝试某个数“选”或“不选”两条分支，将尚未确定的整数数量减少1， 从而转化为一个规模更小的同类问题。
• 这道题的空间规模 是 2^n

import java.util.Scanner;
import java.util.ArrayList;
 public class Main{
    static int n;
    List<Integer>  res = new ArrayList<>();
    public static void main(String [] args) {
        Scanner  input = new Scanner(System.in);
        n = input.nextInt();
        Main m = new Main();
        m.calc(1);
    }

    public void calc( int x) {
         if( x == n + 1) {
            for(int i =0; i< res.length; i++ ) {
                System.out.println( res[i] + " ");
                return;
            } 
         }
        /* 不选 x 分支*/
        calc( x+1); /* 求解子问题 */
      /* 选 x 分支 */
      res.add( x);/* 记录 x 已被选择*/
      calc（x + 1）；/* 求解子问题*/
      res.remove(res.size() - 1);
    }
}

2· 递归实现组合枚举（93 进阶指南）

-. 从1~n 这 n 个整数中随机选出m 个，输出所有可能的选择方案. 只需要在上方calc 函数开头，添加。 这就是所谓的“剪枝”

public vois calc(int x) {
    /* 剪枝情况：1. 已经选了超过m个数， 2.即使再选上剩余所有的数也不够 
 m个*/
    if(res.size() > m || res.size() + (n - x + 1) < m ) {
        return;
    }
}

3· 递归实现排列型枚举（94 进阶指南）

-解题思路：
该问题也被称为全排问题，所有可能的方案总数有 n ! 种。在这里，递归需要求解的问题是“把指定的 n 个整数按照任意次序排列”， 在每次递归中，我们尝试把每个可用的数作为数列的下一个数，求解“把剩余的 n-1 个整数按照任意次序排列”

List<Integer> order = new ArrayList<>(); // 按顺序依次记录被选择的整数
boolean chosen[20];

public void calc(int k) {
    if( k == n + 1 ) { // 问题边界
       for(int i = 1; i <= n ; i++) {
            System.out.println( order[i] + " ");
       }
      return;   
    }
  for(int i=1; i<=n; i++) {
      if( chosen[i]) continue;
      order[k] = i;
      clac( k + 1);
      chosen[i] = false;
      order[k] = 0; // 这一行可以省略 
  }
}

4· 费解的开关（95 进阶指南）