Все задачи
Легко Решено: 0 Процент решений: 0%

Первое число Фибоначчи из n цифр

Найдите номер первого числа Фибоначчи, в котором n цифр.

Чему вы научитесь

  • Складывать два массива цифр
  • Получать числа Фибоначчи без переполнения
  • Останавливаться на первом члене, который удовлетворяет условию

Условие

Последовательность Фибоначчи начинается с F(1) = 1, F(2) = 1, и каждый следующий член равен сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21, ... Найдите, где в последовательности впервые встречается число из n десятичных цифр. Члены быстро перестают помещаться в 64-битные целые, поэтому, если в вашем языке нет длинной арифметики, складывайте их как массивы цифр.

Реализуйте fibonacci_with_n_digits(n).

Входные данные

n: количество цифр.

Выходные данные

Верните номер i первого члена F(i), в котором не меньше n цифр. Для n = 1 ответ равен 1.

Ограничения

1 ≤ n ≤ 1000

Примеры

Пример 1
Ввод:
n = 2

Ожидаемый вывод:
expected = 7
Ввод:
long long n = 2;

Ожидаемый вывод:
long long expected = 7;
Ввод:
long n = 2;

Ожидаемый вывод:
long expected = 7;

Пояснение

В F(6) = 8 одна цифра, а в F(7) = 13 две, поэтому ответ 7.

Пример 2
Ввод:
n = 4

Ожидаемый вывод:
expected = 17
Ввод:
long long n = 4;

Ожидаемый вывод:
long long expected = 17;
Ввод:
long n = 4;

Ожидаемый вывод:
long expected = 17;

Пояснение

F(16) = 987, а F(17) = 1597, поэтому ответ 17.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Храните только два последних члена.

Подсказка 2

Храните каждый член как цифры и складывайте их с переносами.

Подсказка 3

Считайте номер по ходу, начиная с F(1) = 1.

Ожидаемая сложность

время O(n²), доп. память O(n)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

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