세그먼트 오류 - 범위를 벗어나는 배열

Question

사용자가 int N을 입력하면 동일한 행이나 열에 중복이없는 Nx 눈금을 만들 수 있도록 간단한 알고리즘을 작성했습니다. 이 알고리즘은 때로 낮은 숫자로 작동하지만 세그먼트 오류가 발생합니다. 이 오류는 격자 배열의 요소를 설정하는 행의 noRowDuplicates 함수에서 발생합니다.

왜 이런 일이 일어나고 있는지 알 수 없으므로 도움이됩니다. 미리 감사드립니다!

// Author: Eric Benjamin 
// This problem was solved using recursion. fill() is the recursive function. 


#include <iostream> 
#include <cstdlib> 
#include <time.h> 

using namespace std; 

void fillOptions(); 
void fill(int arrayPosition); 
int inputNum; 
int gridSize; 
int *grid; 
int allOptionsSize = 0; 
int *allOptions; 

int main() { 
    cout << "Please enter a number!" << endl; 
    cin >> inputNum; 
    gridSize = inputNum * inputNum; 

    grid = new int[gridSize]; 
    allOptions = new int[inputNum]; 
    for (int i = 0; i < inputNum; i++) { 
     allOptions[i] = i + 1; 
     allOptionsSize++; 
    } 

    srand((unsigned)time(0)); 
    fill(0); 

    delete[] grid; 
    delete[] allOptions; 
    return 0; 
} 

bool noColumnDuplicates(int arrPosition, int valueToCheck) { 
    for (int i = 1; i < inputNum; i++) { 
     if (arrPosition - (inputNum * i) >= 0) { 
      if (grid[arrPosition - (inputNum * i)] == valueToCheck) { 
       return false; 
      } 
     } 
    } 
    return true; 
} 

bool noRowDuplicates(int arrPosition, int valueToCheck) { 
    int rowPosition = arrPosition % inputNum; // 0 to num - 1 
    if (rowPosition > 0) { 
     for (int p = 1; p < rowPosition + 1; p++) { 
      if (grid[arrPosition - p] == valueToCheck) { 
       return false; 
      } 
     } 
    } 
    return true; 
} 

void fill(int arrayPosition) { 
    if (arrayPosition < gridSize) { 
     int randomPosition = rand() % allOptionsSize; 
     grid[arrayPosition] = allOptions[randomPosition]; 
     if (noColumnDuplicates(arrayPosition, grid[arrayPosition])) { 
      if (noRowDuplicates(arrayPosition, grid[arrayPosition])) { 
       if (arrayPosition % inputNum == 0) { 
        cout << endl; 
       } 
       cout << grid[arrayPosition] << " "; 
       fill(arrayPosition + 1); 
      } else { 
       fill (arrayPosition); 
      } 
     } else { 
      fill(arrayPosition); 
     } 
    } 
} 

Answer 1

fill()을 처음 호출하면 해당 매개 변수 인 arrayPosition에 0이 전달됩니다.

gridSize은 매트릭스/어레이의 크기입니다. 당신이 당신의 fill()의 논리를 살펴보면

, 당신은 arrayPosition으로, fill()에 재귀 호출이 이루어집니다 arrayPosition하지 않는 같거나 gridSize보다 큰 것으로 결론을 내릴 것 중 하나 인 동일, 또는 1

씩 증가

arrayPosition < gridSize 일 때 fill()을 통한 모든 논리적 실행 경로는 fill()으로 재귀 호출합니다.

예를 들어, 배열/행렬의 값이 1 만 개일 경우 fill()은 적어도 하나 이상의 중첩 된 재귀 호출을 시도합니다.

이것은 잘 끝나지 않을 것입니다. 운영 체제가 더 많은 스택 공간을 프로세스에 할당하는 것을 거부하면서 운영 체제가 할당 한 최대 스택 공간을 통해 코드가 분할 오류를 일으킬 때 세그먼트 오류가 발생합니다.

이러한 종류의 제어 재귀를 피하려면 논리를 리팩토링해야합니다. 불행히도 스택 공간은 무한하지 않습니다. 표시된 논리는 근본적으로 C++에서 깨졌습니다. 꼬리 재귀 (tail recursion)를 제거하고 모든 재귀 함수 호출을 위해 스택 공간을 소비하지 않으므로 컴파일러에 의존 할 수 없습니다.

간단한 검토는 중첩 된 재귀를 간단히 while 루프로 바꿀 수 있음을 제안합니다. 전반적인 알고리즘은 여전히 ​​개선의 여지가 있지만 적어도 재귀 문제는 해결됩니다.