valeur maximale dans récursion

Question

J'ai ce devoir à la maison:

Soit P_i être l'élément de arr indice i. Nous disons un indice i est 'bien placé' s'il existe un indice j (j> = i) de telle sorte que la somme des éléments dans P_iP_i 1 ... P_j rendements de l'indice i . En d'autres termes, un index est "bien placé" si une séquence d'éléments commençant à cet index donne l'index lorsqu'il est additionné.

Nous définissons « longueur bien placée » d'un indice bien placé pour être j-i 1 - La longueur de la séquence que lorsque additionnées montre que est bien placé l'index. Il est possible qu'un index soit bien placé avec plus d'une seule séquence d'éléments. La «longueur bien placée» dans ce cas est la longueur maximale des différentes séquences définissant l'index comme «bien placé». La «longueur maximale bien placée» est le maximum entre la longueur de placement de tous les indices bien placés dans arr.

Si aucun index dans le tableau n'est bien placé, la longueur maximale bien placée est considérée comme nulle.

Voici le code que j'ai écrit (cela ne fonctionne pas):

int longestIndexHelper(int arr[], int i, int cur, int sum, int flag) 
{ 
    if((arr[i]==115)||(i<0)) 
     return 0; 
    if((sum==0)&&(flag==0)) 
     cur= i; 
    if((sum+arr[i]==cur)&&(arr[i]<=cur)) 
     return longestIndexHelper(arr, i+1, i, sum+arr[i], 1)+1; 
    else return 0; 
} 

int longestIndex(int arr[], int length) 
{ 
    int l, h; 
    if(length<=0) 
     return 0; 
    l= longestIndexHelper(arr, length-1, 0, 0, 0); 
    h= longestIndexHelper(arr, length, 0, 0, 0); 
    if(h>=l) 
     return longestIndex(arr, length-1); 
    else 
     return longestIndex(arr, length-2); 
} 

J'ai essayé de comprendre pourquoi il ne retourne pas la valeur maximale, je suppose que le IF et ELSE doivent définir quelque chose d'autre à faire ... Je ne peux utiliser que ces deux fonctions. merci!

Answer 1

Supposons que votre fonction longestIndex trouve la «longueur maximale bien placée» pour un paramètre length donné. Puis il le laisse tomber (h et l ne sont pas stockés ou retournés n'importe où, sont-ils?), Et s'appelle lui-même avec une diminution length. Donc, la fonction retournera toujours le résultat de longestIndex(arr, 0) ou longestIndex(arr, -1) qui sera toujours 0.

EDIT: et la fonction longestIndexHelper ne peut retourner que 0 aussi.

Answer 2

Le problème semble être que vous devez implémenter deux "boucles" via la récursivité; l'une est une boucle commençant à un index donné et additionnant les valeurs au fur et à mesure, gardant une trace de la longueur maximale bien placée pour cet index de départ. L'autre est une boucle essayant chaque index de départ possible. Je vois que votre fonction d'aide fait le premier. Il semble que vous ayez l'intention que la fonction appelée fasse la dernière, mais elle n'a aucun mécanisme pour garder trace du maximum trouvé jusqu'ici ou de l'index à vérifier, séparé de la longueur du tableau d'entrée.Pour ce faire, vous voudrez peut-être créer une autre fonction d'aide pour recurrencer tous les index de départ possibles. Bien que j'aborder ce en élargissant la fonction d'aide existante pour le faire aussi, quelque chose comme:

int _helper(int arr[], int len, int start, int cur, int sum, int max) 
{ 
    if (start >= len) { 
     /* game over, thanks for playing */ 
     return max; 
    } else if (cur >= len) { 
     /* try another starting index */ 
     return _helper(arr, len, start + 1, start + 1, 0, max); 
    } else if (sum + arr[cur] == start && max < cur - start + 1) { 
     /* found a longer well placed length */ 
     return _helper(arr, len, start, cur + 1, sum + arr[cur], cur - start + 1); 
    } else { 
     /* bzzzt. try a longer length at this starting index */ 
     return _helper(arr, len, start, cur + 1, sum + arr[cur], max); 
    } 
} 

int max_well_placed_length(int arr[], int len) 
{ 
    return _helper(arr, len, 0, 0, 0, 0); 
} 

#include <stdio.h> 

int main(int argc, char **argv) { 
    int arr[100]; 
    int len = 0; 
    if (argc > 100) return 1; 

    while (--argc) sscanf(*++argv, "%d", &arr[len++]); 

    printf("max well placed length: %d\n", max_well_placed_length(arr, len)); 
    return 0; 
}