技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

再帰の最も一般的な理解はシーケンスです。再帰とシーケンスの関係は、アルゴリズムとデータ構造の関係に似ています。
データ構造の線形リスト (順次リストまたは連結リスト、通常は順次リスト) と同様に、再帰は次のようになります。
ループまたは反復列挙プロセス。
再帰は本質的に数学の問題であるため、アルゴリズムに優れた数学が必要かどうかを尋ねる学生もいましたが、そうではないことがわかります。
これらの数学は、私たちが中学や高校で苦手に学んできたものであり、すでに大学受験を経験しているのに、なぜそんなことを恐れる必要があるのでしょうか。

1. フィボナッチ数列

フィボナッチ数列 (通常は F(n) で表されます) をフィボナッチ数列と呼びます。シーケンスは 0 と 1 で始まり、その後に続きます。
の各数値は、前の 2 つの数値の合計です。あれは：

F(0)=0、F(1)=1
F(n)=F(n -1)+ F(n- 2)、n>1、n(0 ≤n≤ 30) の場合、F(n) を計算してください。

この質問を受け取ったら、まず質問の範囲を見てみましょう。30 を超えてはなりません。これは、フィボナッチ数の増加速度が非常に速いためです。
急速に、指数関数的に。そのため、n が大きいと C 言語の 32 ビット整数の範囲を超えてしまいます。これが最も基本的な配信です
演繹問題と再帰式についてはすでに説明しました。必要なのは、ループを使用してこの再帰を実装することだけです。
F[31] 配列を使用し、F[0] と F[1] を初期化し、指定された式に従ってループで計算するだけです。

int febonacci(int n) {  
    int F[30] = {0,1};  
    for (int i = 2; i < 30; i++) {  
        F[i] = F[i - 1] + F[i - 2];  
    }  
    return F[29]  
}
1
2
3
4
5
6
7

2. タボナッチシーケンス

タボナッチ数列 Tn は次のように定義されます。
T(0) = 0、T(1) = 1、T(2)=1
n>2 の条件下では、T(n)=T(n-1)+T(n-2)+T(n-3) となり、整数 n が与えられるので、n 番目のタボナッチを返してください。
数値 T(n) の値。
フィボナッチ数列をすでに理解している場合、この問題は難しくありませんが、初期化するときに最初の 3 つの数値を初期化する必要があります。
そして、ループの反復計算中に、現在の数値の値は、前の 3 つの数値の値の累積和が必要になります。このような：

int tribonacci(int n) {  
    int F[30] = {0,1,1};  
    for (int i = 3; i < 30; i++) {  
        F[i] = F[i - 1] = F[i - 2] + F[i - 3];  
    }  
    return F[29];  
}
1
2
3
4
5
6
7

3. 2次元漸化式問題

フィボナッチ数列のような問題は 1 次元配列で解決できる場合がありますが、1 次元では解決できないことがあります。
私たちは問題をより高い次元から見る必要があります。

長さは n(1
ただし、他の文字があってはなりません)、M を隣接させることは禁止されています。このような文字列は何種類ありますか?

長さが n で、「A」で終わる文字列が f[n][0] 種類あり、「C」で終わる文字列が f[n][1] 種類あり、f[n][ があるとします。 1] ''で終わる文字列の種類
f[n][2] 種

4.実戦

4.1 509 に近いフィボナッチ数

フィボナッチ数(通常使用されるF(n)を表します）形成されたシーケンスはと呼ばれますフィボナッチ数列 。このシーケンスは次のもので構成されます0そして1最初は、後続の各数値は前の 2 つの数値の合計になります。

int fib(int n){
    if(n == 0){
       return 0;

    }
    else if (n == 1){
        return 1;

    }
    return fib(n - 1) + fib(n - 2);
}
1
2
3
4
5
6
7
8
9
10
11

4.2 リコウ70 階段を登る

あなたが階段を登っているとします。必要n階段を登ると建物の最上階に到達できます。
登れるたびに1または2一歩。建物の屋上まで登ることができる方法は何通りありますか?

int climbStairs(int n) {  
    int f[46];  
    f[0] = 1;  
    f[1] = 1;  
    for(int i = 2; i <= n; i++){  
        f[i] = f[i - 1] + f[i - 2];  
    }  
    return f[n];  
}
1
2
3
4
5
6
7
8
9

4.3 リコウ 119 ヤンフイ トライアングル||

負でないインデックスが与えられた場合rowIndex、「楊輝三角形」の3番目のポイントに戻ります。rowIndexわかりました。

int* getRow(int rowIndex, int* returnSize) {  
    int f[34][34];  
    for(int i = 0; i <= rowIndex; i++){  
        for(int j = 0; j <= i; j++){  
            if(j ==0 || j == i){  
                f[i][j] = 1;  
            }  
            else {  
                f[i][j] = f[i - 1][j] + f[i - 1][j - 1];   
            }  
        }  
    }  
    int* ret = (int *)malloc (sizeof(int) * (rowIndex + 1));  
    for(int j = 0; j <= rowIndex; j++){  
        ret[j] = f[rowIndex][j];  
    }  
    *returnSize = rowIndex + 1;  
    return ret;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19