J'essaie d'écrire une méthode récursive qui me donne les plus grosses paires d'entiers (voisins) dans un tableau. Cela fonctionne parfaitement, mais uniquement pour la première exécution, car je ne peux pas réinitialiser mon static int maxSum; "compteur" que j'utilise pour vérifier si la somme actuelle est plus grande que la plus grande somme des exécutions précédentes. peut-être pouvez-vous me donner un indice, c'est la première fois que je travaille avec des compteurs statiques dans une récursivité
static int maxSum = 0;
private static int getMaxPairSum(int[] workArray, int start, int end) {
while(start < end){
if (workArray[start] + workArray[start+1] > maxSum){
maxSum = workArray[start] + workArray[start+1];
return getMaxPairSum(workArray,start +1,end);
}
else return getMaxPairSum(workArray,start +1,end);
}
return maxSum;
}
3 Réponses :
Une manière très simple de faire cela pourrait être:
maxSum à la variable maxSum Ce serait comme ceci:
while(start < end){
if (workArray[start] + workArray[start+1] > maxSum){
maxSum = workArray[start] + workArray[start+1];
return getMaxPairSum(workArray,start +1,end);
}
else return getMaxPairSum(workArray,start +1,end);
}
int tempMaxSum = maxSum;
maxSum = 0;
return tempMaxSum;
J'espère que cela vous a aidé!
Merci pour votre aide :) et cela a parfaitement fonctionné avec tempMaxSum, même si ce n'était pas exactement vers lequel je me dirigeais :)
Génial! Heureux que vous ayez trouvé un autre bon moyen! J'ai essayé de faire le mien pour que vous n'ayez pas à changer trop de code, mais vous avez certainement trouvé un meilleur moyen! De plus, si vous voulez faire en sorte que stackoverflow sache que cette question n'a plus besoin de réponses, vous pouvez définir comme réponse l'une des 3 réponses de cette question, (ou les voter)! :)
J'ai l'impression que vous pensez encore trop dans un état d'esprit de programmation itérative. En récursivité, vous ne devriez pas vraiment avoir besoin d’une variable globale pour suivre les changements. Au lieu de cela, les changements devraient à la place se propager soit vers le haut (pensée toujours très itérative), soit vers le bas (récursivité appropriée!) Votre pile de récursivité, l'opération (dans ce cas une comparaison) étant effectuée à chaque appel de fonction dans cette pile.
Il devrait être le cas que la transitivité de l'opérateur supérieur à s'applique ici, donc le max sera le plus grand quel que soit le moment où cela se produit dans la liste, donc peu importe quand nous le trouvons. Essayez de trouver des exemples concrets et de parcourir quelques itérations de votre méthode si cela ne vous semble pas clair.
Un exemple de son passage dans votre pile de récursivité serait d'ajouter un nouvel argument à votre méthode, tel que «maxSum» et de le transmettre à chaque appel, en gardant une trace du max à chaque appel. En revenant de cela, vous vous sentirez toujours un peu "off", car vous auriez la valeur de votre résultat une fois que vous atteignez la fin de la liste, mais vous auriez toujours besoin de le renvoyer à travers tous les appels récursifs que vous avez passés au jusqu'à ce qu'il revienne au premier appel.
L'approche "la plus récursive", ici, serait de laisser votre méthode fonctionner avec une valeur qui n'a pas encore été déterminée mais dont elle sait qu'elle sera déterminée à l'avenir, et de le faire jusqu'à ce qu'elle atteigne le cas final . Une fois arrivé à la fin, il aura obtenu une valeur concrète, ce qui permet de déterminer maintenant une valeur indéterminée pour l'appel précédent, ce qui permet de déterminer une valeur indéterminée pour l'appel avant cela, etc., jusqu'au premier appel.
Ici, la comparaison serait Math.max (currentSum, nextSum), où currentSum = workArray [i] + workArray [i + 1] et nextSum est la valeur renvoyée par le prochain appel à getMaxPairSum, qui ne sera pas réellement être déterminé jusqu'à ce que vous arriviez à la fin du tableau (votre cas final pour la récursivité) qui renverra une valeur à l'appel avant lui, qui en retourne une valeur à l'appel avant lui, qui renvoie une valeur à l'appel avant lui , et ainsi de suite jusqu'à ce que vous reveniez au premier appel et que vous ayez ainsi votre valeur finale.
Pour une visualisation basée sur des structures de données, cela signifie que les calculs se propageront vers le bas de la pile d'appels de fonction récursive jusqu'au tout premier appel, qui est l'élément le plus bas de la pile.
Merci pour votre aide! J'ai décidé d'écrire un nouveau code, il fonctionne parfaitement et est récursif: D
private static int getMaxPairSum (int [] workArray, int start, int end) {
if (start==end)
return 0;
return Math.max((workArray[start] + workArray[start+1]), getMaxPairSum(workArray,start+1,end));
p>
Quelle est la variable que vous souhaitez réinitialiser?
maxSum?oui maxSum est la variable que je veux réinitialiser après le retour de la guerre de résultat