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

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

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

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

Насколько я понимаю, мы передаем int n дважды рекурсивной программе.

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

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

Если n=10, уравнение будет таким:

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

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


equation-solving mips equations
person melMPLS    schedule 05.06.2012    source источник
comment
Мне это кажется оффтопом... Без понимания, что такое вызов функции одного аргумента со значением x, сложно решать задачи программирования. Вы просили написать почти калькулятор чисел Фибоначчи - поищите...   -  person Alexei Levenkov    schedule 05.06.2012

Ответы (3)


arrow_upward
3
arrow_downward

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

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

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.
    }
}
person duffymo    schedule 05.06.2012
comment
+1. Это также может быть задача по динамическому программированию вместо рекурсии - решать ОП. - person Alexei Levenkov; 05.06.2012
comment
Это не точный код. Я прочитал MIPS для задания; Я написал Джаву. И вы можете делать все, что считаете правильным; Буду следовать своему примеру, спасибо. - person duffymo; 05.06.2012

arrow_upward
0
arrow_downward

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

f(0) = 1
f(1) = 1

Все остальное использует рекурсивную формулу. Например, давайте вычислим f(4). Это не один из базовых случаев, поэтому мы должны использовать полное уравнение. Подставляя n=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)< /strong>
f(2) = 3 f(2-1) + 2 f(2-2) = 3 f(1) + 2 f(0)

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

f(2) = 3 f(1) + 2 f(0) = 31 + 21 = 5

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

f(3) = 3 f(2) + 2 f(1) = 35 + 21 = 17

И, наконец, еще раз раскручиваем и решаем f(4).

f(4) = 3 f(3) + 2 f(2) = 317 + 25 = 61

person John Kugelman    schedule 05.06.2012
comment
Большое спасибо за помощь. Теперь это имеет полный смысл! - person melMPLS; 05.06.2012

arrow_upward
0
arrow_downward

Нет, я думаю, вы правы, и это рекурсивно. Похоже, это разновидность последовательности Фибоначчи, классической рекурсивной задачи.

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

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

Базовый случай указывает точку, в которой вы больше не можете рекурсировать. Например, если вы сортируете рекурсивно, базовым случаем является список длиной 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. Это означает, что для наших целей 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

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

person acattle    schedule 05.06.2012