Compartir tecnología

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

La comprensión más popular de la recursividad es una secuencia. La relación entre la recursividad y una secuencia es como la relación entre un algoritmo y una estructura de datos.
Al igual que una lista lineal en una estructura de datos (que puede ser una lista secuencial o una lista enlazada, generalmente una lista secuencial), la recursividad es
Un proceso de enumeración iterativo o en bucle.
La recursividad es esencialmente un problema matemático, por lo que algunos estudiantes preguntaron si el algoritmo requiere buenas matemáticas. No es cierto.
Estas matemáticas son simplemente cosas que aprendimos mal en la escuela secundaria y en la escuela secundaria. Ya hemos pasado por el examen de ingreso a la universidad, entonces, ¿por qué deberíamos tener miedo de estas cosas?

1. Secuencia de Fibonacci

La secuencia formada por números de Fibonacci (generalmente representada por F(n)) se llama secuencia de Fibonacci.La secuencia comienza con 0 y 1, seguido de
Cada número es la suma de los dos números anteriores. Eso es:

F(0)=0,F(1)=1
F(n)=F(n -1)+ F(n- 2), donde n>1, dado n(0 ≤n≤ 30), calcule F(n)

Después de responder esta pregunta, veamos primero el rango de la pregunta, que no debe exceder 30. Esto se debe a que la tasa de crecimiento de los números de Fibonacci es muy rápida.
Rápido, exponencialmente. Entonces, si n es grande, excederá el rango de enteros de 32 bits en lenguaje C.Esta es la entrega más básica.
Ya te hemos contado la pregunta de deducción y la fórmula de recursividad. Todo lo que tenemos que hacer es usar un bucle para implementar esta recursividad.
Solo necesitamos usar una matriz F [31], inicializar F [0] y F [1] y luego calcularlo en un bucle de acuerdo con la fórmula dada.

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. Secuencia Tabonacci

La secuencia de Tabonacci Tn se define de la siguiente manera:
T(0) = 0, T(1) = 1, T(2) = 1
Y bajo la condición de n>2, T(n)=T(n-1)+T(n-2)+T(n-3), dándole el número entero n, devuelva el enésimo Tabonacci
El valor del número T(n).
Si ya comprende la secuencia de Fibonacci, entonces este problema no es difícil, pero al inicializar, debe inicializar los primeros tres números.
Y durante el cálculo de la iteración del bucle, el valor del número actual requiere la suma acumulativa de los valores de los tres números anteriores. como esto:

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 de recurrencia bidimensional

Problemas como la secuencia de Fibonacci se pueden resolver con una matriz unidimensional. A veces, cuando una dimensión no puede resolverla,
Necesitamos mirar el problema desde una dimensión superior.

La longitud es n(1
Pero no debe haber otros caracteres) y está prohibido tener M adyacentes entre sí. ¿Cuántos tipos de cadenas de este tipo existen?

Considere que la longitud es n, y hay f[n][0] tipos de cadenas que terminan en 'A', f[n][1] tipos de cadenas que terminan en 'C', y que hay f[n][ 1] tipos de cadenas que terminan en ''
f[n][2] especies

4. Combate real

4.1 Cerca de 509 números de Fibonacci

Números de Fibonacci(usualmente usadoF(n)representa) la secuencia formada se llamaSecuencia Fibonacci .Esta secuencia consiste en0y1Inicialmente, cada número subsiguiente es la suma de los dos números anteriores.

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 Subir escaleras

Supongamos que estás subiendo escaleras.necesidadnPuedes llegar a la cima del edificio siguiendo unos escalones.
cada vez que puedas escalar1o2 un paso. ¿De cuántas maneras diferentes puedes subir a la cima de 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 Triángulo Yang Hui||

Dado un índice no negativorowIndex, Regrese al tercer punto del "Triángulo Yang Hui"rowIndexDE ACUERDO.

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