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

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

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

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

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

  • 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