Matematicamente.it

Salve, sto cominciando a trattare alcuni esercizi che hanno come argomento l'utilizzo del metodo ricorsivo per essere svolti. Prendendo come esempio quelli del calcolo del fattoriale e della serie di Fibonacci, ho capito come svolgere altri simili, ma non capisco come usare il metodo ricorsivo per altre tipologia di esercizi dove non riesco a trovare un possibile caso base.
Uno degli esercizi è quello sul "percorso più redditizio":
ho una matrice di numeri che rappresentano il guadagno; quindi io dovrei cercare di raggiungere,partendo dalla posizione (0,0), la posizione(i,j) in basso a destra cercando di trovare il percorso con più guadagno e muovendosi soltanto in giù e a destra. Il codice scritto fin'ora è questo:
#include <stdio.h>
#define ROWS 4
#define COLUMNS 4

void printArray(int a[][COLUMNS]);
//int guadagno(int a[][COLUMNS], int i, int j);
//int max(int a, int b);

int main(void) {
int a[][COLUMNS] = {{1,9,5,4}, {7,6,7,3}, {8,5,4,8},{5,6,4,8}};
printArray(a);
//printf("malloppo = %d\n", guadagno(a, ROWS-1, COLUMNS-1));
}

//int guadagno(int a[][COLUMNS], int i, int j) {}




//int max(int a, int b) {}

void printArray(int a[][COLUMNS]) {
for (size_t i=0; i<ROWS; i++) {
for (size_t j=0; j<COLUMNS; j++)
printf("%d ", a[i][j]);
printf("\n");
}
}

Dovrei sviluppare la funzione ''guadagno'' con il metodo ricorsivo e con la funzione max per scegliere di volta in volta il numero più grande. Vorrei capire bene come usare al meglio il metodo ricorsivo più in generale anche per svolgere altri esercizi. Grazie per la disponibilità.

il caso base in questo caso sarebbe non fare nessun passo, quindi il malloppo dovrebbe coincidere con il numero nella prima casella(0,0) giusto?

Prima di tutto pensa a cosa vuoi calcolare globalmente in funzione degli elementi a disposizione. Qui l'output dev'essere la somma dei guadagni dei singoli nodi di un qualche cammino.
Ora, relativamente ad un generico elemento (nel nostro caso una cella (i,j)), esprimi quanto detto come composizione dell'apporto di quest'ultimo con un ipotetico risultato parziale. Qui il contributo di (i,j) alla somma è a[i][j]:

Codice:

guadagno = a[i][j] + guadagno_parziale

Il risultato parziale sarà il guadagno dato dal proseguimento del cammino: da (i,j) si può andare, tenendo opportunamente in considerazione gli estremi della matrice, in (i, j+1) oppure in (i+1, j).
Scelgo l'opzione che mi da il guadagno maggiore, supponendo di saperlo calcolare:

Codice:

guadagno_parziale = max(guadagno(a, i, j+1), guadagno(a, i+1, j))

Quindi il passo ricorsivo è:

Codice:

guadagno = a[i][j] + max(guadagno(a, i, j+1), guadagno(a, i+1, j))

Per il passo base pensa a quando il processo deve avere fine, ovvero quando non esiste più un risultato parziale da calcolare. Qui è in corrispondenza della cella (ROWS-1, COLUMNS-1).

Codice:

if(i == ROWS - 1 && j == COLUMNS - 1)
   guadagno = a[i][j] // guadagno_parziale = 0


Mettendo assieme i pezzi:

Codice:

guadagno(a, i, j)
{
   if(i == ROWS - 1 && j == COLUMNS - 1)
      return a[i][j]
   else
      return a[i][j] + max(guadagno(a, i, j+1), guadagno(a, i+1, j))
}


Ciao!

Ti ringrazio per la spiegazione ^^!

Ho scritto il codice basandomi su quello detto sopra:
#include <stdio.h>
#define ROWS 4
#define COLUMNS 4

void printArray(int a[][COLUMNS]);
int guadagno(int a[][COLUMNS], int i, int j);
int max(int a, int b);

int main(void) {
int a[][COLUMNS] = {{1,9,5,4}, {7,6,7,3}, {8,5,4,8},{5,6,4,8}};
printArray(a);
printf("malloppo = %d\n", guadagno(a, ROWS-1, COLUMNS-1));
}

int guadagno(int a[][COLUMNS], int i, int j) {
if( i == 0 && j == 0) {return a[i][j];}
else{
if (i==0) {return (guadagno(a, i,j-1) + a[i][j]);}
else{
if (j==0) {return (guadagno(a, i-1,j) + a[i][j]);}
return a[i][j] + max(guadagno(a, i, j-1), guadagno(a, i-1, j));}

}
}



int max(int a, int b) {
return (a>b) ? a : b;
}

void printArray(int a[][COLUMNS]) {
for (size_t i=0; i<ROWS; i++) {
for (size_t j=0; j<COLUMNS; j++)
printf("%d ", a[i][j]);
printf("\n");
}
}

Se ho capito bene: la base ricorsiva si ha quando non si ha un guadagno precedente, cioè appunto i e j = 0, altrimenti il guadagno sarebbe la posizione attuale a[i][j] + quella precedente con appunto i-1 O j-1.
PS: come faccio a cambiare la formattazione del codice per renderlo meglio?

O in modo più conciso:

Codice:

#include <stdio.h>

#define R 4
#define C 4

int max(int a, int b)
{
    return (a > b) ? a : b;
}

int fun(int m[R][C], int i, int j)
{
    switch((i == R - 1) + (j == C - 1))
    {
        case 0: return m[i][j] + max(fun(m, i + 1, j), fun(m, i, j + 1));
        case 1: return m[i][j] + fun(m, i + (i != R - 1), j + (j != C - 1));
        case 2: return m[i][j];
    }
}

int main()
{
    int m[R][C] = {{1, 9, 5, 4},
                   {7, 6, 7, 3},
                   {8, 5, 4, 8},
                   {5, 6, 4, 8}};
    printf("%d", fun(m, 0, 0));
}

Per inserire il codice sul forum utilizza il tasto "Code" presente nell'editor completo.

ah capisco. Insomma dovrò sbatterci più la testa anche per creare codici diversi anche per avere gli stessi risultati. Grazie ancora!