Newsgroup: it.comp.lang.c
Titolo: somma elementi array con ricorsività+divide et impera

Salve ragazzi,è la prima volta che posto qui:dovrei scrivere in C una
function che mi permetta di eseguire la somma di un array di 10
elementi di int attraverso il divide et impera e la
ricorsione.Chiunque sia in grado di spiegarmelo,o di postare il
codice,mi farebbe un immenso da piacere,xche da solo non lo capisco...

 Salve ragazzi,č la prima volta che posto qui:dovrei scrivere in C una

rispondo a parole, l'implementazione e' meglio che la fai tu altrimenti 
la validita' didattica di questo esercizio si annulla.
versione ricorsiva semplice :
la somma degli elementi di un vettore di n elementi e' pari alla somma 
del vettore compostovettori composto dai primi n-1 elementi piu' il 
valore dell' enne-simo elemento,se il vettore e' composto da un solo 
elemento ha come somma il valore di quell'unico elemento
versione ricorsiva divide et impera :
la somma deggli elementoi di un vettore di n-elementi e' pari alla somma 
   delle somme di due vettore composti il primo dai primi n/2 elementi 
ed il secondo dagli altri n/2 elementi ( se n non e' divisibile per due 
la divisione va fatta in maniera asimmetrica ) ancora una volta vettori 
composti da un solo elemento hanno somma pari al valore du quel singolo 
elemento.
suggerimento: in nessuno dei due casi e' necessario ricopiare i dati dei 
vettori nei sub-vettori successivi essendo possibile elaborarli in loco 
con un uso accorto dei puntatori.
nota bene: il primo algoritmo puo' essere visto come una versione 
'degenere' del divide et impera in cui il secondo vettore e' composto 
sempre da un solo elemento.
ancora : fare la somma di un vettore in maniera ricorsiva e' solo un 
modo didattico per introdurre algoritmi ricorsivi ( e tecniche di 
programmazione come il divide et impera ) in quanto e' certamente meno 
efficiente dell'algoritmo iterativo 'classico'.

forse è per questo che nn riesco a capirlo,nn riesco a trovarne
l'effettiva utilità,potresti postarmi ugualmente un codice
sorgente,magari commentato?in qst modo studio direttamente sul sorgente

raeziel wrote:

Alcuni problemi sono formulati naturalmente con la ricorsione, per questo
risolverli in maniera ricorsiva è banale.
Nel caso degli array, invece non è la prima cosa che ti viene in mente e per
questo può sembrare una cosa ostica.
Devi formulare il problema in maniera ricorsiva.
Come ti hanno già risposto:
Sommare gli elementi di un array vuol dire sommare al primo elemento la
somma degli elementi dell'array che parte dal secondo elemento.
Se l'array non ha elementi allora la somma vale zero.
Fin qui mi pare semplice no?
Il codice te lo posto anche se non dovrei e si spiega da solo.
a è l'array e n il numero di elementi. ATTENZIONE: Forse le graffe non si
vedono bene devo correggere la codifica dei caratteri non so perchè non
vanno queste sono graffe {}
float somma (float* a, int n){
        if (n=0)
                return 0;
        return a[0] + somma (&a[1], n-1);
}
non l'ho provato ma dovrebbe andare. Tre righe! Ti rendi conto della
leggibilità!? Come vedi i commenti non sono neanche necessari!
Spero ora ti sia più chiara la faccenda
Ciao
Giuseppe

  
        if (n == 0)
 
M

Max M. wrote:

oopssss !!!
G.

 
un libro dove le tecniche di programmazione di base sono ben trattate e' 
il wirth algoritmi+strutture dati=programmi
un capitolo sulla ricorsione in generale piu' un capitolo sulle 
strutture dati ricorsive e' basato sul pascal ma la trattazione e' buona
esiste una versione free basata su oberon ma il valore didattico e' 
comunque altissimo.
http://www.oberon.ethz.ch/WirthPubl/
algoritmo ricorsivo divide et impera
int summa( int vec[], int size) {
	if (n==1) {			// un solo elemento somma banale
		return vec[0];		// la ricorsione termina
	}
	else {				// divisione in due problemi 							// piu' piccoli e ricorsione
		return summa(VEC1,SIZE1)+summa(VEC2,SIZE2);
	}
}
ti ho lasciato appeso VEC1,SIZE1 e VEC2,SIZE2 i due 'sottovettori' e le 
due dimensioni
sta tutto il problema ed e' bene che lo affronti TU per capire come 
approcciare il divide et impera.