Solución de problemas de forma recursiva en C

Question

Nuestro profesor nos dio la siguiente asignación:

A "correct" series is one in which the sum of its members equals to the index of its first member.

Se supone que el programa para encontrar la longitud de la serie más larga "correcto" dentro de una serie de n números. Por ejemplo, si la serie de entrada sería arr[4]={1, 1, 0, 0} , la salida (serie "correcta" más larga) sería 3
arr[0]=1. 0!=1 por lo tanto, la serie más larga aquí es 0.
arr[1]=1,and 1=1. pero los siguientes miembros también suman hasta 1 como se muestra a continuación:
1=arr[1]+arr[2]+arr[3] = 1+ 0 + 0, por lo tanto, la serie más larga aquí es 3.

La salida en este ejemplo es 3.

Esto es lo que tengo hasta ahora:

int solve(int arr[], int index, int length,int sum_so_far) 
{ 
    int maxwith,maxwithout; 

    if(index==length) 
     return 0; 

    maxwith = 1+ solve(arr,index+1,length,sum_so_far+arr[index]); 
    maxwithout = solve(arr,index+1,length,arr[index+1]); 

    if(sum_so_far+arr[index]==index) 
     if(maxwith>maxwithout) 
      return maxwith; 

    return maxwithout; 

    return 0; 
} 



int longestIndex(int arr[], int index,int length) 
{ 
    return solve(arr,0,length,0); 
} 

¿Qué estoy haciendo mal aquí?

No se supone que tengamos que realizar bucles en esta tarea.

Answer 1

Me parece que el problema está aquí:

if(sum_so_far+arr[index]==index) 

que está comparando la suma hasta el momento con el índice actual, pero se debe comparar con el primer índice de la serie. Me parece que sería mejor si comenzases con el último elemento de arr hacia el primero, en lugar de ir en el orden natural. De esta forma, comienzas a sumar elementos hasta que la suma sea igual al índice actual.

Answer 2

Primero, escriba una función que pruebe una serie del índice inicial dado y la longitud dada para la condición "suma de sus miembros". Luego, escriba una segunda función que busque las series más largas dentro de su matriz donde solo se da el índice inicial (debe hacerlo sobre la longitud de la sub-serie en orden decreciente); esta función puede llamar al primero. Por último, escriba una tercera función que recorre todos los índices iniciales, llamando a la función número dos.

Oh, espera, no hay recursividad necesita más, por lo que una gran cantidad de cerebro-torsión se ha ido ... :-)

Answer 3

Hmm, hay varios problemas con este programa.

Más obvio, "return maxwithout; return 0;" debería dar un error de compilación: no hay forma de llegar a la última declaración de devolución.

En segundo lugar, está recurriendo para resolver en la ruta "maxwith" hasta llegar al final de la matriz. Entonces vas a volver a recurse en maxwithout, golpeándolo por primera vez con index = 4. No creo que esto vaya a funcionar.

Francamente, no creo que este problema realmente requiera recurrencia. La solución más natural sería un bucle anidado:

for (int start=0;start<length;++start) 
{ 
    for (int end=start;end<length;++end) 
    { 
    // calculate the sum of arr[start]->arr[end] and compare to start 
    } 
} 

O algo por el estilo.

¿El problema requería resolverlo con recurrencia o era solo su primera idea en una buena solución?

Editar

bien, así que usted tiene que utilizar la recursividad. Supongo que el objetivo de la lección es aprender a usar la recursión, no necesariamente para resolver el problema de la manera más natural o eficiente. (Personalmente, creo que la maestra debería haber surgido un problema donde la recursión era una solución natural, pero creo que no estamos aquí para criticar al maestro hoy.)

No quiero hacer la tarea para usted, pero le daré una pista. Puede usar la recursividad para simular un ciclo al poner la condición de corte al comienzo de la función y al poner la llamada recursiva al final de la función con un parámetro +1. Es decir, en lugar de escribir

for (int x=0;x<10;++x) { ... whatever ...} 

puede escribir

void forx(int x) 
{ 
    if (x>=10) 
    return; 
    ... whatever ... 
    forx(x+1); 
} 

Así que en este caso me gustaría hacer algo como:

void endloop(int start, int end) 
{ 
    if (end>=arrayLength) 
    return; 
    ... work on running total ... 
    endloop(start, end+1); 
} 

void startloop(int start) 
{ 
    if (start>=arrayLength) 
    return; 
    endloop(start, start); 
} 
int main() 
{ 
    ... setup ... 
    startloop(0); 
    ... output ... 
} 

listas de parámetros no son necesariamente completa. Como digo, no quiero hacer tu tarea por ti, solo darte una pista para comenzar.