Diviser et conquérir des algorithmes pour trouver le maximum d'élément d'un tableau

Je suis en train d'essayer de comprendre comment les algorithmes suivants œuvres.

#include <iostream>
using namespace std;
int maxsimum(int a[], int l, int r) {
    if (l == r)  
        return a[l];
    int m = (l+r)/2;
    int u = maxsimum(a,l,m);
    int v = maxsimum(a,m+1,r);
    return u>v?u:v;    
}

int main() {
    int a[] = {34,23,45,56,30,31,57,33,55,10};
    int n = sizeof(a)/sizeof(int);
    cout << maxsimum(a,0,n) << endl;         
    return 0;
}

Tout d'abord, ce qui m'intéresse, c'est que, en dépit de l'algorithme fonctionne correctement, il est mystérieux pour moi la façon dont il trouve l'élément maximum. Je vais vous montrer comment j'ai compris de cet algorithme:

Étape 1: nous dire que dans le cas d'un tableau, l=0 et r=10, il vérifie if (l>r) qui ne détiennent pas de cours donc il calcule m=(0+10)/2;. Puis effectuez de nouveau la procédure pour les nouvelles limites. La première paire est (0,5), la deuxième (6,10) et après l'opération finale, il compare deux valeurs renvoyées et enfin retourne l'élément maximal entre eux.

N'cet algorithme travaille toujours? À chaque itération, il ne fait pas de comparaison, seule la dernière étape. Comment peut-il déterminer l'élément maximum à chaque récursive itération? Il vérifie que ce. Par exemple: prendre la paire(0,5), est (0 plus de 5)? Non, afin de le répéter encore et diviser ces limites en deux afin d'obtenir de nouvelles valeur moyenne m1=(0+5)/2, puis à nouveau à nouveau et revenir à l'élément, mais pas le maximum. Aussi pour la deuxième subarray on peut dire la même chose.

Quelle est l'idée principale de cet algorithme?

  • oui je sais que c'est récursive maximale de l'élément de recherche, j'ai besoin que voulez comprendre comment il trouve le maximum j'ai essayé de faire un peu de travail sur le papier, mais pas de résultat
  • Votre question est complètement inintelligible. J'ai essayé de l'améliorer mais je ne sais pas vraiment par où commencer. Veuillez utiliser les paragraphes et une mise en forme appropriée.
  • Konrad Rudolph ma question est est-il exact que la comparaison est écrit sur la dernière ligne?
  • Pourquoi dois-je continuer à voir de cet algorithme sur ce site? Est-ce un apprentissage en commun de l'exercice? Il ne semble pas plus vite qu'un linéaire de recherche...
  • Qu'est-ce que la complexité asymptotique de cet algorithme ?
  • Asymtotic de la complexité est la même, mais la constante multiplicateur est au moins deux fois plus grande, de sorte que c'est au moins deux fois plus lent.
  • C'est le grand O(n). J'ai pensé à elle.

InformationsquelleAutor dato datuashvili | 2011-09-06
  1. 4

    Votre confusion est compréhensible: l'algorithme comme l'écrit contient un certain nombre de bugs. Il accède à la mémoire au-delà de la fin de l'un, qui est très, très mauvais. Aussi, le test de savoir si une série ne contient qu'un seul élément est incorrect. Si non traitée, ce qui conduit à un débordement de pile.

    La façon dont le maxsimum fonction est appelée suggère que la limite inférieure est incluse dans la gamme, mais la limite supérieure n'est pas. a[0] est valide, mais a[n] accède à la mémoire au-delà de la fin d'une. Lorsque le fractionnement de la gamme, nous voulons la première partie à courir à partir de l à, mais pas y compris m, et la deuxième partie pour commencer à m et mais pas la r. En d'autres termes: le "exclusif" limite supérieure de la première partie est égale à la "inclusive" limite inférieure de la deuxième partie. Le premier appel interne à maxsimum est correct. Le deuxième appel interne devrait être:

    int v=maxsimum(a,m,r);

    Ce qui nous laisse avec le problème de la détection d'une gamme de longueur 1. En fait, l'algorithme de recherche d'un vide gamme. Le bon test est de regarder la différence entre la partie supérieure et la limite inférieure:

    if (r-l == 1) return a[l];

    La fonction complète est la suivante:

    int maxsimum(int a[],int l,int r){
   if (r-l==1)  return a[l];
   int m=(l+r)/2;
   int u=maxsimum(a,l,m);
   int v=maxsimum(a,m,r);
   return u>v?u:v;    
}

    Maintenant que nous avons un programme correct, l'explication de la façon dont cela fonctionne est simple:

    1. Si la plage contient un seul élément, alors cet élément est le maximum.
    2. Si la plage contient plus d'un élément, nous avons divisé en deux parties. Nous appelons la fonction de manière récursive pour calculer la valeur maximale de chaque partie. Le maximum de ces deux valeurs est la valeur maximale de l'ensemble de la gamme.
    • Qu'est-ce que la complexité asymptotique de cet algorithme ?
    • Il O(n) T(n) = 2T(n/2) + 1
    InformationsquelleAutor Jeffrey Sax
  2. 3

    L'idée principale est que si l'on divise le tableau en 2 sous-tableaux, puis le maximum doit être dans la gauche ou la partie droite de la matrice; il n'y a pas d'autre possibilité.

    Nous avons donc trouver le maximum dans la partie gauche, on trouve le maximum dans la partie droite et le maximum global sera évidemment le maximum entre les deux maximum, c'est ce qui est retourné par la dernière ligne de la maxsimum fonction.

    • merci pour la réponse, je sais ce que je ne suis pas de demander à propos de ce que fait cet algorithme ne s'il vous plaît, je me demande comment il détermine dans chaque subarray, comment il trouve maxsimum, comparaison est à finall étape,de sorte qu'il me confond
    • Qu'est-ce que c'est de la course du temps, ou asymptotique de la complexité de cet algorithme?
    InformationsquelleAutor Simone
  3. 2

    Votre erreur est ici:

    À chaque itération, il ne fait pas de comparaison, seule la dernière étape.

    Ce qui est faux. En fait, il fait une comparaison dans chaque étape de la récursion (sauf dans la base de cas, c'est à dire la taille de la matrice est 1).

    • ok merci @Konrad Rudolph merci pour la réponse je vais essayer de comprendre plus profondément
    InformationsquelleAutor Konrad Rudolph
  4. 1

    Permettez-moi de commenter le maximum de la partie du code pour vous, et essayez de ne pas ajouter de la confusion:

    if (l==r)  return a[l]; //trivial case, if there is only one value in the array return it
int m=(l+r)/2; //find value halfway into the array
int u=maxsimum(a,l,m); //find the maximum value for the lower part of the array
int v=maxsimum(a,m+1,r); //find the maximum value for the top part of the array
return u>v?u:v; //return the highest value of them.

    Ainsi, le tableau 0..10 est divisée en 0..5 et 6..10 et est passé dans la même fonction. Seulement quand il n'y a qu'une seule valeur à la récursivité se termine et que la seule valeur est transmise à leurs fonctions appelées. Puis, dans la deuxième plus faible nombre de cas, comme la valeur de a[0] et[1] il fera le premier des comparaisons. Les résultats de ces va être transmis au plus les cas jusqu'à ce qu'il quitte la fonction pour la dernière fois de retour avec la plus grande valeur de tous les cas.

    Je l'espère, a été en mesure de préciser un peu pour vous.

    InformationsquelleAutor daramarak
  5. 1

    Erreur dans main() fonction de test tableau de 10 éléments, devrait être:

    cout << maxsimum(a,0,n-1) << endl;
    InformationsquelleAutor alex
  6. 1

    Cette réponse pourrait être trop tard, mais il peut être utile à quelqu'un pour saisir la récursivité des appels, j'ai modifié le code ci-dessus à tracer les appels de fonction.
    Après avoir vu la sortie, il est facile de voir comment un récursif de l'arbre est faite.

    #include <iostream>
using namespace std;
int maxsimum(int a[], int l, int r) {
if (l == r)  
    return a[l];
int m = (l+r)/2;

cout<<"values gonna get computed in 1st recursive call"<< l<<" "<< m<<"\n";
int u = maxsimum(a,l,m);

cout<<"value of u "<<u<<"\n";

cout<<"value gonna get computed in 2nd recursion  call "<<m+1 <<" "<<r<<"\n";
int v = maxsimum(a,m+1,r);

cout<<"value of v : "<<v<<"\n";
cout<<"current u value :"<<u <<"current v value "<<v <<"\n";

return u>v?u:v;    
}

int main() {
int a[] = {5,6,7,8,9};
int n = sizeof(a)/sizeof(int);
cout << maxsimum(a,0,n-1) << endl;         
return 0;
}

    Ici est la récurrence de l'arbre pour le programme ci-dessus, l'arbre va d'abord vers la gauche je.e pour la première récursive de l'instruction, puis chaque appel renvoie sa valeur de base, le retour à la condition permet de s'assurer au maximum de l'élément est sélectionné dans chacun des appels.

                     (9)  
                (0,4)
              /      \
           7 /        
        (0,2)          (3,4)
         /  \          /    \
       6/          8/      
       (0,1)  (2,2)  (3,3)     (4,4) 
        / \      
      5/   
     (0,0) (1,1)
    InformationsquelleAutor Kishy Nivas