Grade 9 · Number sequences read one at a timeCitește în română

Largest Fibonacci term not greater than n

Original: Cel mai mare termen Fibonacci cel mult egal cu n

ExponentialC++1734 lines2 examples

The idea

We generate the terms of the Fibonacci sequence (1, 1, 2, 3, 5, ...) while the next term does not exceed n. The last term kept is the answer. We assume n >= 1.

Original description (Romanian)

Generăm termenii șirului lui Fibonacci (1, 1, 2, 3, 5, ...) cât timp următorul termen nu depășește n. Ultimul termen păstrat este răspunsul. Se presupune n >= 1.

Complexity
O(log n), because the terms grow exponentially
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

100

Expected output

89
Example 2

Input

21

Expected output

21

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

cel-mai-mare-termen-fibonacci.cpp
/*
 * Titlu: Cel mai mare termen Fibonacci cel mult egal cu n
 * Clasa: 9
 * Capitol: Șiruri de numere citite pe rând
 * Descriere: Generăm termenii șirului lui Fibonacci (1, 1, 2, 3, 5, ...) cât
 *            timp următorul termen nu depășește n. Ultimul termen păstrat este
 *            răspunsul. Se presupune n >= 1.
 * Complexitate: O(log n), pentru că termenii cresc exponențial
 *
 * Exemplu
 * Intrare: 100
 * Ieșire: 89
 *
 * Exemplu
 * Intrare: 21
 * Ieșire: 21
 */
#include <iostream>
using namespace std;

int main()
{
    long long n, a = 1, b = 1;
    cin >> n;
    while (a + b <= n)
    {
        long long c = a + b;
        a = b;
        b = c;
    }
    cout << b << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.