Г-н Фаршеклоакин (spamsink) wrote,
Г-н Фаршеклоакин
spamsink

Работа над ошибками

Сегодня я исправил ошибку в собственном коде, которой практически ровно 10 лет. Интересно, что за всё это время она ни разу не проявлялась ни на примерах из реальной жизни, ни на стандартном пакете тестов, а была обнаружена при очередном раунде улучшения тестирования.

Даны N K-битных слагаемых. Каждый бит каждого слагаемого представлен булевской переменной (возможно, неуникальной, как, например, в случае размножения знака) или константой 0/1. Предложите алгоритм вычисления минимальной разрядности операции сложения для получения правильного результата разрядности K.

Пример: пусть требуется сложить два 8-битных слагаемых вида "aaaaaaab" и "cccccccd". Понятно, что реально складывать нужно всего несколько младших бит слагаемых, а старшие биты окончательного результата будут всегда равны старшему биту полученной суммы. Задача заключается в нахождении алгоритма вычисления оптимума для общего случая.
До исправления ошибки мой алгоритм давал правильный оптимальный ответ в подавляющем большинстве случаев, но иногда его результат был на 1 меньше, чем надо.
Tags: puzzle, work
Subscribe

  • Хочу всё знать, или физики, ау!

    Представьте себе плавательный бассейн, для конкретности стандартный олимпийский (50x25x2 м) в котором много часов никто не плавал. Вода в нём…

  • Не два, а полтора

    Довольно несложная, но на первый взгляд неочевидная задачка: запишите число 100 по основанию полтора, не используя знаков после запятой. Ну и, ради…

  • Нас скоро ждёт масса веселья

    Если кто не знает, богоспасаемый штат Техас, известный своей любовью к пложению и размножению человеков помимо их воли, недавно принял закон,…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 24 comments

  • Хочу всё знать, или физики, ау!

    Представьте себе плавательный бассейн, для конкретности стандартный олимпийский (50x25x2 м) в котором много часов никто не плавал. Вода в нём…

  • Не два, а полтора

    Довольно несложная, но на первый взгляд неочевидная задачка: запишите число 100 по основанию полтора, не используя знаков после запятой. Ну и, ради…

  • Нас скоро ждёт масса веселья

    Если кто не знает, богоспасаемый штат Техас, известный своей любовью к пложению и размножению человеков помимо их воли, недавно принял закон,…