Partage de technologie

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

La compréhension la plus populaire de la récursion est une séquence. La relation entre la récursivité et une séquence est en quelque sorte la relation entre un algorithme et une structure de données.
Comme une liste linéaire dans une structure de données (qui peut être une liste séquentielle ou une liste chaînée, généralement une liste séquentielle), la récursivité est
Un processus d'énumération en boucle ou itératif.
La récursion est essentiellement un problème mathématique, c'est pourquoi certains étudiants ont demandé si l'algorithme nécessite de bonnes mathématiques. Ce n'est pas vrai.
Ces mathématiques ne sont que des choses que nous avons mal apprises au collège et au lycée. Nous avons déjà passé l'examen d'entrée à l'université, alors pourquoi devrions-nous avoir peur de ces choses !?

1. Séquence de Fibonacci

La séquence de nombres de Fibonacci (généralement représentée par F(n)) est appelée séquence de Fibonacci.La séquence commence par 0 et 1, suivis de
Chaque nombre est la somme des deux nombres précédents. C'est-à-dire:

F(0)=0,F(1)=1
F(n)=F(n -1)+ F(n- 2), où n>1, étant donné n(0 ≤n≤ 30), veuillez calculer F(n)

Après avoir répondu à cette question, examinons d’abord l’étendue de la question, qui ne doit pas dépasser 30 au maximum, car le taux de croissance des nombres de Fibonacci est très rapide.
Rapide, exponentielle. Ainsi, si n est grand, il dépassera la plage des entiers de 32 bits en langage C.C'est la livraison la plus basique
Nous vous avons déjà posé la question de déduction et la formule de récursion. Il ne nous reste plus qu'à utiliser une boucle pour implémenter cette récursion.
Il suffit d'utiliser un tableau F[31], d'initialiser F[0] et F[1], puis de le calculer en boucle selon la formule donnée.

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. Séquence Tabonacci

La séquence de Tabonacci Tn est définie comme suit :
T(0) = 0, T(1) = 1, T(2)=1
Et sous la condition de n>2, T(n)=T(n-1)+T(n-2)+T(n-3), vous donnant l'entier n, veuillez renvoyer le nième Tabonacci
La valeur du nombre T(n).
Si vous comprenez déjà la séquence de Fibonacci, alors ce problème n'est pas difficile, mais lors de l'initialisation, vous devez initialiser les trois premiers nombres.
Et lors du calcul de l'itération de boucle, la valeur du nombre actuel nécessite la somme cumulée des valeurs des trois nombres précédents. comme ça:

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. Problème de récurrence bidimensionnelle

Des problèmes comme la séquence de Fibonacci peuvent être résolus avec un tableau à une dimension. Parfois, lorsqu'une dimension ne peut pas le résoudre, je le fais.
Nous devons considérer le problème sous un angle supérieur.

La longueur est n(1
Mais il ne doit pas y avoir d'autres caractères) et il est interdit d'avoir des M adjacents. Combien de types de telles chaînes existe-t-il ?

Considérons que la longueur est n et qu'il existe f[n][0] types de chaînes se terminant par « A », f[n][1] types de chaînes se terminant par « C », et il existe f[n][ 1] types de chaînes se terminant par ''
f[n][2] espèce

4. Combats réels

4.1 Près de 509 nombres de Fibonacci

Numéros de Fibonacci(généralement utiliséF(n)représente) la séquence formée est appeléeSéquence de Fibonacci .Cette séquence consiste à0et1Initialement, chaque nombre suivant est la somme des deux nombres précédents.

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 Likou 70 Monter les escaliers

Supposons que vous montiez des escaliers.besoinnVous pouvez atteindre le sommet du bâtiment en empruntant des marches.
chaque fois que tu peux grimper1ou2 une étape. De combien de manières différentes peut-on grimper au sommet d’un immeuble ?

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 Likou 119 Triangle Yang Hui||

Étant donné un indice non négatifrowIndex, revenons au troisième point du "Triangle Yang Hui"rowIndexD'ACCORD.

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