Condivisione della tecnologia

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

La comprensione più popolare della ricorsione è una sequenza. La relazione tra ricorsione e una sequenza è in qualche modo simile alla relazione tra un algoritmo e una struttura di dati
Come una lista lineare in una struttura dati (che può essere una lista sequenziale o una lista concatenata, solitamente una lista sequenziale), la ricorsione è
Un processo di enumerazione ciclico o iterativo.
La ricorsione è essenzialmente un problema matematico, quindi alcuni studenti hanno chiesto se l'algoritmo richiede una buona matematica. Lo scoprirai
Questa matematica è solo cose che abbiamo imparato male alle scuole medie e superiori. Abbiamo già sostenuto l'esame di ammissione all'università, quindi perché dovremmo avere paura di queste cose!?

1. Sequenza di Fibonacci

La sequenza dei numeri di Fibonacci (solitamente rappresentata da F(n)) è chiamata sequenza di Fibonacci.La sequenza inizia con 0 e 1, seguiti da
Ogni numero in è la somma dei due numeri precedenti. Questo è:

F(0)=0, F(1)=1
F(n)=F(n -1)+ F(n- 2), dove n>1, dato n(0 ≤n≤ 30), calcolare F(n)

Dopo aver ricevuto questa domanda, diamo prima un’occhiata all’intervallo della domanda, che non dovrebbe superare al massimo 30. Questo perché il tasso di crescita dei numeri di Fibonacci è molto rapido.
Veloce, esponenziale. Pertanto, se n è grande, supererà l'intervallo degli interi a 32 bit nel linguaggio C.Questa è la consegna più elementare
Ti abbiamo già detto la domanda sulla deduzione e la formula di ricorsione. Tutto quello che dobbiamo fare è utilizzare un ciclo per implementare questa ricorsione.
Dobbiamo solo utilizzare un array F[31], inizializzare F[0] e F[1] e quindi calcolarlo in un ciclo secondo la formula fornita.

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. Sequenza di Tibernacci

La sequenza Tabonacci Tn è definita come segue:
T(0) = 0, T(1) = 1, T(2) = 1
E sotto la condizione di n>2, T(n)=T(n-1)+T(n-2)+T(n-3), dandoti l'intero n, restituisci l'ennesimo Tabonacci
Il valore del numero T(n).
Se comprendi già la sequenza di Fibonacci, questo problema non è difficile, ma durante l'inizializzazione devi inizializzare i primi tre numeri.
E durante il calcolo dell'iterazione del ciclo, il valore del numero corrente richiede la somma cumulativa dei valori dei tre numeri precedenti. come questo:

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. Problema di ricorsione bidimensionale

Problemi come la sequenza di Fibonacci possono essere risolti con una matrice unidimensionale A volte, quando una dimensione non può risolverlo, I
Dobbiamo guardare il problema da una dimensione più alta.

La lunghezza è n(1
Ma non devono esserci altri caratteri) ed è vietato avere M adiacenti tra loro. Quanti tipi di stringhe di questo tipo esistono?

Considera che la lunghezza è n, e ci sono f[n][0] tipi di stringhe che terminano con 'A', f[n][1] tipi di stringhe che terminano con 'C', e ci sono f[n][ 1] tipi di stringhe che terminano con ''
f[n][2] specie

4. Combattimento reale

4.1 Vicino a 509 numeri di Fibonacci

Numeri di Fibonacci(di solito usatoF(n)rappresenta) la sequenza formata viene chiamataSequenza di Fibonacci .Questa sequenza è composta da0E1Inizialmente, ogni numero successivo è la somma dei due numeri precedenti.

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 Salire le scale

Supponiamo che tu stia salendo le scale.BisognonÈ possibile raggiungere la cima dell'edificio tramite alcuni gradini.
ogni volta che puoi arrampicarti1O2 un passo. In quanti modi diversi puoi salire in cima a un edificio?

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 Triangolo Yang Hui||

Dato un indice non negativorowIndex, ritorna al terzo punto del "Triangolo Yang Hui"rowIndexOK.

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