Числа НЕ фибоначи

@BoolReturn1 · Регистрация: 24.03.2020

Студворк — интернет-сервис помощи студентам

Здравствуйте форумчане, потратил несколько дней на решение задачи из ПРОШЕДШЕГО чемпиона BSUIR, прошу помочь мне с решением.
Условие задачи (https://ibb.co/n1MkM9C):

Мое решение работало при t =10, n <= 10¹⁵, Заранее спасибо

Добавлено через 6 минут
В первом десятке таких чисел 5 - 0, 4, 6, 7, 9 (да, 0 считается)
В десятках такие числа - (40 46 47 49 60 64 67 69 70 74 76 79 90 94 96 97) всего 16 чисел,
Хочу подметить что от 1 до 10 таких чисел 4, от 10 до 100 - 16, от 100 до 1000 - 64 и так далее...
Соответственно можем округлить n к ближ разряду и быстро найти сколько чисел будет у него, после от него вручную идти циклом, однако при n = 10¹⁸ к примеру 1e17 + 5e16 то тогда нам придеться идти вручную 5 * 10¹⁶ однако это не пройдет по времени..

zer0mail · 30.05.2020, 07:54

а где описание алгоритма и программа?

@zss · 30.05.2020, 09:57

Комментарий модератора

BoolReturn1, запрещено давать ссылки на задания, расположенные на других сайтах.
Также запрещено размещать задания в виде изображений.
Перепечатайте его, пожалуйста, в своем следующем сообщении.

@eaa · 30.05.2020, 14:28

разве в десятках не так:
40 44 46 47 49 60 64 66 67 69 70 74 76 77 79 90 94 96 97 99
?

@BoolReturn1 · 30.05.2020, 14:35 **[ТС]**

Да, так, писал перед сном и совсем забыл добавить.

Добавлено через 2 минуты
Тогда в 1 десятке таких чисел 5, в 1 и 2 будет 25, в 1 2 и 3 будет 125 и так далее.. Соответственно ответ на n = 2019 будет 125.

Добавлено через 2 минуты
Насчет моего алгоритма, я его писал в марте на самом соревновании и сейчас у меня его нету, однако он работал только при n <= 10¹⁵, думаю нет смысла заново писать нерабочий алгоритм

@eaa · 30.05.2020, 15:04

нужно найти наибольшее число состоящее из цифр (0, 4, 6, 7, 9) меньше или равное n.
ну и найти порядковый номер в 5ой системе счисления.
сложность зависит от количества цифр в n, а оно не больше 18.

@BoolReturn1 · 30.05.2020, 16:12 **[ТС]**

Порядковый номер чего??

Добавлено через 6 минут
К примеру n = 100 значит такое число это 99 в 5ой системе счисления это 344, а дальше что? Нужно найти порядковый номер 344? Это будет 99 )) Откуда пришли туда и вернулись

Добавлено через 8 минут
Понял, спасибо!

Добавлено через 17 секунд
Понял, спасибо!

zer0mail · 30.05.2020, 16:57

Сообщение от eaa

нужно найти наибольшее число состоящее из цифр (0, 4, 6, 7, 9) меньше или равное n.

А почему числа нефибоначчи именно такие?

Добавлено через 11 минут
В частности, почему не существует чисел Фибоначчи только из цифр 0,4,6,7,9 ?

@BoolReturn1 · 30.05.2020, 17:02 **[ТС]**

потому что из остальных чисел можно путем удаления получить 1 2 3 5 8 следовательно любое число с этими цифрами будет числом НЕ фибоначи

@eaa · 30.05.2020, 17:07

Сообщение от BoolReturn1

в 5ой системе счисления это 344

5ая сс у вас состоит из цифр (0, 4, 6, 7, 9).
меняем их на цифры (0,1,2,3,4) и переводим в 10ую сс.

@TheCalligrapher · 30.05.2020, 18:24

Сообщение от BoolReturn1

потому что из остальных чисел можно путем удаления получить 1 2 3 5 8 следовательно любое число с этими цифрами будет числом НЕ фибоначи

Вопрос, заданный zer0mail звучит так: почему не существует чисел Фибоначчи только из цифр 0,4,6,7,9? Ваш ответ никак не отвечает на этот вопрос. Подозреваю, что ответ тут можно дать только чисто эмпирический.

Если вдруг найдется такое число Фибоначчи в диапазоне задачи, то это сразу сделает приведенное здесь решение неверным.

zer0mail · 31.05.2020, 11:12

Сообщение от TheCalligrapher

Если вдруг найдется такое число Фибоначчи в диапазоне задачи, то это сразу сделает приведенное здесь решение неверным.

Наверное, надо делать проверку на наличие такого числа. int64 позволяет это сделать...

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@BoolReturn1 3 / 4 / 3 Регистрация: 24.03.2020 Сообщений: 88

	Числа НЕ фибоначи 29.05.2020, 23:52. Показов 2216. Ответов 11 Метки нет (Все метки) Здравствуйте форумчане, потратил несколько дней на решение задачи из ПРОШЕДШЕГО чемпиона BSUIR, прошу помочь мне с решением. Условие задачи (https://ibb.co/n1MkM9C): Мое решение работало при t =10, n <= 10¹⁵, Заранее спасибо Добавлено через 6 минут В первом десятке таких чисел 5 - 0, 4, 6, 7, 9 (да, 0 считается) В десятках такие числа - (40 46 47 49 60 64 67 69 70 74 76 79 90 94 96 97) всего 16 чисел, Хочу подметить что от 1 до 10 таких чисел 4, от 10 до 100 - 16, от 100 до 1000 - 64 и так далее... Соответственно можем округлить n к ближ разряду и быстро найти сколько чисел будет у него, после от него вручную идти циклом, однако при n = 10¹⁸ к примеру 1e17 + 5e16 то тогда нам придеться идти вручную 5 * 10¹⁶ однако это не пройдет по времени.. 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	30.05.2020, 07:54
	а где описание алгоритма и программа? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	30.05.2020, 14:28
	разве в десятках не так: 40 44 46 47 49 60 64 66 67 69 70 74 76 77 79 90 94 96 97 99 ? 1

@BoolReturn1 3 / 4 / 3 Регистрация: 24.03.2020 Сообщений: 88
	30.05.2020, 14:35 [ТС]
	Да, так, писал перед сном и совсем забыл добавить. Добавлено через 2 минуты Тогда в 1 десятке таких чисел 5, в 1 и 2 будет 25, в 1 2 и 3 будет 125 и так далее.. Соответственно ответ на n = 2019 будет 125. Добавлено через 2 минуты Насчет моего алгоритма, я его писал в марте на самом соревновании и сейчас у меня его нету, однако он работал только при n <= 10¹⁵, думаю нет смысла заново писать нерабочий алгоритм 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	30.05.2020, 15:04
	Сообщение было отмечено zer0mail как решение Решение нужно найти наибольшее число состоящее из цифр (0, 4, 6, 7, 9) меньше или равное n. ну и найти порядковый номер в 5ой системе счисления. сложность зависит от количества цифр в n, а оно не больше 18. 1

@BoolReturn1 3 / 4 / 3 Регистрация: 24.03.2020 Сообщений: 88
	30.05.2020, 16:12 [ТС]
	Порядковый номер чего?? Добавлено через 6 минут К примеру n = 100 значит такое число это 99 в 5ой системе счисления это 344, а дальше что? Нужно найти порядковый номер 344? Это будет 99 )) Откуда пришли туда и вернулись Добавлено через 8 минут Понял, спасибо! Добавлено через 17 секунд Понял, спасибо! 0

@BoolReturn1 3 / 4 / 3 Регистрация: 24.03.2020 Сообщений: 88
	30.05.2020, 17:02 [ТС]
	потому что из остальных чисел можно путем удаления получить 1 2 3 5 8 следовательно любое число с этими цифрами будет числом НЕ фибоначи 0

Числа НЕ фибоначи

Решение