Compartilhamento de tecnologia

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

O entendimento mais popular de recursão é uma sequência. A relação entre recursão e uma sequência é como a relação entre um algoritmo e uma estrutura de dados.
Como uma lista linear em uma estrutura de dados (que pode ser uma lista sequencial ou uma lista vinculada, geralmente uma lista sequencial), a recursão é
Um loop ou processo de enumeração iterativo.
A recursão é essencialmente um problema matemático, então alguns alunos perguntaram se o algoritmo requer boa matemática. Você descobrirá que isso não é verdade.
Essas matemáticas são apenas coisas que aprendemos mal no ensino fundamental e médio. Já passamos pelo vestibular, então por que deveríamos ter medo dessas coisas?

1. Sequência de Fibonacci

A sequência de números de Fibonacci (geralmente representada por F(n)) é chamada de sequência de Fibonacci.A sequência começa com 0 e 1, seguidos por
Cada número é a soma dos dois números anteriores. Aquilo é:

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

Depois de responder a esta questão, vamos primeiro olhar para o intervalo da questão, que não deve exceder no máximo 30. Isso porque a taxa de crescimento dos números de Fibonacci é muito rápida.
Rápido, exponencialmente. Portanto, se n for grande, excederá o intervalo de números inteiros de 32 bits na linguagem C.Esta é a entrega mais básica
Já falamos sobre a questão da dedução e a fórmula da recursão. Tudo o que precisamos fazer é usar um loop para implementar essa recursão.
Precisamos apenas usar um array F[31], inicializar F[0] e F[1] e então calculá-lo em um loop de acordo com a fórmula fornecida.

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. Sequência de Tibernacci

A sequência de Tabonacci Tn é definida como segue:
T(0) = 0, T(1) = 1, T(2)=1
E sob a condição de n>2, T(n)=T(n-1)+T(n-2)+T(n-3), fornecendo o número inteiro n, retorne o enésimo Tabonacci
O valor do número T(n).
Se você já entende a sequência de Fibonacci, então esse problema não é difícil, mas ao inicializar você precisa inicializar os três primeiros números.
E durante o cálculo da iteração do loop, o valor do número atual requer a soma cumulativa dos valores dos três números anteriores. assim:

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 recursão bidimensional

Problemas como a sequência de Fibonacci podem ser resolvidos com uma matriz unidimensional. Às vezes, quando uma dimensão não consegue resolver, eu.
Precisamos olhar para o problema de uma dimensão superior.

O comprimento é n(1
Mas não deve haver outros caracteres) e é proibido ter M adjacentes entre si. Quantos tipos dessas strings existem?

Considere que o comprimento é n, e existem f[n][0] tipos de strings que terminam com 'A', f[n][1] tipos de strings que terminam com 'C', e existem f[n][ 1] tipos de strings que terminam com ''
f[n][2] espécies

4. Combate real

4.1 Perto de 509 números de Fibonacci

Números de Fibonacci(geralmente usadoF(n)representa) a sequência formada é chamadaSequência de Fibonacci .Esta sequência consiste em0e1Inicialmente, cada número subsequente é a soma dos dois 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 escadas

Suponha que você esteja subindo escadas.precisarnVocê pode chegar ao topo do edifício seguindo algumas etapas.
toda vez que você pode subir1ou2 um passo. De quantas maneiras diferentes você pode subir até o topo de um prédio?

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 Triângulo Likou 119 Yang Hui||

Dado um índice não negativorowIndex, retorne ao terceiro ponto do “Triângulo 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