е (п), понимая уравнение

Question

Я была поставлена ​​задача написания кода инструкции MIPS по следующей формуле:

f(n) = 3 f(n-1) + 2 f(n-2) 
f(0) = 1 
f(1) = 1 

У меня возникли проблемы с пониманием того, что на самом деле означает, что формула.

Из того, что я понимаю, мы передаем int n для двухрекурсивной программы.

Таким образом, для F (0), то для бы уравнение будет:

f(n)=3*1(n-1) + 2*(n-2) 

Если п = 10 уравнение будет:

f(10)=3*1(10-1) + 2*(10-2) 

Я знаю, что я не получаю это право на все потому, что это не будет рекурсивным. Любой свет, который вы могли бы проливать на то, что на самом деле означает уравнение, будет отличным. Я должен быть в состоянии написать код MIPS, как только я пойму уравнение.

Answer 1

Я думаю, что это уравнение разницы.

Вы дали два начальных значений:

f(0) = 1 
f(1) = 1 
f(n) = 3*f(n-1) + 2*f(n-2) 

Итак, теперь вы можете продолжать идти, как это:

f(2) = 3*f(1) + 2*f(0) = 3 + 2 = 5 
f(3) = 3*f(2) + 2*f(1) = 15 + 2 = 17 

Таким образом, ваш рекурсивный метод будет выглядеть следующим образом (я буду писать Java- как обозначение):

public int f(n) { 
    if (n == 0) { 
     return 1; 
    } else if (n == 1) { 
     return 1; 
    } else { 
     return 3*f(n-1) + 2*f(n-2); // see? the recursion happens here. 
    } 
} 

Answer 2

Нет, я думаю, вы правы и рекурсивны. Вроде бы вариация Fibonacci Sequence, классическая рекурсивная проблема

Помните, что рекурсивный алгоритм имеет 2-х частей:

1. Базовый вариант
2. Рекурсивный вызов

База case указывает точку, в которой вы больше не можете переписывать. Например, если вы сортируете рекурсивно, базовый регистр представляет собой список длины 1 (поскольку один элемент сортируется тривиально).

Таким образом, (если n не отрицательно), у вас есть 2 базовых блока: n = 0 и n = 1. Если ваша функция получает значение n, равное 0 или 1, тогда нет смысла переписывать

Имея это в виду, что ваш код должен выглядеть примерно так:

function f(int n): 
    #check for base case 

    #if not the base case, perform recursion 

Итак, давайте использовать Фибоначчи в качестве примера.

В последовательности Фибоначчи каждое число является суммой двух чисел перед ним. Таким образом, с учетом последовательности 1, 2 следующее число, очевидно, 1 + 2 = 3, а число после этого равно 2 + 3 = 5, 3 + 5 = 8 и так далее.В общем случае n-е число Фибоначчи представляет собой (n - 1) -й номер Фибоначчи плюс (n - 2) -й номер Фибоначчи, или f(n) = f(n - 1) + f(n - 2)

Но где начинается последовательность? Это был базовый случай. Фибоначчи определил свою последовательность начиная с 1, 1. Это означает, что для наших pruposes, f(0) = f(1) = 1. Так что ...

function fibonacci(int n): 
    if n == 0 or n == 1: 
     #for any n less than 2 
     return 1 

    elif n >= 2: 
     #for any n 2 or greater 
     return fibonacci(n-1) + fibonacci(n-2) 

    else: 
     #this must n < 0 
     #throw some error 

Обратите внимание, что одна из причин, по Фибоначчи преподается вместе с рекурсией, потому что это показывает, что иногда рекурсия является плохой идеей. Я не буду вдаваться в это здесь, но для больших n этот рекурсивный подход очень неэффективен. В качестве альтернативы, чтобы иметь 2 глобальные переменные, n1 и n2 таким образом, что ...

n1 = 1 
n2 = 1 

print n1 
print n2 

loop: 
    n = n1 + n2 
    n2 = n1 
    n1 = n 

    print n 

будет печатать последовательность.

Answer 3

У Вас есть два базовых случая:

F (0) = 1
F (1) = 1

Все остальное использует рекурсивную формулу. Например, давайте вычислим f (4). Это не один из базовых случаев, поэтому мы должны использовать полное уравнение. Подключение п = 4 мы получаем:

F (4) = 3 F (4-1) + 2 F (4-2) = 3 F (3) + 2 F (2)

Хм, еще не сделан. Для вычисления f (4) нам нужно знать, что f (3) и f (2). Ни один из них не является базовым, поэтому мы должны сделать некоторые рекурсивные вычисления. Хорошо ...

F (3) = 3 F (3-1) + 2 F (3-2) = 3 F (2) + 2 F (1)
е (2) = 3 F (2-1) + 2 е (2-2) = 3 е (1) + 2 е (0)

Там мы идем! Мы достигли дна. f (2) определяется через f (1) и f (0), и мы знаем, каковы эти два значения. Нам это давали, поэтому нам не нужно делать никаких рекурсивных вычислений.

е (2) = 3 е (1) + 2 е (0) = 3 × 1 + 2 × 1 = 5

Теперь, когда мы знаем, что е (2), мы можем раскрутить нашу рекурсивную цепочку и решить f (3).

F (3) = 3 F (2) + 2 F (1) = 3 × 5 + 2 × 1 = 17

И, наконец, отдохнуть один больше времени и решить f (4).

F (4) = 3 F (3) + 2 F (2) = 3 × 17 + 2 × 5 = 61