?

Log in

No account? Create an account

Предыдущий | Следующий

Про числа Фибоначчи я услышал еще на первом курсе института.
И даже трижды, в течении следующего года, реализовывал алгоритм их расчета:
- для ЕС-1035 на Фортране;
- для ДВК-4М на том же Фортране, но другом;
- для IBM PC на Turbo Pascal.
Однако физической сути понять не мог.

А тут наткнулся на ОПЗ:
"Имеется пара новорожденных кроликов (самец и самка), которые, спустя два месяца начинают спариваться.
Каждый месяц они производят новую пару кроликов, отвечающую первичным условиям.
Сколько пар кроликов будет через год, при условии, что все кролики останутся живы?
"

Жаль, что нам не предлагали к решению другие его задачи по теории чисел.
В те времена я бы решал их в лоб, грубым перебором. :-)

Я вот тут, кстати, посмотрел как нынешние студенты решают задачу по определению всех чисел в диапазоне от N1 до N2, которые делятся на M без остатка.
Оказывается всё просто: в цикле по i от N1 до N2 делят на M и проверяют остаток.
Вроде бы в современных языках уже и операторов тех нет, но работает.

А я своего преподавателя четверть века назад удивил.
Потому что находил минимальный и максимальный множитель, а потом тупо умножал в цикле по ним на M.
Внезапно выяснилось, что мой алгоритм для больших диапазонов работает в пять раз быстрее.
Но зачет я не получил, потому что, формально, я не проверял числа из диапазона, а формировал набор решений, а это совсем другая задача.

Comments

( 9 комментариев — Оставить комментарий )
v_pychick
23 июн, 2017 11:49 (UTC)
да ты ботан!
ivalnick
26 июн, 2017 07:59 (UTC)
Угу. Есть немного. :-)
livejournal
23 июн, 2017 12:29 (UTC)
Здравствуйте! Ваша запись попала в топ-25 популярных записей LiveJournal северного региона. Подробнее о рейтинге читайте в Справке.
mindfactor
23 июн, 2017 13:10 (UTC)
>Потому что находил минимальный и максимальный множитель, а потом тупо умножал в цикле по ним на M.

А зачем цикл вообще ? Округляем максимальный вниз и вычитаем из него минимальный, округлённый вверх. Фсё !
ivalnick
26 июн, 2017 08:00 (UTC)
Так надо было найти полный набор, а не диапазон.
dmitrmax
23 июн, 2017 14:53 (UTC)
умножать - это дорого. достаточно найти минальный и добавлять M каждый цикл.
ivalnick
26 июн, 2017 08:01 (UTC)
На ДВК при четных M умножать быстрее, чем складывать.
sergey_cheban
23 июн, 2017 14:53 (UTC)
> Потому что находил минимальный и максимальный множитель, а потом тупо
> умножал в цикле по ним на M.
> Внезапно выяснилось, что мой алгоритм для больших диапазонов работает
> в пять раз быстрее.
1. Прибавлять в цикле M - должно получиться быстрее, чем умножать.
2. По идее, алгоритм должен работать в M раз быстрее. Ну и ещё во сколько-то за счёт того, что сложение быстрее деления.
ivalnick
26 июн, 2017 08:02 (UTC)
Это я сейчас понимаю. :-)
Но, кстати, при четных M на ДВК выгоднее умножать, чем складывать.
( 9 комментариев — Оставить комментарий )

Profile

Аватарка
ivalnick
ivalnick

Latest Month

Июнь 2018
Вс Пн Вт Ср Чт Пт Сб
     12
3456789
10111213141516
17181920212223
24252627282930

Метки

Разработано LiveJournal.com
Designed by Tiffany Chow