Беседы о программировании 002 :: Замена целочисленного деления на умножение и сдвиг (теория)

В этой беседе даётся теоретическое представление о том, как можно заменить процедуру деления целых неотрицательных чисел с округлением вниз на умножение с последующим сдвигом. Доказывается теорема, с помощью которой можно точно установить необходимый сдвиг, когда известен знаменатель и диапазон значений числителя. Выводятся формулы, с помощью которых вычисляется нужный множитель и сдвиг, даются примеры.

Читать далее «Беседы о программировании 002 :: Замена целочисленного деления на умножение и сдвиг (теория)»

Беседы о программировании 001 :: Бинарный поиск

 

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

Читать далее «Беседы о программировании 001 :: Бинарный поиск»

Задача 1 — Бинарный поиск

[ Обновление: Данный пост более не актуален, см. тему Беседы о программировании 001 :: Бинарный поиск ]

Первая беседа будет посвящена бинарному поиску. Я расскажу о некоторых неочевидных для меня в прошлом соображениях по части данного алгоритма.

Читать далее «Задача 1 — Бинарный поиск»