亚洲综合图片区自拍_思思91精品国产综合在线观看_一区二区三区欧美_欧美黑人又粗又大_亚洲人成精品久久久久桥本

首頁 > 數(shù)碼 > 內容頁

觀速訊丨萬字詳解遞歸與遞推

2023-02-05 12:31:18 來源：51CTO博客

前言

相信這個故事，朋友們應該都不陌生，

從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？「從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？『從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？……』」

(相關資料圖)

遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，并規(guī)定其他所有情況都能被還原為其基本情況。上面的故事就是一個簡單的遞歸，當然還有斐波那契數(shù)列等等，一系列我們熟知的。

遞歸

遞歸是將原問題拆成多個子問題然后求解，遞歸的代碼往往很短，可能進行重復求解某些問題，而??動態(tài)規(guī)劃是在遞歸的基礎上保存了子問題的解，避免重復計算。??下面我們通過例題來加深對遞歸的理解

斐波那契數(shù)列問題的遞歸

??爬樓梯問題力扣??

題目描述: 有 N 階樓梯，每次可以上一階或者兩階，求有多少種上樓梯的方法。

定義一個數(shù)組 dp 存儲上樓梯的方法數(shù)(為了方便討論，數(shù)組下標從 1 開始)，dp[i] 表示走到第 i 個樓梯的方法數(shù)目。第 i 個樓梯可以從第 i-1 和 i-2 個樓梯再走一步到達，走到第 i 個樓梯的方法數(shù)為走到第 i-1 和第 i-2 個樓梯的方法數(shù)之和。

思路一：直接遞歸

class Solution {    public int climbStairs(int n) {        if(n == 1)            return 1;        if(n == 2)            return 2;        return climbStairs(n-1) + climbStairs(n-2);    }}

發(fā)現(xiàn)超時了，原因是我們對于??climbStairs遞歸??進行了重復的計算，dp的方程不難看出：

思路二：動態(tài)規(guī)劃

class Solution {    public int climbStairs(int n) {        int[] dp = new int[n + 1];        dp[0] = 1;        dp[1] = 1;        for(int i = 2; i <= n; i++) {            dp[i] = dp[i - 1] + dp[i - 2];        }        return dp[n];    }}

遞歸實現(xiàn)排列型枚舉

題目描述：把 1～n 這 n個整數(shù)排成一行后隨機打亂順序，輸出所有可能的次序。輸入格式：一個整數(shù) n。輸出格式：按照從小到大的順序輸出所有方案，每行 1 個。首先，同一行相鄰兩個數(shù)用一個空格隔開。其次，對于兩個不同的行，對應下標的數(shù)一一比較，字典序較小的排在前面。數(shù)據(jù)范圍：1≤n≤9

輸入樣例：3輸出樣例：1 2 31 3 22 1 32 3 13 1 23 2 1

思路：數(shù)據(jù)范圍是1~9，推斷可能選擇的算法為，暴力遞歸，指數(shù)級別，dfs+剪枝排列型枚舉，依次枚舉每個數(shù)放到哪個位置，從小到大枚舉，肯定是字典序最小，轉換為遞歸搜索樹為：

import java.util.Scanner;/** * @Author 秋名山碼神 * @Date 2023/1/30 * @Description */public class 排列枚舉每個數(shù) {    static int N = 10;    static int n;    static int[] state = new int[N];//0表示沒放數(shù)，1~n表示放了哪個數(shù)    static boolean[] used = new boolean[N];    public static void dfs(int u){        if(u>n){            for(int i = 1; i<=n; i++){                System.out.print(state[i]);            }            System.out.println();            return;        }        //依次枚舉每個分支        for(int i = 1; i<=n; i++){            if(!used[i]){                state[u] = i;                used[i] = true;                dfs(u+1);                //恢復現(xiàn)場                state[u] = 0;                used[i] = false;            }        }    }    public static void main(String[] args) {        Scanner cin = new Scanner(System.in);        n = cin.nextInt();        dfs(1);//從1開始，最后打印除了就是字典序最小    }}

遞歸實現(xiàn)組合型枚舉

題目描述：從 1~n 這 n 個整數(shù)中隨機選出 m 個，輸出所有可能的選擇方案。

輸入格式：兩個整數(shù) n,m ,在同一行用空格隔開。

輸出格式：按照從小到大的順序輸出所有方案，每行1個。首先，同一行內的數(shù)升序排列，相鄰兩個數(shù)用一個空格隔開。其次，對于兩個不同的行，對應下標的數(shù)一一比較，字典序較小的排在前面（例如1 3 5 7排在1 3 6 8前面）。

數(shù)據(jù)范圍：n>0，0≤m≤n ，n+(n?m)≤25

輸入樣例：5 3輸出樣例：1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5

思路：

import java.util.Scanner;/** * @Author 秋名山碼神 * @Date 2023/1/30 * @Description */public class 組合枚舉每個數(shù) {    static int N = 30;    static int n,m;    static  int[] ways = new int[N];    public static void dfs(int u,int start){        //剪枝， 如果把后面的數(shù)都選上還不夠m，意味這無解，例如4開始，……        if(u+n - start 遞推
前面的遞歸我們是從原問題來推出子問題，遞推剛好相反，遞推：子問題推出原問題
遞推的斐波那契
題目描述：輸入一個整數(shù)N，輸出這個序列的前N項。(序列為斐波那契數(shù)列）
數(shù)據(jù)范圍：0
import java.util.Scanner;/** * @Author 秋名山碼神 * @Date 2023/1/31 * @Description */public class fib {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        int[] f = new int[46];        f[1] = 0;        f[2] = 1;        for(int i = 3; i<= n; i++){            f[i] = f[i-1] + f[i-2];        }        for(int i = 1; i<=n; i++)            System.out.print(f[i]+" ");        System.out.println();    }}
帶分數(shù)
來源：第四屆藍橋杯省賽C++B/C組,第四屆藍橋杯省賽JAVAA/B組
數(shù)據(jù)范圍：1 <= N < 10^6
目標是找到三個數(shù),使得n=a+b/c,可以考慮使用暴力解法將1~9的全排列給一個個搜出來,然后每次找到一種排列,就利用二重循環(huán)將該段排列分成三段,第一段得到a,第二段得到b,第三段得到c,然后進行判斷即可
優(yōu)化： n是已知的，可以把等式變形為，cn = c *a + b,枚舉ac，直接算出b
package 遞歸;import java.util.Scanner;/** * @Author 秋名山碼神 * @Date 2023/1/31 * @Description */public class 帶分數(shù)真題 {    static boolean[] st = new boolean[12];    static int[] ans = new int[12];    static int n = 100;    static int res = 0;    public static void dfs(int x)    {        if(x > 9)        {            for(int i = 1;i <= 7;i++)                for(int j = i + 1;j <= 8;j++)                {                    int a = 0;                    int b = 0;                    int c = 0;                    int cnt = 1;                    for(int k = 1;k <= i;k++)                    {                        a += ans[k] * cnt;                        cnt *= 10;                    }                    cnt = 1;                    for(int k = i + 1;k <= j;k++)                    {                        b += ans[k] * cnt;                        cnt *= 10;                    }                    cnt = 1;                    for(int k = j + 1;k <= 9;k++)                    {                        c += ans[k] * cnt;                        cnt *= 10;                    }                    if(b % c == 0)                    {                        if(a + b/c == n) {res ++;}                    }                }            return;        }        for(int i = 1;i <= 9;i++)        {            if(st[i]) continue;            ans[x] = i;            st[i] = true;            dfs(x + 1);            st[i] = false;        }    }    public static void main(String[] args) {        Scanner scan = new Scanner(System.in);        n = scan.nextInt();        dfs(1);        System.out.println(res);    }}
翻硬幣
來源：第四屆藍橋杯省賽C++B組
數(shù)據(jù)范圍：n<100
暴力遞歸可以寫
import java.util.Scanner;/** * @Author 秋名山碼神 * @Date 2023/1/31 * @Description */public class Main{    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        String ss1 = sc.next();        String ss2 = sc.next();        char[] s1 = ss1.toCharArray();        char[] s2 = ss2.toCharArray();        int cnt = 0;        for(int i = 0; i < s1.length-1; i++){            if(s1[i] != s2[i]){                cnt++;                if(s1[i] == "*")                    s1[i] = "o";                else                    s1[i] = "*";                if(s1[i+1] == "*")                    s1[i+1] = "o";                else                    s1[i+1] = "*";            }        }        System.out.println(cnt);    }}
最后
看在博主這么努力，熬夜肝的情況下，給個免費的三連吧！