Обмен технологиями

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

Наиболее популярное понимание рекурсии — это последовательность. Отношения между рекурсией и последовательностью подобны отношениям между алгоритмом и структурой данных. Последовательность в некотором роде.
Подобно линейному списку в структуре данных (который может быть последовательным списком или связным списком, обычно последовательным списком), рекурсия
Цикл или итеративный процесс перечисления.
Рекурсия, по сути, является математической проблемой, поэтому некоторые студенты спросили, требует ли алгоритм хорошей математики. Вы обнаружите, что это не так.
Эту математику мы плохо изучали в средней и старшей школе. Мы уже сдали вступительные экзамены в колледж, так почему же нам следует бояться этих вещей!?

1. Последовательность Фибоначчи

Последовательность, образованная числами Фибоначчи (обычно обозначаемая F(n)) называется последовательностью Фибоначчи.Последовательность начинается с 0 и 1, за которыми следуют
Каждое число в является суммой двух предыдущих чисел. То есть:

Ф(0)=0，Ф(1)=1
F(n)=F(n-1)+ F(n- 2), где n>1, учитывая n(0 ≤n≤ 30), вычислите F(n)

Получив этот вопрос, давайте сначала посмотрим на диапазон вопроса, который не должен превышать 30. Это потому, что скорость роста чисел Фибоначчи очень быстрая.
Быстро, экспоненциально. Таким образом, если n велико, оно выйдет за пределы диапазона 32-битных целых чисел в языке C.Это самая элементарная поставка
Мы уже рассказали вам о вопросе вывода и формуле рекурсии. Все, что нам нужно сделать, это использовать цикл для реализации этой рекурсии.
Нам нужно всего лишь использовать массив 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 определяется следующим образом:
Т(0) = 0, Т(1) = 1,Т(2)=1
И при условии n>2, T(n)=T(n-1)+T(n-2)+T(n-3), давая вам целое число n, пожалуйста, верните n-й Табоначчи.
Значение числа T(n).
Если вы уже понимаете последовательность Фибоначчи, то эта задача не представляет сложности, но при инициализации необходимо инициализировать первые три числа.
А во время расчета итерации цикла для значения текущего числа требуется накопительная сумма значений трех предыдущих чисел. так:

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. Двумерная рекуррентная задача

Такие задачи, как последовательность Фибоначчи, можно решить с помощью одномерного массива. Иногда, когда одно измерение не может решить ее, я.
Нам нужно посмотреть на проблему с более высокого уровня.

Длина равна n(1
Но других символов быть не должно) и соседние M запрещены. Сколько существует типов таких строк?

Предположим, что длина равна n, и существует f[n][0] типов строк, оканчивающихся на 'A', f[n][1] типов строк, заканчивающихся на 'C', и есть f[n][ 1] виды строк, заканчивающихся на ''
f[n][2] вид

4. Настоящий бой

4.1 Около 509 чисел Фибоначчи

Числа Фибоначчи(обычно используетсяF(n)представляет) образовавшаяся последовательность называетсяПоследовательность Фибоначчи .Эта последовательность состоит из0и1Изначально каждое последующее число представляет собой сумму двух предыдущих чисел.

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, вернитесь к третьей точке «Треугольника Ян Хуэй».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