1. Идея

Нужно вычислить n-е число Фибоначчи, где:

• F(1) = 1
• F(2) = 1
• F(k) = F(k - 1) + F(k - 2) при k > 2

Самый прямой способ — последовательно строить числа Фибоначчи от первых двух к нужному номеру.

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

• a — предыдущее число
• b — текущее число

Тогда следующее число равно a + b.

2. Наблюдения

1. Для n = 1 и n = 2 ответ сразу равен 1.

2. Для любого n >= 3 можно идти циклом от 3 до n, каждый раз пересчитывая следующее число Фибоначчи.

3. Нам не нужен массив, потому что в формуле участвуют только два последних значения.

4. По условию n <= 90, и ответ гарантированно помещается в long long, поэтому в C++ достаточно типа long long.

3. Алгоритм

1. Считать n.
2. Если n == 1 или n == 2, вывести 1.
3. Иначе:
   • присвоить a = 1, b = 1
   • для всех i от 3 до n:
     • вычислить c = a + b
     • сдвинуть значения: a = b, b = c
4. После цикла в b будет находиться F(n).
5. Вывести b.

4. Почему это работает

Покажем, что после каждого шага цикла переменные действительно хранят нужные числа Фибоначчи.

Перед началом цикла:

• a = 1 = F(1)
• b = 1 = F(2)

Пусть перед некоторой итерацией выполняется:

• a = F(i - 2)
• b = F(i - 1)

Тогда мы вычисляем:

• c = a + b = F(i - 2) + F(i - 1) = F(i)

После этого делаем:

• a = b, значит теперь a = F(i - 1)
• b = c, значит теперь b = F(i)

То есть после итерации инвариант сохраняется для следующего шага.

Когда цикл закончится на i = n, переменная b будет равна F(n), что и требуется вывести.

5. Сложность

• Время: O(n), потому что выполняется один цикл длиной до n
• Память: O(1), потому что используется только несколько переменных

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n == 1 || n == 2) {
        cout << 1 << '\n';
        return 0;
    }

    long long a = 1;
    long long b = 1;

    for (int i = 3; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }

    cout << b << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())

if n == 1 or n == 2:
    print(1)
else:
    a = 1
    b = 1
    for _ in range(3, n + 1):
        c = a + b
        a = b
        b = c
    print(b)