Как перестать допускать offbyone error?

Question

[SoloFree]

Как перестать допускать offbyone error? При реализации алгоритмов иногда ошибаюсь. Может быть есть какие то правила? Секретные китайские техники и приемы?

Answer 1

[Алексей Уколов]

Эти ошибки, по сути, логические.
Значит, чтобы их не допускать, нужно следить за логикой и смыслом. Главные инструменты, которые могут в этом помочь - декомпозиция на небольшие фрагменты и осмысленное именование переменных и функций. Немудрено ошибиться, если у вас, например, три одинаковых вложенных цикла с переменными i, j и k.

Answer 2

[AM5800]

Мне помогло олимпиадное программирование.
Очень быстро становится очевидно, что выгоднее сразу написать без ошибки, чем потом мучительно ее искать.
В общем, приходилось заставлять себя быть более внимательным с этими индексами. И со временем стало проще.

Но вообще, самый лучший способ избегать offbyone ошибок - это не использовать индексы вообще.
Свертки там всякие. For each вместо for и прочее. И вообще, больше стандартных алгоритмов/функций.

Вот пример для C++: допустим, вам нужно взять последний элемент массива длины n. Тогда индекс этого элемента будет равен n-1. Вот вам и возможность ошибиться. Но если использовать вместо массива vector - то у него уже можно просто взять back().

Comments

[SoloFree]

Можете книгу посоветовать по олимпиадному программированию? Проверенную личным опытом.

[AM5800]

Эм. Именно по ОП - нет. Но все, что вам нужно - это хорошее введение в алгоритмы.
Я их изучал по вот этой шикарной книге habrahabr.ru/company/spbau/blog/222427
Ну а потом Кормен, конечно же.

Еще попробуйте порешать контесты на codeforces.com

И еще. Попробуйте изучить какой-нибудь функциональный язык программирования. Они очень быстро выбивают из людей всю эту дурь про индексы =) Да и в принципе полезно.