Ошибка на единицу: различия между версиями
[отпатрулированная версия] | [непроверенная версия] |
РоманСузи (обсуждение | вклад) викификация, оформление |
Нет описания правки |
||
(не показана 41 промежуточная версия 19 участников) | |||
Строка 1: | Строка 1: | ||
'''Ошибка на единицу''' или '''ошибка неучтённой единицы''' ({{lang-en|off-by-one error}}) — логическая ошибка в алгоритме, включающая в частности дискретный вариант нарушения граничных условий. Ошибка часто встречается в программировании, когда количество итераций пошагового [[Цикл (программирование)|цикла]] оказывается на единицу меньше или больше необходимого. Например, программист при сравнении указывает «меньше или равно» |
'''Ошибка на единицу''' или '''ошибка неучтённой единицы''' ({{lang-en|off-by-one error}}) — логическая ошибка в алгоритме (или в математических вычислениях), включающая в частности дискретный вариант нарушения граничных условий. |
||
Ошибка часто встречается в программировании, когда количество итераций пошагового [[Цикл (программирование)|цикла]] оказывается на единицу меньше или больше необходимого. Например, программист при сравнении указывает «меньше или равно» вместо «меньше», или ошибается, отсчитывая начало последовательности не с нуля, а с единицы ([[Индекс (массив)|индексация]] [[Массив (программирование)|массивов]] во многих [[Язык программирования|языках программирования]] начинается с нуля). |
|||
== Перебор элементов массива == |
== Перебор элементов массива == |
||
Рассмотрим [[Массив (программирование)|массив]] элементов, в котором обрабатываются элементы с ''m''-го по ''n''-й включительно. Сколько членов массива будет обработано? Ответ ''n-m'' является ошибкой на единицу и примером ошибки |
Рассмотрим [[Массив (программирование)|массив]] элементов, в котором обрабатываются элементы с ''m''-го по ''n''-й включительно. Сколько членов массива будет обработано? Ответ ''n-m'' является ошибкой на единицу и примером «[[#Ошибка заборного столба|ошибки заборного столба]]». Правильный ответ — ''n-m+1''. |
||
Для уменьшения ошибок из-за неучтённых единиц диапазон индексирования часто представляют полуоткрытыми интервалами. Так диапазон от ''m'' до ''n'' (включительно) представляется диапазоном от ''m'' (включительно) до ''n+1'' (не включая последнее значение). Например, [[Цикл (программирование)|цикл]], который проходит пять значений, может быть записан с использованием полуоткрытого интервала от 0 до 5: |
Для уменьшения ошибок из-за неучтённых единиц диапазон индексирования часто представляют полуоткрытыми интервалами. Так, диапазон от ''m'' до ''n'' (включительно) представляется диапазоном от ''m'' (включительно) до ''n+1'' (не включая последнее значение). Например, [[Цикл (программирование)|цикл]], который проходит пять значений, может быть записан с использованием полуоткрытого интервала от 0 до 5 ([[Си (язык программирования)|язык C]]): |
||
<source lang="c"> |
<source lang="c"> |
||
for (i = 0; i < 5; |
for (i = 0; i < 5; ++i) |
||
{ |
{ |
||
/* тело цикла */ |
/* тело цикла */ |
||
Строка 13: | Строка 15: | ||
</source> |
</source> |
||
[[Цикл (программирование)|Тело цикла]] выполняется |
[[Цикл (программирование)|Тело цикла]] выполняется начиная с i, равного 0; затем i принимает значение 1, 2, 3 и наконец на последующем шаге становится равным 4. Когда i становится равным 5, то условие i < 5 не выполняется и цикл заканчивается. Однако, если условие сравнения будет <= (меньше или равно), цикл будет выполняться шесть раз: i будет принимать значения 0, 1, 2, 3, 4 и 5. Подобным же образом, если i будет инициализировано в 1, а не в 0, в цикле будет только 4 итерации: i примет значения 1, 2, 3 и 4. Обе эти альтернативы ведут к ошибке на единицу. |
||
Подобная же ошибка может возникнуть, если цикл [[ |
Подобная же ошибка может возникнуть, если цикл [[цикл с постусловием|do-while]] используется вместо цикла [[Цикл с предусловием|while]] (или наоборот). Цикл do-while гарантирует выполнение по крайней мере одной итерации, поскольку проверка условия осуществляется после выполнения тела цикла. |
||
Ошибки, связанные с массивами, могут также являться результатом различия в языках программирования. Отсчёт с нуля традиционен, но некоторые языки ведут |
Ошибки, связанные с массивами, могут также являться результатом различия в языках программирования. Отсчёт с нуля традиционен, но некоторые языки ведут отсчёт с 1. В языках [[Паскаль (язык программирования)|Паскаль]] и [[Фортран]] можно определять индексы<ref>Традиционно в языке Паскаль отсчёт принято начинать с единицы.</ref>. Это позволяет настроить модель массива на предметную область. |
||
Количество элементов q в массиве можно подсчитать следующим образом: |
|||
q = n-m-1 в открытом интервале (A, B) где начальный и конечный элемент не включены в массив. |
|||
q= n-m+1 в закрытом интервале [A, B] где начальный и конечный элемент включены в массив. |
|||
q = n-m в полузакрытом (полуоткрытом) интервале (A, B] или [A,B) где включён в массив только один из граничных элементов. |
|||
== Ошибка заборного столба == |
== Ошибка заборного столба == |
||
[[Файл:Fencepost error.svg|thumb|250px|Прямой забор с ''n'' секциями имеет ''n+1'' столбов |
[[Файл:Fencepost error.svg|thumb|250px|Прямой забор с ''n'' секциями имеет ''n+1'' столбов]] |
||
Ошибка заборного |
Ошибка заборного столба (иногда её называют ошибкой телеграфного столба или фонарного столба) является частным случаем ошибки на единицу. Следующая задача иллюстрирует эту ошибку: |
||
<blockquote> |
|||
Вы ставите прямой забор длиной 30 метров и ставите столбы каждые 3 метра. Сколько столбов вам необходимо? |
|||
</blockquote> |
|||
«Очевидный» на первый взгляд ответ — 10, ошибочен. |
«Очевидный» на первый взгляд ответ — 10, ошибочен. |
||
<br>Забор имеет 30 : 3 = 10 секций. Но столбов требуется 11, на один больше. |
|||
Обратная ошибка возникает, когда известно количество столбов, а количество секций полагается равным количеству столбов. В действительности количество секций на единицу меньше количества столбов. |
Обратная ошибка возникает, когда известно количество столбов, а количество секций полагается равным количеству столбов. В действительности количество секций на единицу меньше количества столбов. |
||
Строка 31: | Строка 44: | ||
В более общем виде задача может быть сформулирована следующим образом: если есть n телеграфных столбов, сколько имеется промежутков между ними? |
В более общем виде задача может быть сформулирована следующим образом: если есть n телеграфных столбов, сколько имеется промежутков между ними? |
||
Корректный ответ может быть n-1, если линия столбов открыта с |
Корректный ответ может быть n-1, если линия столбов открыта с обоих концов; n если столбы образуют круг; n+1 — если свободные пространства с обоих концов считать промежутками. Точное определение проблемы должно быть тщательно изучено, поскольку решение, верное в одной ситуации, может дать ошибочный результат в другой. Ошибка заборного столба возникает из-за того, что считаются столбы вместо промежутков между ними или наоборот, а также пренебрежения вопросом, нужно ли рассматривать один или два конца ряда. |
||
Ошибка заборного столба может также проявить себя при |
Ошибка заборного столба может также проявить себя при счёте других элементов, а не только длин. Примером может служить [[пирамида времени]], которая должна состоять из 120 блоков, каждый из которых помещается на своё место с интервалом в 10 лет. Для её строительства с начала установки первого блока и до последнего блока требуется 1190 лет, а не 1200. Одним из самых ранних примеров ошибки заборного столба, касающихся времени, был [[Юлианский календарь]], где изначально неправильно рассчитывались [[Високосный год|високосные годы]] по причине расчёта с включением, а не с исключением. Из-за этого в расчёте високосный год повторялся через 3 года, а не через 4. |
||
Ошибка заборного столба в редких случаях может вызываться неожиданным порядком входных данных, который может, например, полностью свести к нулю эффективность использования [[Двоичное дерево|бинарного дерева]] или выполнения [[Хеширование| |
Ошибка заборного столба в редких случаях может вызываться неожиданным порядком входных данных, который может, например, полностью свести к нулю эффективность использования [[Двоичное дерево|бинарного дерева]] или выполнения [[Хеширование|хеш-функции]]. Эта ошибка имеет отношение к различию между ожидаемым и наихудшим поведением алгоритма. |
||
При больших числах ошибка на единицу часто не столь важна в конкретном случае. При |
При больших числах ошибка на единицу часто не столь важна в конкретном случае. При небольших числах, однако, и в некоторых специфических случаях, где точность первостепенна, появление ошибки на единицу может быть катастрофической. Иногда ошибка может повториться и, следовательно, усилена, тем, кто выполняет некорректные вычисления, если следующий человек делает эту ошибку снова (конечно, эта ошибка может быть совершена и в обратную сторону). |
||
В качестве примера такой ошибки можно взять функцию linspace()<ref> |
В качестве примера такой ошибки можно взять функцию linspace()<ref>{{Cite web |url=http://help.scilab.org/docs/5.4.1/ru_RU/linspace.html |title=вектор с равномерными интервалами между элементами |access-date=2015-02-04 |archive-date=2015-02-04 |archive-url=https://web.archive.org/web/20150204142651/http://help.scilab.org/docs/5.4.1/ru_RU/linspace.html |deadlink=no }}</ref> из вычислительного языка [[MATLAB|Matlab]], параметрами которой являются: наименьшая величина, наибольшая величина и количество величин, а не: наименьшая величина, наибольшая величина и количество шагов. Программист, который неправильно поймёт, что из себя представляет третий параметр, будет считать, что linspace(0,10,5) сгенерирует последовательность [0,2,4,6,8,10], но вместо этого получит [0, 2.5, 5, 7.5, 10]. |
||
== Проблемы безопасности == |
== Проблемы безопасности == |
||
{{Переписать раздел}} |
|||
Обычная ошибка на единицу, которая приводит к проблеме безопасности — это |
Обычная ошибка на единицу, которая приводит к проблеме безопасности — это некорректное использование функции [[strncat|strncat()]] из [[Стандартная библиотека языка Си|стандартной библиотеки]] [[ANSI C|C]]. Обычное недоразумение, связанное с [[strncat|strncat()]], заключается в том, что null-байт<ref>Символ, однобайтовый код которого равен нулю. Библиотека C поддерживает правило, по которому такой байт обозначает конец строки</ref> не может быть записан дальше, чем длина строки. В действительности функция пишет null-байт за указанной длиной строки, если третий параметр равен или превышает эту длину. Следующий код содержит именно такую ошибку: |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
{ |
{ |
||
char buf[15]; |
char buf[15]; |
||
buf[0] = '\0'; |
|||
strncat(buf, s, sizeof(buf)); // последний параметр должен быть равен |
strncat(buf, s, sizeof(buf)); // ОШИБКА - последний параметр должен быть равен sizeof(buf)-1 |
||
//sizeof(buf)-1 |
|||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Ошибка на единицу обычна при использовании стандартной библиотеки C, потому что в ней не реализован единый подход по поводу того, отнимать или нет 1: функции подобные [[gets|fgets()]] и [[strncpy|strncpy()]] никогда не выйдут за указанную им длину (fgets() сама отнимает 1 и извлекает (length-1) байтов), тогда как другие функции, подобные strncat(), осуществляют запись далее указанной для строки длины. По этой причине программист должен помнить для каких функций требуется отнимать 1. |
Ошибка на единицу обычна при использовании стандартной библиотеки C, потому что в ней не реализован единый подход по поводу того, отнимать или нет 1: функции, подобные [[gets|fgets()]] и [[strncpy|strncpy()]], никогда не выйдут за указанную им длину (fgets() сама отнимает 1 и извлекает (length-1) байтов), тогда как другие функции, подобные strncat(), осуществляют запись далее указанной для строки длины. По этой причине программист должен помнить, для каких функций требуется отнимать 1. |
||
В некоторых системах (особенно в архитектуре с порядком байтов от младшего к старшему) это может привести к переписыванию значимых байтов в стеке процесса, что может создать условие, когда злоумышленник получает данные, позволяющие ему вызывать процедуру процесса<ref>Запись данных за границу буфера называется [[Переполнение буфера|'''ошибкой переполнения буфера''']]. |
В некоторых системах (особенно в архитектуре с порядком байтов от младшего к старшему) это может привести к переписыванию значимых байтов в стеке процесса, что может создать условие, когда злоумышленник получает данные, позволяющие ему вызывать процедуру процесса<ref>Запись данных за границу буфера называется [[Переполнение буфера|'''ошибкой переполнения буфера''']].</ref>. |
||
Один из подходов, с помощью которого можно решать такие проблемы — использовать модификацию указанных функций, которые считают |
Один из подходов, с помощью которого можно решать такие проблемы — использовать модификацию указанных функций, которые считают количество записанных байтов с учётом длины буфера, вместо того, чтобы писать или читать максимальное количество байтов. Примером могут служить функции [[strlcat|strlcat()]] и [[strlcpy|strlcpy()]], которые часто рассматриваются как «безопасные», потому что исключают случайную возможность записи за концом буфера (в коде выше вызов strlcat(buf, s, sizeof(buf)) устраняет ошибку безопасности). |
||
== См. также == |
== См. также == |
||
*[[Массив (программирование)]] |
|||
*[[Си (язык программирования)]] |
|||
*[[Ошибка (программирование)]] |
|||
*[[Отладка программы]] |
|||
*[[Стандартная библиотека языка Си]] |
|||
*[[Список функций стандартной библиотеки Си]] |
|||
*[[Переполнение стека]] |
|||
== Примечания == |
== Примечания == |
||
Строка 74: | Строка 87: | ||
== Ссылки == |
== Ссылки == |
||
*[https://code-live.ru/post/cpp-arrays/ Массивы в C++ ] {{Wayback|url=https://code-live.ru/post/cpp-arrays/ |date=20150421225353 }} |
|||
*[http://dolphinsbay.narod.ru/Reefs.html#1 Ошибка заборных столбов] {{Wayback|url=http://dolphinsbay.narod.ru/Reefs.html#1 |date=20150204142650 }} |
|||
*[http://wiki.mvtom.ru/index.php/%D0%9E%D1%82%D0%BB%D0%B0%D0%B4%D0%BA%D0%B0_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D1%8B Ошибки программирования] {{Wayback|url=http://wiki.mvtom.ru/index.php/%D0%9E%D1%82%D0%BB%D0%B0%D0%B4%D0%BA%D0%B0_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D1%8B |date=20160305112245 }} |
|||
*[http://shgpi.edu.ru/pirogov/cpp/ Заметки по языкам C и C++] {{Wayback|url=http://shgpi.edu.ru/pirogov/cpp/ |date=20160414212247 }} |
|||
{{rq|wikify|style|sources}} |
{{rq|wikify|style|sources}} |
||
Текущая версия от 03:52, 6 мая 2024
Ошибка на единицу или ошибка неучтённой единицы (англ. off-by-one error) — логическая ошибка в алгоритме (или в математических вычислениях), включающая в частности дискретный вариант нарушения граничных условий.
Ошибка часто встречается в программировании, когда количество итераций пошагового цикла оказывается на единицу меньше или больше необходимого. Например, программист при сравнении указывает «меньше или равно» вместо «меньше», или ошибается, отсчитывая начало последовательности не с нуля, а с единицы (индексация массивов во многих языках программирования начинается с нуля).
Перебор элементов массива
[править | править код]Рассмотрим массив элементов, в котором обрабатываются элементы с m-го по n-й включительно. Сколько членов массива будет обработано? Ответ n-m является ошибкой на единицу и примером «ошибки заборного столба». Правильный ответ — n-m+1.
Для уменьшения ошибок из-за неучтённых единиц диапазон индексирования часто представляют полуоткрытыми интервалами. Так, диапазон от m до n (включительно) представляется диапазоном от m (включительно) до n+1 (не включая последнее значение). Например, цикл, который проходит пять значений, может быть записан с использованием полуоткрытого интервала от 0 до 5 (язык C):
for (i = 0; i < 5; ++i)
{
/* тело цикла */
}
Тело цикла выполняется начиная с i, равного 0; затем i принимает значение 1, 2, 3 и наконец на последующем шаге становится равным 4. Когда i становится равным 5, то условие i < 5 не выполняется и цикл заканчивается. Однако, если условие сравнения будет <= (меньше или равно), цикл будет выполняться шесть раз: i будет принимать значения 0, 1, 2, 3, 4 и 5. Подобным же образом, если i будет инициализировано в 1, а не в 0, в цикле будет только 4 итерации: i примет значения 1, 2, 3 и 4. Обе эти альтернативы ведут к ошибке на единицу.
Подобная же ошибка может возникнуть, если цикл do-while используется вместо цикла while (или наоборот). Цикл do-while гарантирует выполнение по крайней мере одной итерации, поскольку проверка условия осуществляется после выполнения тела цикла.
Ошибки, связанные с массивами, могут также являться результатом различия в языках программирования. Отсчёт с нуля традиционен, но некоторые языки ведут отсчёт с 1. В языках Паскаль и Фортран можно определять индексы[1]. Это позволяет настроить модель массива на предметную область.
Количество элементов q в массиве можно подсчитать следующим образом:
q = n-m-1 в открытом интервале (A, B) где начальный и конечный элемент не включены в массив.
q= n-m+1 в закрытом интервале [A, B] где начальный и конечный элемент включены в массив.
q = n-m в полузакрытом (полуоткрытом) интервале (A, B] или [A,B) где включён в массив только один из граничных элементов.
Ошибка заборного столба
[править | править код]Ошибка заборного столба (иногда её называют ошибкой телеграфного столба или фонарного столба) является частным случаем ошибки на единицу. Следующая задача иллюстрирует эту ошибку:
Вы ставите прямой забор длиной 30 метров и ставите столбы каждые 3 метра. Сколько столбов вам необходимо?
«Очевидный» на первый взгляд ответ — 10, ошибочен.
Забор имеет 30 : 3 = 10 секций. Но столбов требуется 11, на один больше.
Обратная ошибка возникает, когда известно количество столбов, а количество секций полагается равным количеству столбов. В действительности количество секций на единицу меньше количества столбов.
В более общем виде задача может быть сформулирована следующим образом: если есть n телеграфных столбов, сколько имеется промежутков между ними?
Корректный ответ может быть n-1, если линия столбов открыта с обоих концов; n если столбы образуют круг; n+1 — если свободные пространства с обоих концов считать промежутками. Точное определение проблемы должно быть тщательно изучено, поскольку решение, верное в одной ситуации, может дать ошибочный результат в другой. Ошибка заборного столба возникает из-за того, что считаются столбы вместо промежутков между ними или наоборот, а также пренебрежения вопросом, нужно ли рассматривать один или два конца ряда.
Ошибка заборного столба может также проявить себя при счёте других элементов, а не только длин. Примером может служить пирамида времени, которая должна состоять из 120 блоков, каждый из которых помещается на своё место с интервалом в 10 лет. Для её строительства с начала установки первого блока и до последнего блока требуется 1190 лет, а не 1200. Одним из самых ранних примеров ошибки заборного столба, касающихся времени, был Юлианский календарь, где изначально неправильно рассчитывались високосные годы по причине расчёта с включением, а не с исключением. Из-за этого в расчёте високосный год повторялся через 3 года, а не через 4.
Ошибка заборного столба в редких случаях может вызываться неожиданным порядком входных данных, который может, например, полностью свести к нулю эффективность использования бинарного дерева или выполнения хеш-функции. Эта ошибка имеет отношение к различию между ожидаемым и наихудшим поведением алгоритма.
При больших числах ошибка на единицу часто не столь важна в конкретном случае. При небольших числах, однако, и в некоторых специфических случаях, где точность первостепенна, появление ошибки на единицу может быть катастрофической. Иногда ошибка может повториться и, следовательно, усилена, тем, кто выполняет некорректные вычисления, если следующий человек делает эту ошибку снова (конечно, эта ошибка может быть совершена и в обратную сторону).
В качестве примера такой ошибки можно взять функцию linspace()[2] из вычислительного языка Matlab, параметрами которой являются: наименьшая величина, наибольшая величина и количество величин, а не: наименьшая величина, наибольшая величина и количество шагов. Программист, который неправильно поймёт, что из себя представляет третий параметр, будет считать, что linspace(0,10,5) сгенерирует последовательность [0,2,4,6,8,10], но вместо этого получит [0, 2.5, 5, 7.5, 10].
Проблемы безопасности
[править | править код]Этот раздел должен быть полностью переписан. |
Обычная ошибка на единицу, которая приводит к проблеме безопасности — это некорректное использование функции strncat() из стандартной библиотеки C. Обычное недоразумение, связанное с strncat(), заключается в том, что null-байт[3] не может быть записан дальше, чем длина строки. В действительности функция пишет null-байт за указанной длиной строки, если третий параметр равен или превышает эту длину. Следующий код содержит именно такую ошибку:
void foo (const char *s)
{
char buf[15];
buf[0] = '\0';
strncat(buf, s, sizeof(buf)); // ОШИБКА - последний параметр должен быть равен sizeof(buf)-1
}
Ошибка на единицу обычна при использовании стандартной библиотеки C, потому что в ней не реализован единый подход по поводу того, отнимать или нет 1: функции, подобные fgets() и strncpy(), никогда не выйдут за указанную им длину (fgets() сама отнимает 1 и извлекает (length-1) байтов), тогда как другие функции, подобные strncat(), осуществляют запись далее указанной для строки длины. По этой причине программист должен помнить, для каких функций требуется отнимать 1.
В некоторых системах (особенно в архитектуре с порядком байтов от младшего к старшему) это может привести к переписыванию значимых байтов в стеке процесса, что может создать условие, когда злоумышленник получает данные, позволяющие ему вызывать процедуру процесса[4].
Один из подходов, с помощью которого можно решать такие проблемы — использовать модификацию указанных функций, которые считают количество записанных байтов с учётом длины буфера, вместо того, чтобы писать или читать максимальное количество байтов. Примером могут служить функции strlcat() и strlcpy(), которые часто рассматриваются как «безопасные», потому что исключают случайную возможность записи за концом буфера (в коде выше вызов strlcat(buf, s, sizeof(buf)) устраняет ошибку безопасности).
См. также
[править | править код]- Массив (программирование)
- Си (язык программирования)
- Ошибка (программирование)
- Отладка программы
- Стандартная библиотека языка Си
- Список функций стандартной библиотеки Си
- Переполнение стека
Примечания
[править | править код]- ↑ Традиционно в языке Паскаль отсчёт принято начинать с единицы.
- ↑ вектор с равномерными интервалами между элементами . Дата обращения: 4 февраля 2015. Архивировано 4 февраля 2015 года.
- ↑ Символ, однобайтовый код которого равен нулю. Библиотека C поддерживает правило, по которому такой байт обозначает конец строки
- ↑ Запись данных за границу буфера называется ошибкой переполнения буфера.
Ссылки
[править | править код]- Массивы в C++ Архивная копия от 21 апреля 2015 на Wayback Machine
- Ошибка заборных столбов Архивная копия от 4 февраля 2015 на Wayback Machine
- Ошибки программирования Архивная копия от 5 марта 2016 на Wayback Machine
- Заметки по языкам C и C++ Архивная копия от 14 апреля 2016 на Wayback Machine
Для улучшения этой статьи желательно:
|