Здравствуйте, rg45, Вы писали:
А>>>Простой вопрос: Дано число А, которое не делится нацело на 4. Необходимо определить ближайшее числу А число В (В > А), которое будет делиться нацело на 4.
R>Херней, говоришь? А проверь-ка свое решение для a = 4, получается 8.
KISS
Люди, я люблю вас! Будьте бдительны!!!
Re[4]: Определение ближайшего числа, делимого нацело на 4
Здравствуйте, Denis Mingulov, Вы писали:
DM>Здравствуйте, rg45, Вы писали:
А>>>>Простой вопрос: Дано число А, которое не делится нацело на 4. Необходимо определить ближайшее числу А число В (В > А), которое будет делиться нацело на 4. BZ>>>a/4*4+4 BZ>>>вместо того чтобы маяться хернёй с bit fiddling and unit tests around it R>>Херней, говоришь? А проверь-ка свое решение для a = 4, получается 8. DM>И?
R>>А теперь давай исправим ошибку, да не забудем про отрицательную область определения: DM>Какую ошибку-то? Условие не читали, что ли?
Да, действительно, условие прочел невнимательно. Давайте будем следовать условию строго. Все равно в формуле, которую предложил BulatZiganshin содержится ошибка. Например для a = -5 результатом должно быть -4. А по этой формуле получается 0.
Итак, исправляем ошибку:
a < 0 ? (a + 1) / 4 * 4 : a / 4 * 4 + 4
А вот решение с битовыми операциями:
(a + 4) & ~3
--
Re[5]: Определение ближайшего числа, делимого нацело на 4
Здравствуйте, rg45, Вы писали:
R>А вот решение с битовыми операциями:
а на какое решение ты потратил меньше времени? какое проще понять читателю?
серьёзно, у меня такое подозрение, что такие решения здесь предлагаются людьми, которые ничего серьёзного в жизни не оптимизировали, и потому думают что оптимизации надо пихать куда попало
я пишу архиватор, большая часть кода в нём на хаскеле, который вообще на порядок медленней С. тем не менее, мой архиватор занимает первые места в бенчмарках, поскольку он соптимизирован с умом — где надо haskell, где надо — C и низкоуровневая оптимизация
Люди, я люблю вас! Будьте бдительны!!!
Re[4]: Определение ближайшего числа, делимого нацело на 4
Здравствуйте, BSDыщъх, Вы писали:
BSD>Подобный код, конечно, широко используется, но условию задачи не удовлетворяет.
почему не удовлетворяет?
повторю условие :
Простой вопрос: Дано число А, которое не делится нацело на 4. Необходимо определить ближайшее числу А число В (В > А), которое будет делиться нацело на 4.
Здравствуйте, Аноним, Вы писали:
А>Простой вопрос: Дано число А, которое не делится нацело на 4. Необходимо определить ближайшее числу А число В (В > А), которое будет делиться нацело на 4. А>Но мне кажется есть более простое решение ...
Самое простое и изящное, что приходит в голову — использовать паттерн "визитор" совместно с паттерном "стратегия". С помощью фабрики стратегий создается стратегия, которая умеет определять ближайшее делящееся на 4 число, визитор посещает число и применяет к нему выбранную стратегию. Конкретные реализации математической части лучше поискать в интернете — наверняка же эта задача уже кем-то решалась, так зачем изобретать велосипед?
Re[6]: Определение ближайшего числа, делимого нацело на 4
Здравствуйте, BulatZiganshin, Вы писали:
BZ>серьёзно, у меня такое подозрение, что такие решения здесь предлагаются людьми, которые ничего серьёзного в жизни не оптимизировали, и потому думают что оптимизации надо пихать куда попало
С битами лично мне проще и понятнее. Да и надежнее как-то.
Re[6]: Определение ближайшего числа, делимого нацело на 4
Здравствуйте, BulatZiganshin, Вы писали:
R>>А вот решение с битовыми операциями: BZ>а на какое решение ты потратил меньше времени? какое проще понять читателю?
Возможно, ты сочтешь, что я лукавлю, но вариант с битовыми операциями у меня родился просто слету, а вариант с умножением и делением напряг несколько больше. Но это все субъективно, и зависит от личного опыта. Я вполне допускаю, что для кого-то более очевидным и простым будет вариант с умножением и делением.
BZ>серьёзно, у меня такое подозрение, что такие решения здесь предлагаются людьми, которые ничего серьёзного в жизни не оптимизировали, и потому думают что оптимизации надо пихать куда попало
BZ>я пишу архиватор, большая часть кода в нём на хаскеле, который вообще на порядок медленней С. тем не менее, мой архиватор занимает первые места в бенчмарках, поскольку он соптимизирован с умом — где надо haskell, где надо — C и низкоуровневая оптимизация
В общем я с тобой согласен, преждевременная оптимизация — корень всех зол спору нет. Приоритет в этом случае, конечно же, у понятности. И эффективности в первую очередь следует добиваться на уровне алгоритмов и проектирования вцелом. Но бывают же и исключения. Лично мне известны случаи (давно правда это было), когда по пальцам приходилось считать количество умножений и делений и от существенно этого зависела общая производительность. Но это, повторюсь, исключения.
--
Re[2]: Определение ближайшего числа, делимого нацело на 4
Здравствуйте, Панда, Вы писали:
П>Здравствуйте, Аноним, Вы писали:
А>>Простой вопрос: Дано число А, которое не делится нацело на 4. Необходимо определить ближайшее числу А число В (В > А), которое будет делиться нацело на 4. А>>Но мне кажется есть более простое решение ...
П>Самое простое и изящное, что приходит в голову — использовать паттерн "визитор" совместно с паттерном "стратегия". С помощью фабрики стратегий создается стратегия, которая умеет определять ближайшее делящееся на 4 число, визитор посещает число и применяет к нему выбранную стратегию. Конкретные реализации математической части лучше поискать в интернете — наверняка же эта задача уже кем-то решалась, так зачем изобретать велосипед?
Как ты мог забыть о потокобезопасном синглтоне???
--
Re[2]: Определение ближайшего числа, делимого нацело на 4
Здравствуйте, Панда, Вы писали:
А>>Простой вопрос: Дано число А, которое не делится нацело на 4. Необходимо определить ближайшее числу А число В (В > А), которое будет делиться нацело на 4. А>>Но мне кажется есть более простое решение ...
П>Самое простое и изящное, что приходит в голову — использовать паттерн "визитор" совместно с паттерном "стратегия". С помощью фабрики стратегий создается стратегия, которая умеет определять ближайшее делящееся на 4 число, визитор посещает число и применяет к нему выбранную стратегию. Конкретные реализации математической части лучше поискать в интернете — наверняка же эта задача уже кем-то решалась, так зачем изобретать велосипед?
Стронг джава бэкграунд детектед
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Здравствуйте, rg45, Вы писали:
R>Сложноватый assert получился. Глядя на него, невольно думаешь, а не обложить ли его юнит-тестами
Будущее за автоматическим доказательством корректности программ, assert несмотря на свою рудиментарность такому доказательству ближе чем юнит-тесты.
Вот вариант почти дословно перелагающий условие задачи на язык assertions:
assert(a % 4 != 0); // Дано число А, которое не делится нацело на 4.
b = . . . // Необходимо определить
assert(b > a); // ближайшее числу А число В (В > А)for (int c = a + 1; c < b; ++c)
assert(c % 4 != 0);
assert(b % 4 == 0); // , которое будет делиться нацело на 4.
Здравствуйте, igna, Вы писали:
I>Будущее за автоматическим доказательством корректности программ,
PEX в этом плане порою неплохо помогает!
I>assert несмотря на свою рудиментарность такому доказательству ближе чем юнит-тесты.
Ассёрты, безусловно, хороши, но проблема в том, что они (обычно) исключаются из релиз-версии.
Поэтому если в продакшн-коде у клиента возникнет бага (как например, вот такая
Здравствуйте, andy1618, Вы писали:
A>Ассёрты, безусловно, хороши, но проблема в том, что они (обычно) исключаются из релиз-версии. A>Поэтому если в продакшн-коде у клиента возникнет бага (как например, вот такая
Здравствуйте, Аноним, Вы писали:
А>Простой вопрос: Дано число А, которое не делится нацело на 4. Необходимо определить ближайшее числу А число В (В > А), которое будет делиться нацело на 4.
А>Можно сделать циклом: А>Но мне кажется есть более простое решение ...
Я фигею, просто слов нет. А если бы это была задачка по математике, а не по программированию, как бы ты ее решал? Тоже циклом? Включи мозг, задача для 4 класса по математике
Здравствуйте, ilnar, Вы писали:
BZ>>a/4*4+4
BZ>>вместо того чтобы маяться хернёй с bit fiddling and unit tests around it
I>это смотря сколько раз этот код выполняться будет
Любой нормальный компилятор умножения/деления на степени двойки превращает в соответствующие сдвиги.
А остатки от деления — в соответствующие битовые И.
Это я наблюдал лично в gcc в виде инструкций сдвига в ассемблере, а насчет битового И: он у меня тип, инстанцировавшийся целым числом, являвшимся остатком от деления некоей константы на 4 превратил в "константа & 3" — я долго тормозил, глядя на это, потому что точно помнил, что ничего такого не писал.
Подобные преобразования компилятору делать легче легкого, так что не надо фигней в коде заниматься.
Здравствуйте, rg45, Вы писали:
R>Да, действительно, условие прочел невнимательно. Давайте будем следовать условию строго. Все равно в формуле, которую предложил BulatZiganshin содержится ошибка. Например для a = -5 результатом должно быть -4. А по этой формуле получается 0.
Если строго следовать стандарту, то -5/4 может дать как -1, так и -2, это зависит от реализации:
The binary / operator yields the quotient, and the binary % operator yields the remainder from the division
of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative;
if not, the sign of the remainder is implementation-defined74).
Как видишь, гарантируется толко соотношение между частным и остатком, и все это зависит от того, какой знак будет иметь остаток.
Только в С++0х явно закреплено, что округление всегда в сторону нуля:
The binary / operator yields the quotient, and the binary % operator yields the remainder from the division
of the first expression by the second. If the second operand of / or % is zero the behavior is undefined. For
integral operands the / operator yields the algebraic quotient with any fractional part discarded;81 if the
quotient a/b is representable in the type of the result, (a/b)*b + a%b is equal to a.
Здравствуйте, rg45, Вы писали:
R>Здравствуйте, BulatZiganshin, Вы писали:
А>>>Простой вопрос: Дано число А, которое не делится нацело на 4. Необходимо определить ближайшее числу А число В (В > А), которое будет делиться нацело на 4.
BZ>>a/4*4+4
BZ>>вместо того чтобы маяться хернёй с bit fiddling and unit tests around it
R>Херней, говоришь? А проверь-ка свое решение для a = 4, получается 8.
внимательно читаем выделенное
Re[2]: Определение ближайшего числа, делимого нацело на 4
Здравствуйте, jazzer, Вы писали:
J>Я фигею, просто слов нет. А если бы это была задачка по математике, а не по программированию, как бы ты ее решал? Тоже циклом? Включи мозг, задача для 4 класса по математике
Почему обязательно циклом?
Можно случайные числа использовать — до тысячи, например, раз бросать, выпавшее умножать на 4 и сравнивать.
После этого будет некоторая уверенность, что число найдено — или не делится на 4.
Еще память можно использовать — все совпавшие числа складывать в кеш какой-нибудь — и вначале сравнивать с ним.
Re[2]: Определение ближайшего числа, делимого нацело на 4
Здравствуйте, jazzer, Вы писали:
J>Я фигею, просто слов нет. А если бы это была задачка по математике, а не по программированию, как бы ты ее решал? Тоже циклом? Включи мозг, задача для 4 класса по математике
Решение циклом в данном случае не так плохо. Хороший компилятор всегда сможет снять две-три итерации и сделать этот цикл линейным. А даже и не снимет -- лишняя обратная ветка в графе выполнения -- сущие пустяки по сравнению с багами, на которые наталкивается битовая магия при близости к гранчиным условиям (что например должно быть ближайшим нацело делящимся на 4 к INT_MAX? Хотите проверить на этом большинство "решений" из этой ветки? а циклом такое отсекается тривиально).
