Esercizio ricorsione

[giuliomontenero]

Scrivere un metodo ricorsivo che, dato un array bidimensionale a di interi, restituisce
la somma degli elementi di a.
non riesco a farlo funzionare

#include<iostream>
#include<cassert>
using namespace std;
int sum_matrix(int [5][3],int,int);
int main()
{
    int i=5;
    int j=3;
    int a[5][3]={{1,2,3},{1,4,5},{5,2,3},{1,1,1},{0,9,1}};
    int somma;
    somma=sum_matrix(a,i,j);
    cout<<somma<<endl;
return 0;
}
int sum_matrix(int a[5][3],int i,int j)
{
    assert(i>0 && j>0);
    if(i==1 && j==1)return a[0][0];
    if(i==1)return a[0][j-1]+sum_matrix(a,i,j-1);
    else if(j==1)return a[i-1][0]+sum_matrix(a,i-1,j);
    else return a[i-1][j-1]+sum_matrix(a,i,j-1);
}

[garnak.olegovitc1]

Salve maschulillo,
se ho capito bene, tu vuoi sommare tutti gli elementi dell'array?
Cordiali saluti

[giuliomontenero]

si
la funzione deve restituire la somma di tutti gli elementi dell'array bidimensionale a

[garnak.olegovitc1]

Salve maschulillo,
premetto che io non programmo in C++ ma in C quindi alcune funzione e tipi di dati del C++ non li conosco,però potrei suggerirti di fare la somma per righe, o per colonne, cioè ricavarti le somme degli elementi di ogni riga, o di ogni colona, dell'array, magari le fai stampare per vedere se le somme sono giuste, e dopo sommi tutte queste somme ottenendo la somma che tu vuoi.
Cordiali saluti

P.S.=Scusami per il gioco di parole!

[giuliomontenero]

ho provato credo come tu abbia detto
ma non mi viene lo compila ma non lo esegue
prova a darci un'occhiata e fammi sapere dov'è che sbaglio

#include<iostream>
using namespace std;
int somma_riga(int [5][3],int ,int );
int somma_elementi(int [5][3],int ,int );
int main()
{
    int i=5;
    int j=3;
    int a[5][3]={{1,2,4},{5,8,0},{0,1,0},{1,3,3},{5,5,5}};
    somma_elementi(a,i,j);
return 0;
}
int somma_riga(int a[5][3],int i,int j)
{
    return a[i][j-1]+somma_riga(a,i,j-1);
}
int somma_elementi(int a[5][3],int i,int j)
{
    int somma=0;
    for(int r=0;r<i;r++)
    somma+=somma_riga(a,r,j);
cout<<somma<<endl;
}

[apatriarca]

Fare la somma su ogni riga è certamente la soluzione migliore per quanto riguarda l'accesso alla memoria, ma non è certo la migliore se l'idea è quella di sommare tutti gli elementi della matrice in modo ricorsivo (in effetti la tua soluzione non è completamente ricorsiva ma un misto tra iterativa e ricorsiva). È infatti più semplice sfruttare l'identità:
\[ \sum_{i=0}^{m-1} \sum_{j=0}^{n-1} a_{ij} = \sum_{i=0}^{\lceil m/2 \rceil -1} \sum_{j=0}^{\lceil n/2 \rceil - 1} a_{ij} + \sum_{i=0}^{\lceil m/2 \rceil -1} \sum_{j=\lceil n/2 \rceil}^{n-1} a_{ij} + \sum_{i=\lceil m/2 \rceil}^{m-1} \sum_{j=0}^{\lceil n/2 \rceil - 1} a_{ij} + \sum_{i=\lceil m/2 \rceil}^{m-1} \sum_{j=\lceil n/2 \rceil}^{n-1} a_{ij}, \]
dove \( A = ( a_{ij} )_{0 \le i < m, 0 \le j < n} \) è la matrice della quale si vuole calcolare la somma degli elementi. Definendo quindi la funzione
\[ S(A, x, y, w, h) = \sum_{i = x}^{x+w-1} \sum_{j = y}^{y+h-1} a_{ij}, \]
l'identità precedente diventa (generalizzando la somma da calcolare ad una sottomatrice qualsiasi)
\[ \begin{align} S(A, x, y, w, h) =& S(A, x, y, \lceil w/2 \rceil, \lceil h/2 \rceil) + S(A, x, y + \lceil h/2 \rceil, \lceil w/2 \rceil, h) \\ &+ S(A, x + \lceil w/2 \rceil, y, w, \lceil h/2 \rceil) + S(A, x + \lceil w/2 \rceil, y + \lceil h/2 \rceil, w, h). \end{align} \]
Ovviamente la somma totale è uguale a \( S(A, 0, 0, m, n) \) e la ricorsione si ferma quando la matrice ha dimensione 0 o 1 in entrambe le direzioni.

P.S. Il tuo metodo ricorsivo è comunque sbagliato perché manca il "caso base" che ferma la ricorsione. Scritto in quel modo la funzione viene infatti richiamata indefinitamente fino all'inevitabile crash del programma. Il metodo corretto sarebbe stato:

int somma_riga(int a[5][3], int i, int j) {
    if (j <= 0) {
        return 0;
    } else {
        return a[i][j-1] + somma_riga(a, i, j-1);
    }
}

Ma credo sarebbe stato meglio scrivere la funzione per sommare le righe nel modo seguente:

int somma(int *a, int j) {
    if (j < 0) return 0;
    else return a[j] + somma(a, j-1);
}

chiamando la funzione nel modo seguente in somma_elementi:

    s += somma(a[r], j-1); 

somma_elementi deve poi restituire la somma (oppure dovresti dichiararla come void).

[giuliomontenero]

scusa ma non ho capito a cosa serve nella funzione somma il puntatore *a, che cosa indica?

[apatriarca]

È il puntatore al primo elemento della riga che vuoi sommare.

[giuliomontenero]

quindi ho le due funzioni somma e somma_elementi
la seconda somma_elementi va a sommare tutti gli elementi scorrendo riga per riga , ma la funzione somma che cosa fa, che cosa somma?

[apatriarca]

Gli elementi di un array lungo j a partire dall'elemento puntato dal primo argomento. In C++ gli elementi di ogni riga sono adiacenti in memoria.

[giuliomontenero]

scusate ma io ancora nn ho capito bene
cioè ho capito lo scopo della funzione
ma il modfo di scriverla non lo capisco
io sapevo(studiando la teoria) che si poteva scrivere un array UNIDIMENSIONALE sia come a[] che con i puntatori *a, ma in questo caso siamo in presenza di un array bidimensionale a e vado a richiamare per di più lo stesso con *a.Perchè?
ho capito che *a punta al primo elemento della riga, per l'aritmetica dei puntatori dove *(a+n) equivale all' n-esimo elemnto dell'array, ma proprio non riesco neanche a capire perchè dopo scrivo return a[j] + somma(a, j-1)
a[j] è l'ultimo elemento della riga e quindi di un array unidimensionale e poi vado per ricorsione
il mio problema è : perchè uso l'array unidimensionale in questo caso trascurando completamente la riga e facendo scorrere solo le colonne? Insomma sul mio libro di testo o su internet non ho trovato niente a riguardo su puntatori ad array bidimensionali, potreste spiegarmi qualcosa voi?ve ne sarei molto grato.

[apatriarca]

Ogni volta che hai un puntatore puoi accedere ad esso come se fosse un array monodimensionale. In effetti a[n] è del tutto equivalente a *(a + n) in C*. Gli elementi di un array multidimensionale sono memorizzati uno dopo l'altro per righe. In memoria vedrai quindi la prima riga, poi la seconda e così via. Se hai quindi un puntatore al primo elemento di una qualche riga, puoi accedere agli elementi di quella riga semplicemente facendo finta che quello sia un array monodimensionale lungo quanto la riga. Il motivo per cui è meglio scrivere una funzione di quel tipo usando i puntatori invece che gli array bidimensionali è quindi quella che quella funzione la si potrebbe usare anche con gli array monodimensionali o anche con quelli 9-dimensionali se si desidera scorrere sugli elementi dell'ultima dimensione.


* Per vedere che è proprio equivalente puoi provare il seguente programma:

#include <stdio.h>

int main(void) {
    const char array[] = "!!!odnoM oaiC";
    const unsigned lastChar = sizeof(array) - 2;
    int i = 0;

    for (i = lastChar; i >= 0; --i) {
        putchar(i[array]);
    }
    puts("\n");

    return 0;
}

Ovviamente sconsiglio vivamente di scrivere un programma del genere se non per gioco in quanto rischi solo di rendere il codice meno leggibile.

[giuliomontenero]

ti ringrazio per la spiegazione ora ho capito
il problema è che non avevo pensato e non ricordavo che gli elementi di un array bidimensionale fossero memorizzati per righe
grazie ancora