Количество звонков для n-го числа Фибоначчи

Question

Рассмотрим следующий фрагмент кода:

int fib(int N)
{
   if(N<2) return 1;
   return (fib(N-1) + fib(N-2));
}

Учитывая, что fib вызывается из основного с N как 10,35,67, ... (скажем), сколько всего вызовов сделаны до fib?

Есть ли отношение к этой проблеме?

PS: Это теоретический вопрос, который не должен выполняться.

РЕДАКТИРОВАТЬ:

Мне известны другие методы для более быстрого вычисления рядов Фибоначчи.

Я хочу, чтобы решение для вычисления числа раз, которое fib вызывается для fib (40), fib (50), .. без помощи компилятора и в условии экзамена, где вы должны ответить на 40 вопросов, подобных этому оговоренное время (около 30 минут).

Спасибо,

Answer 1

Пусть f (n) будет количеством вызовов, сделанных для расчета fib(n).

• Если n <2 </em>, то f (n) = 1 .
• В противном случае, f (n) = 1 + f (n - 1) + f (n - 2) .

Итак, f составляет не менее O (fib (n)) . Фактически, f (n) равно 2 * fib (n) - 1 . Покажем это по индукции:

• Базовые случаи ( n <2 </em>, то есть n = 0 или n = 1 ): f (n) = 1 = 2 * 1 - 1 = 2 * fib (n) - 1 .

Шаг индукции ( n> = 2 ):

• f (n + 1) = f (n) + f (n - 1) + 1
• f (n + 1) = 2 * fib (n) - 1 + 2 * fib (n - 1) - 1 + 1
• f (n + 1) = 2 * fib (n + 1) - 1

Существует эффективных способов для вычисления любого термина Фибоначчи. Таким образом, то же самое верно для f (n) .

Answer 2

Есть ли отношение к этой проблеме

Существует уравнение в близкой форме для n-го числа Фибоначчи: http://en.wikipedia.org/wiki/Fibonacci_number#Closed_form_expression

В размещенном вами псевдокоде количество вызовов удовлетворяет рекуррентному отношению

x(n) = x(n-1) + x(n-2) +1   # for n>=2
x(1) = 1
x(0) = 1

Это почти то же самое, что рекуррентное соотношение Фибоначчи. Доказательство по индукции может показать, что число вызовов fib, сделанных fib (n), равно 2 * fib (n) -1, для n> = 0.

Конечно, можно ускорить вычисление, используя выражение закрытой формы или добавив код для запоминания ранее вычисленных значений.

Answer 3

Как уже упоминалось выше, вам нужно решить следующее повторяющееся уравнение: К (п) = К (п-1) + К (п-2) + 1

Давайте напишем это для n-1: K (n-1) = K (n-2) + K (n-3) + 1

Теперь вычтите второе из первого: K (n) -K (n-1) = K (n-1) - K (n-3),

или

K (n) - 2 * K (n-1) + K (n-3) = 0.

Соответствующее характеристическое уравнение будет иметь вид: х ^ 3 - 2 * х ^ 2 + 1 = 0.

Имеет следующие корни: 1, (1 + sqrt (5)) / 2, (1-sqrt (5)) / 2

Таким образом, для любой реальной А, В, С следующая функция K (n) = A * (1) ^ n + B * ((1 + sqrt (5)) / 2) ^ n + C * ((1-sqrt (5)) / 2) ^ n

будет решением для вашего уравнения.

Чтобы найти A, B, C, вам нужно определить несколько начальных значений K (0), K (1), K (2) и решить систему уравнений.

Answer 4

фи является константой

position = ceil(log((n - 0.5)*sqrt(5))/log(phi));

n - число Фибоначчи ... позиция даст вам, какое число Фибоначчи n

например, учитывая 13, позиция будет 7 - 0 1 1 2 3 5 8 13

используя эту позицию, просто вычислите число Фибоначчи в позиции-1 или любую другую позицию, которую вы хотите относительно заданного числа Фибоначчи.

Previous Fibo Num = floor((pow(phi,position-1)/sqrt(5))+0.5);

floor((pow(phi, position)/sqrt(5))+0.5) - это стандартная формула для вычисления N-го числа фибоначчи (Примечание - это не приближение)

Я просто перевернул эту формулу, чтобы вычислить положение, и использую положение - 1, чтобы вычислить предыдущее число Фибоначчи.

Ссылка - http://itpian.com/Coding/20951-Given-the-Nth-fib-no-and-find-the--N-1-th-fib-number-without-calculating-from-the-beginning---------.aspx

Answer 5

Интересный вопрос, я не могу дать вам формулу, но я написал для этого программу на Ruby, она работает с числами, которые я выяснил на бумаге, и она должна работать для любого.

#!/usr/bin/ruby
#find out how many times fib() would need to be called

def howmany(n)
    a = [ ]
    a.push n-1
    a.push n-2
    while a.select{|n| n > 2}.length > 0
        a.map! do |n|
            n > 2 ? [n-1,n-2] : n
        end
        a.flatten!
    end
    a.length
end

.

>> howmany(10)
=> 55

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

Edit:

>> howmany(35)
=> 9227465

Answer 6

Это классическая задача для решения с Рекуррентные отношения .

В частности, проблема Фибоначчи имеет следующие параметры:

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

Как только вы овладеете решением повторений, у вас не возникнет проблем с достижением решения (что, кстати, точно так же, как fib(n)).