1
votes

Divide et impera somme des éléments d'un bug de tableau

J'ai écrit la fonction suivante pour calculer la somme de tous les éléments d'un vecteur en utilisant la méthode divide et impera

int Sum(std::vector<int> v, int left, int right)
{
int mid = (left + right) / 2;

if (left >= right)
    return v[mid];
else
    return Sum(v, left, mid - 1) + Sum(v, mid + 1, right);
}

//in main:
vector <int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

cout << Sum(v, 0, v.size() - 1);

Cependant, dans l'exemple donné, il en produit 37 au lieu de 55. Je suis allé à travers avec un débogueur et il semble ignorer certains nombres. J'ai essayé de changer left> = right en left> right et cela me donne toujours une mauvaise réponse (56) même si je pense que cela devrait être left => right logiquement.

Qu'est-ce qui ne va pas dans le code?

c++ recursion divide-and-conquer

3 commentaires

La prochaine fois, veuillez publier votre code sous la forme d'un exemple minimal reproductible , comme cet exemple . Il manque des en-têtes include à votre code et nous ne savons pas si d'autres éléments pertinents sont manquants dans main . Si vous laissez à quelqu'un le soin de combler ces lacunes, il est possible que le code rempli ne corresponde pas à ce que vous compilez et exécutez.

Sum (v, left, mid - 1) + Sum (v, mid, right); et cela fonctionne dans O (n ^ 2) car vous copiez le vecteur, passez it by const reference: int Sum (const std :: vector & v, int left, int right)

Il semble qu'il soit temps d'apprendre à utiliser un débogueur pour parcourir votre instruction de code par instruction tout en surveillant les variables et leurs valeurs. Il est également utile de noter des notes lors du débogage sur une feuille de papier.

3 Réponses :

2
votes

Problème principal: la récursivité exclut mid des deux sous-sommes.

Problème secondaire: il peut arriver que gauche> droite (bien qu'avec une entrée initiale raisonnable, au pire gauche == droite + 1 ). Dans ce cas, vous voulez renvoyer 0.

Alors peut-être

if ( left > right ) 
   return 0;
else
   return Sum(v, left, mid-1) + v[mid] + Sum(v, mid+1, right);

0 commentaires

0
votes

Le problème est ici,

if (left >= right)
    return v[left]; // v[mid] also helps.

return Sum(v, left, mid) + Sum(v, mid + 1, right);

Il vous manque pour ajouter v [mid] . Alors changez-le,

return Sum(v, left, mid - 1) + Sum(v, mid + 1, right);

3 commentaires

Qu'avez-vous changé exactement et pourquoi ce changement résoudra-t-il le problème? Veuillez expliquer et ne pas simplement afficher du code qui encourage la programmation culte du fret . Veuillez également actualiser comment rédiger de bonnes réponses .

return Sum (v, left, mid - 1) + v [mid] + Sum (v, mid + 1, right); Celui-ci renvoie 70 (trop). Les deux autres fonctionnent bien, merci.

espérons, la réponse est maintenant ok.

0
votes

Sum devrait être comme ceci:

std::vector<int> v(100'000, 1);  // digit separator comes since C++14
Sum(v, 0, v.size() - 1);

Dans votre version vous copiez également le vecteur pendant la récursivité, essayez d'appeler votre fonction comme ceci:

XXX

et vous verrez combien de temps cela prend

0 commentaires