C++ - le programme a cessé de fonctionner

Question

Le code que j'ai posté ci-dessous est censé fonctionner en récursivité (la fonction Sort()) jusqu'à 1kk fois. Le problème est le suivant: lorsque la fonction Sort() entre dans le numéro de boucle 43385, la console cesse de fonctionner et alerte: "Le programme a cessé de fonctionner". Est-ce un problème de mémoire? Si oui, où est la mauvaise partie du code? Salutations.

#include <iostream> 
#include <string> 

using namespace std; 
string a, b; 
int n=0,i=0,counter=0; 

int Sort(int i) 
{ 
    int x=0,y=0,tmp0=0; 
    char tmp1; 

    for(x=i;x<n;x++) { 
     if(a[x]==b[i]){ 
      tmp0=x; 
      tmp1=a[x]; 
      break; 
     } 
     else 
      continue; 
    } 
    for(y=tmp0;y>=i;y--) 
     y==i ? a[i]=tmp1 : a[y]=a[y-1]; 

    counter+=tmp0-i; 
    if(i==n-1) 
     return counter; 
    else 
     Sort(i+1); 
} 
int main() 
{ 
    cin >> n >> a >> b; 
    Sort(0); 
    return 0; 
} 

Answer 1

Peut-être un débordement de pile d'appel en raison d'une récursion trop profonde?

Answer 2

Le compteur est de type int mais il contient beaucoup de valeurs qui peuvent être plus grandes que int. peut-être essayer int64?

Answer 3

Vous pouvez coder en dur certains cas de test, comme n = 20, a = "xyz ...", b = "abc ...", et ajouter des instructions d'impression à votre fonction de tri pour suivre ce qui se passe. En outre, il peut être utile d'ajouter quelques commentaires pour clarifier le but des différentes boucles.

Answer 4

Pour ajouter au commentaire de iltal, vous pouvez imprimer des informations sur les chaînes a, b: a.size(), a.length(), a.capacity(), a.max_size()

Answer 5

Je ne suis pas sûr de savoir ce que ce code essaie de faire. Voici une révision, avec quelques instructions d'impression ajoutées, avec un générateur de chaîne aléatoire.

#include <iostream> 
#include <string> 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

using namespace std; 
string a, b; 
int n=0,i=0,counter=0; 

int Sort(int i) 
{ 
int x=0,y=0,tmp0=0; 
char tmp1; 

for(x=i;x<n;x++) { 
    if(a[x]==b[i]){ 
     tmp0=x; 
     tmp1=a[x]; 
    cout << "x = " << x << " set tmp0 to " << tmp0 << " and tmp1 to " << tmp1 << endl; 
     break; 
    } 
    else 
     continue; 
} 
for(y=tmp0;y>=i;y--) 
    y==i ? a[i]=tmp1 : a[y]=a[y-1]; 

counter+=tmp0-i; 
cout << " endof sort: a is " << a << endl; 
cout << "    b is " << b << endl; 
if(i==n-1) { 
    cout << "Returning counter " << counter << endl; 
    return counter; 
} else { 
    cout << "Running sort(" << i << " + 1)" << endl; 
    Sort(i+1); 
} 
} 
string randomStrGen(int length) { 
static string charset =  "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"; 
string result; 
result.resize(length); 

for (int i = 0; i < length; i++) 
    result[i] = charset[rand() % charset.length()]; 

return result; 
} 
int main() 
{ 
n = 50; 
srand(time(NULL)); 
string a0, b0; 
a0 = randomStrGen(n); 
a = a0; 
b0 = randomStrGen(n); 
b = b0; 
// cin >> n >> a >> b; 
cout << "Max string size is " << a.max_size() << endl; 
cout << "Calling sort" << endl 
    << " n is " << n << endl 
<< " a is " << a << endl 
<< " b is " << b << endl; 
Sort(0); 
cout << " endof program: a inital: " << a0 << endl; 
cout << "     a final: " << a << endl; 
cout << "     b inital: " << b0 << endl; 
cout << "     b final: " << b << endl; 
return 0; 
}