Trouver des indices de tableau pour l'algorithme "diviser pour régner"?

Question

Je dois implémenter un algorithme de division et de conquête en C++ pour une fonction max, qui renvoie la valeur maximale dans un tableau. Je comprends l'algorithme et ai déjà conçu la fonction, mais je rencontre des problèmes avec les indices de tableau.

En pseudocode, voici ma fonction:

def max(array, startIndex, endIndex) 

    // if there is only one element, return it 
    if startIdx = endIdx 
     return array[startIdx]; 

    leftHigh = max(array, startIdx, endIdx/2); 
    rightHigh = max(array, endIdx/2 + 1, endIdx); 

    return maximum of leftHigh and rightHigh; 

Cependant, je rencontre un problème avec ces valeurs pour les paramètres d'appel récursives. Le paragraphe suivant montre ce que j'ai trouvé lorsque j'ai mentalement traversé l'algorithme:

Le cas le plus simple est un tableau de 4 éléments. Le premier appel à max prendra les paramètres d'index 0, 3 et effectuera les appels avec les paramètres 0, 1 et 2, 3. Le premier appel récursif se traduira par des appels avec 0, 0 et 1, 1 qui se terminera correctement. Cependant, le deuxième appel récursif se traduira par des appels avec 2, 1 et 2, 3. La première résulte finalement de dépasser les limites du tableau et la seconde résulte en une boucle infinie puisque ces paramètres ont déjà été utilisés.

J'ai essayé de jouer avec, par exemple en utilisant (startIdx, endIdx/2 -1) pour les premières limites et (endIdx/2, endIdx) pour les secondes limites, et cela corrige la deuxième branche des appels récursifs, mais endommage le premier.

Existe-t-il un moyen de trouver ces indices résultant du comportement correct? J'apprécie l'aide.

Answer 1

Il devrait être

leftHigh = max(array, startIdx, (startIdx + endIdx)/2); 
rightHigh = max(array, (startIdx + endIdx)/2 + 1, endIdx); 

Answer 2

solution proposée en Python:

from math import floor, ceil 
def maximum(arr, left, right): 
    if left >= right: 
     if left < len(arr): 
      return arr[left] 
     else: 
      return arr[right] 
    else: 
     left = maximum(arr, left, int((left+right)/2)) # pay attention to the midpoint! 
     right = maximum(arr, int((left+right)/2), right) 
     return max(left, right) 

print maximum([1,8,2,9,3,15,5,3,2], 0, 8) 

SORTIE

15 

Answer 3

Si je vous donne deux chiffres: < c, mais alors comment vous caractérisez les nombres entre le deux. I.E, que pouvons-nous dire à propos de b quand un < b < c?

a < b < c 
0 < b - a < c - a 

Vous choisissez b = c/2. Ce que nous pouvons voir que les critères ci-dessus rencontre dans certains cas:

   b = c/2 
and    b > a 
then   c/2 > a 

Ainsi, nous pouvons voir que votre méthode fonctionne aussi longtemps que> c/2. Dans votre cas a = startIdx et c = endIdx, de sorte que votre algorithme ne fonctionne que lorsque startIdx < endIdx/2.

cette recherche soigneusement Tenir compte:

a < b < c 
0 < b - a < c - a (subtract a from all parts) 

Si b est à mi-chemin entre un et c, alors quelle est sa valeur? Dans ce cas, comment (b - a) se rapporte-t-il à (c - a)?