아.. 기존에 쓰다가 날려버렸다..
공부를 하다가 신기한 문제를 만났다 그 문제는 다음과 같다
"100미터짜리 울타리를 만들고 100미터마다 기둥을 세운다면 몇 개의 기둥을 세워야 할까?"
나는 많은 사람들의 답처럼 10개라고 답하였지만 답은 11개였다 이런 종류의 1 차이 오류를 울타리 말뚝 오류라고 부른단다
이에 흥미를 느껴서 구글 검색을 해보았지만 죄다 영어고 몇개 없는 한글로 되어 있는 것도 한두줄뿐이였다. 그래서 결국 영어울렁증이 있음에도 초반에는 자력으로 번역을 하다가 구글번역기 힘을 빌려 번역을 해보았다(내가 해석한 것보다 구글번역이 나은것 같다).
그래서 보기좋게 번역한 것도 아니고 그냥 흥미를 느껴 재미삼아 한 것이기 때문에 번역가지고 뭐라하지는 마라
처음 나의 답 풀이
0 |
10 |
20 |
30 |
40 |
50 |
60 |
70 |
80 |
90 |
100 |
말뚝 |
말뚝 |
말뚝 |
말뚝 |
말뚝 |
말뚝 |
말뚝 |
말뚝 |
말뚝 |
말뚝 |
|
그림을 사용하여 문제를 풀었는데 0부터 10까지 말뚝 한 개 ,10부터 20까지 말뚝 한 개, 이런식으로 계산을 하여 말뚝 10개가 나왔다
그러나 말뚝 사이의 길이를 측정하면 90미터가 된다 그렇다 일단 말뚝을 한개 박고 시작을 해야 이문제가 해결이 된다
물론 10개가 답이 되는 방법도 있다(일자로 나열하지말고 원을 만들면 해결이 된다)
번역:Off-by-one error
일반적으로 OBOB (off-by-one 버그), OB1 오류 또는 "원하지 않는 추가 크기"라고도 하는 off-by-one 오류 (OBOE)는 경계조건의 등식과 관련된 논리 오류이다. 이것은 반복문의 루프가 너무 많이 또는 너무 적은 횟수로 반복 할 때 종종 컴퓨터 프로그래밍에서 한다. 이 문제는 프로그래머가 "작거나 같음"을 사용하는 것과 같이 잘못된 숫자로 비교할 때나 시퀀스가 하나가 아닌 0에서 시작한다는 점을 고려하지 않을 때 발생할 수 있다. 이것은 또한 수학적 맥락에서 발생할 수 있다.
Looping over arrays
항목의 배열을 고려하고 m ~ n (항목 포함) 항목을 처리해야합니다. 몇 개의 아이템이 있습니까? 직관적인 대답은 n-m 일지 모르지만 그것은 하나에 의해 떨어져 있고, fencepost 오류를 보여줍니다. 정답은 (n - m) + 1입니다.
이러한 이유 때문에 계산 범위는 종종 반 개방 형식으로 표시됩니다. fencepost 오류를 피하기 위해 m에서 n까지의 범위는 m (포함)부터 n + 1 (포함되지 않음)의 범위로 나타납니다. 예를 들어, 5 회 반복하는 루프 (0에서 4 포함)는 0에서 5까지의 반 개방 형식으로 작성할 수 있습니다.
for (i = 0; i < 5; i++)
{
/* Body of the loop */
}
위의 예의 루프문에서 우선 i가 0인 상태에서 실행된다 i는 반복문을 거쳐 1,2,3 그리고 마지막으로 4가 된다. 그 시점에서 i는 5가 되고 i<5는 거짓이 됨으로 루프는 끝나게 된다. 그러나 사용된 비교가 <=(작거나 같음) 인 경우 루프는 6번 돌게 된다. 이 경우 i는 0,1,2,3,4,5값이 되는 것이다. 마찬가지로 i가 1이 아니라 0이라면 4번만 반복되고 i는 1,2,3,4를 가진다 두 가지 대안 모두 Off-by-one error를 유발하게 된다.
do-while 루프가 while 루프 대신에 사용되는 경우 (또는 그 반대로) 다른 에러가 발생할 수 있다. do-while 루프는 적어도 한 번 이상 실행되는 것이 보장한다.
배열 관련 혼동은 프로그래밍 언어의 차이로 인해 발생할 수도 있다. 0부터 번호 매김이 가장 일반적이지만 일부 언어는 1로 배열 번호 매기기를 시작한다. 파스칼은 사용자 정의 색인이있는 배열을 가지고 있습니다. 이렇게하면 문제 도메인 다음에 배열 인덱스를 모델링 할 수 있다.
Fencepost error
fencepost 오류(전신주,램프-기둥,울타리,울타리 말뚝 오류라고도 함)는 특정 유형의 off-by-one 오류이다. 이 오류는 비트루비우스 저서에 나온다.
문제: 30m 길이의 직선형 울타리를 3m 간격으로 배치하면 얼마나 많은 말뚝이 필요할까?
순진한 대답으로 10을 대답하지만 틀렸다. 울타리에는 10개의 구역이 있지만 11개의 말뚝이 필요하다.
역의 오류(reverse error)는 말뚝이가 알려지고 구역 수가 동일한 것으로 가정 할 때 발생한다 실제 구역 수는 말뚝 보다 1 적다
보다 일반적으로 다음과 같이 설명 할 수 있다.
말뚝이 n 개 있는 경우, 그 사이에 몇 개의 구역이 있을까?
정답은 말뚝이 행으로 열린 경우 n-1,루프를 형성하는 경우 n, 말뚝 순서의 열린면이 구역으로 계산되는 경우 n+1이 될 수 있다.
한 상황에 대한 설정이 다른 상황에 대해 잘못된 대답을 줄 수 있으므로 정확한 문제 정의를 고려해야한다. Fencepost error는 그 사이의 공백이 아닌 사물의 갯수로 계산되거나 행의 한쪽 또는 양쪽 끝을 계산할지 여부를 고려하지 않음으로써 발생한다.
Fencepost error는 길이가 아닌 단위에서도 발생 할 수 있다. 예를 들어, 시간 피라미드는 블록 사이에 10년 간격으로 배치 된 120개의 블록으로 구성되어 있으며 첫 번째 블록을 설치한 시점에서 마지막 블록까지 구축하는데 1200년이 걸리지 않는다(1190년이 걸린다). 가장 초기의 Fencepost error 중 하나는 율리우스력이 독점적으로가 아닌 포괄적으로 계산하여 율리우스력이 원래 4년이 아닌 3년마다 윤년을 산출하기 때문에 잘못 계산이 되었다
Fencepost error는 드문 경우지만 이론적으로 효율적인 이진 트리 또는 해시 함수 구현을 완전히 막을 수 있는 예기치 않은 입력 값의 규칙성으로 인한 오류를 나타낼 수 있다. 이 오류는 알고리즘의 예상되는 동작과 최악의 동작의 차이를 포함한다.
더 큰 숫자에서 벗어나는 것은 종종 중요한 문제가 아니다. 그러나 숫자가 적을수록 정확도가 가장 중요한 특정 사례가 하나씩 잘못된 오류를 범하는 것은 재앙이 될 수 있다. 사람이 같은 종류의 실수를 다시 저지른 경우 잘못된 계산을 통과하는 사람이 이러한 문제를 반복하여 악화 될 수 있다. 물론 오류는 되돌릴 수 있다.
이 오류의 예로는 매개변수가 (lower value, upper value, number of values) 및 그렇지 않은 (lower value, upper value, number of increments) linspace()함수가 포함된 MATLAB에서 발생 할 수 있다
프로그래머는 linspace(0,10,5)의 결과로 [0,2,4,6,8,10]을 원하는지만
대신에[0, 2.5, 5, 7.5, 10]을 얻게 된다.
Security implications
보안 관련 버그가 발생하는 일반적인 off-by-one error는 C 표준 라이브러리 strncat 의 잘못된 사용으로 인해 생긴다. strncat의 일반적인 오해는 보장된 널이 최대 길이를 초과하지 않는다는 것이다. 실제로는 최대 길이를 초과하는 1바이트의 종료 널 문자를 쓴다.
다음 코드에는 이러한 버그가 포함되어 있다.
void foo (char *s)
{
char buf[15];
memset(buf, 0, sizeof(buf));
strncat(buf, s, sizeof(buf)); // Final parameter should be: sizeof(buf)-1
}
출처:https://en.wikipedia.org/wiki/Off-by-one_error