Как вычислить количество шагов для вычисления чисел Фибоначчи?

Question

[432ffqfw]

Нужно вычислить количество шагов для вычисления чисел Фибоначчи. Нашел че-то про числа Леонардо, но не понял как это связанно...

Comments

[Wan-Derer]

М... Каждое число вычисляется за один шаг. Сколько чисел - столько и шагов. Не?

[432ffqfw]

Wan-Derer, Нет, может не корректно сформулировал вопрос, для числа 5(сложить 3-тее и 4-тое) нам нужно посчитать число 3 (1 действие) и число 4(1 действие) которое в свою очередь состоит из числа 3(1 действие), а 1 и 2 известны они по 1. Пока писал вроде понял че делать)

[mayton2019]

432ffqfw, попробуй как на олимпиадах описать.

Input: 
13

Output:
7
(1,1,2,3,5,8,13)

Answer 1

[Wataru]

Составьте рекурентное соотношение. Пусть S(k) - сколько шагов надо для вычисления k-ого числа.
Это будет 1 шаг (сумма в конце), плюс сколько надо шагов, чтобы подсчитать слагаемые. Т.е.:
S(k) = S(k-1) + S(k-2) + 1
И известно, что S(1) = S(2) = 0

Уже можно это все подсчитать, как если бы вы числа фиббоначи считали. Хоть рекурсивно, хоть циклом (что, конечно, быстрее).

Но можно добавить в обе стороны урванения +1 и сгрупировать слагаемые аккуратно:
S(k)+1 = S(k-1)+1 + S(k-2)+1

Тогда, если обозначить G(k) = S(k)+1, то получится:
G(k) = G(k-1) + G(k-2) и G(1) = G(2) = 1

Т.е. ответом будет предыдущее число фиббоначи минус один (нам же S(k) = G(k)-1 надо. Плюс, у вас числа с 1,2 начинаются, а тут с 1,1).
Принципиально от вычислений выше не отличается, но наблюдение интересное.