Segmentierungsfehler - Array außerhalb der Grenzen

Question

Ich habe einen einfachen Algorithmus geschrieben, so dass, wenn der Benutzer ein int N eingibt, ein N-mal-N-Gitter erstellt wird, in dem sich keine Duplikate in derselben Zeile oder Spalte befinden. Der Algorithmus arbeitet manchmal mit niedrigeren Zahlen, löst jedoch häufig einen Segmentierungsfehler aus. Der Fehler tritt in der Funktion noRowDuplicates in der Zeile auf, in der ein Element des Grid-Arrays festgelegt wird.

Ich bin mir nicht sicher, warum das passiert und würde jede Hilfe zu schätzen wissen. Danke im Voraus!

// 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

Ihr erster Anruf() zu füllen 0 Pass für seine Parameter, arrayPosition.

gridSize ist die Größe Ihrer Matrix/Array.

Wenn Sie die Logik in Ihrem fill() untersuchen, werden Sie feststellen, dass es sei denn, arrayPosition gleich oder größer ist als gridSize, wird ein rekursiver Aufruf fill() gemacht werden, mit arrayPosition entweder die gleiche ist, oder um 1 erhöht

Alle logischen Ausführungspfade bis fill(), wenn arrayPosition < gridSize, führen zu einem rekursiven Aufruf von fill().

Um Wörter, wenn zum Beispiel Ihr Array/Matrix zehntausend Werte hat, wird Ihr fill() versuchen, mindestens (und wahrscheinlich viel mehr als) zehntausend geschachtelte rekursive Aufrufe an sich selbst zu machen!

Dies wird nicht gut enden. Ihr Code trifft auf einen Segmentierungsfehler, wenn er von Ihrem Betriebssystem die maximale Menge an zugeordnetem Stapelspeicher durchbricht und Ihr Betriebssystem dem Prozess nicht mehr Stapelspeicherplatz zuweist.

Sie müssen Ihre Logik umgestalten, um diese Art der außer Kontrolle geratenen Rekursion zu vermeiden. Leider ist der Stapelspeicher nicht unendlich. Die gezeigte Logik ist in C++ grundsätzlich gebrochen. Sie können sich nicht darauf verlassen, dass der Compiler die Tail-Rekursion eliminiert und den Stack-Speicherplatz für jeden rekursiven Funktionsaufruf vermeidet.

Eine kurze Überprüfung schlägt vor, dass verschachtelte Rekursion trivial durch eine while Schleife ersetzt werden kann. Der Gesamtalgorithmus hätte noch etwas Raum für Verbesserungen, aber zumindest löst dies das Rekursionsproblem.