View Full Version : [C] somma interi con ricorsione - migliorare programma già fatto
#include <stdio.h>
int sommaTraInteri(int myA, int myB, int*, int*);
int main(){
int mA=12;
int mB=16;
int sum=0;
int cur=mA+1;
printf("\n%d\n",sommaTraInteri(mA,mB,&sum,&cur));
}
int sommaTraInteri(int myA, int myB, int *sum, int *cur){
if(*cur>myA && *cur<myB){
*sum=*sum+*cur;
*cur=*cur+1;
sommaTraInteri(myA,myB,sum,cur);
} else return *sum;
}
ho appena fatto questo programma che effettua la somma di tutti gli interi che si trovano tra i due interi passati alla funzione come argomento ( quindi non considera gli estremi nella somma ), il punto è che funziona perfettamente, ma non mi piace stilisticamente e per come è scritto, vorrei migliorarlo un po', ma sarà l'ora, ma non mi vengono molte idee, voi ne avete?
#include <stdio.h>
int sommaTraInteri(int myA, int myB, int);
int main(){
int mA=12;
int mB=16;
int cur=mA+1;
printf("\n%d\n",sommaTraInteri(mA, mB, cur));
}
int sommaTraInteri(int myA, int myB, int cur) {
if(cur>myA && cur<myB)
return cur + sommaTraInteri(myA, myB, cur+1);
}
Spero non sia un qualche genere di compito :)
#include <stdio.h>
int sommaTraInteri(int myA, int myB, int);
int main(){
int mA=12;
int mB=16;
int cur=mA+1;
printf("\n%d\n",sommaTraInteri(mA, mB, cur));
}
int sommaTraInteri(int myA, int myB, int cur) {
if(cur>myA && cur<myB)
return cur + sommaTraInteri(myA, myB, cur+1);
}
Spero non sia un qualche genere di compito :)
tranquillo che sono esercitazioni a caso che sto rabattando da internet giusto per fare qualcosa.
in pratica hai tolto il passaggio per riferimento e fatto un "trenino" di int con il return, sembra più corta in effetti ...
EDIT: il programma ha una logica errata, mi da un risultato sbagliato
Puoi darmi qualche dettaglio in più? Con l'esempio 12-16 mi da 42 che è la risposta giusta se non ho capito male il problema.
Puoi darmi qualche dettaglio in più? Con l'esempio 12-16 mi da 42 che è la risposta giusta se non ho capito male il problema.
io ho controllato la logica e mi sembra corretta, ma il programma compilato sotto codeblocks mi da 58 come valore, preso pari pari e soltanto incollato e compilato.
non riesco a capire, provo a compilarlo "a mano" con gcc.
sempre 58 mi da.
edit: in pratica include nella somma anche l'estremo mB, il risultato dovrebbe essere 42, ma viene 58 cioé 42+16
int Summer( int a, int b )
{
if (a>=b) return 0;
if (b-a==1) return 0;
if (b-a==2) return a+1;
return a+1 + Summer(a+1, b);
}
Scritto al volo, non l'ho testato molto...
Non ho codeblocks qua ma usando questo
http://codepad.org/txumHNmt
Mi dà il risultato giusto. Non sò che dire.
Prova così sennò.
int sommaTraInteri(int myA, int myB, int cur) {
if(cur<=myA || cur>=myB)
return 0;
return cur + sommaTraInteri(myA, myB, cur+1);
}
adesso installo linux da qualche parte e provo con altre versioni di gcc, ho paura che questo sia un bug ...
compilato sotto la beta1 attuale di Ubuntu
tux@tux-VirtualBox:~$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.6.1/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.6.1-7ubuntu2' --with-bugurl=file:///usr/share/doc/gcc-4.6/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++,go --prefix=/usr --program-suffix=-4.6 --enable-shared --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.6 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-plugin --enable-objc-gc --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.6.1 (Ubuntu/Linaro 4.6.1-7ubuntu2)
e sempre 58 mi da, inizio a pensare male di gcc
C'è da dire che la tua versione iniziale mi pare sia tail-recursive (involontariamente, credo), mentre le altre che ho visto successivamente mi pare non lo siano.
Io farei una roba tipo (se non ho scritto stronzate):
#include <stdio.h>
int SumRangeAux(int a, int b, int accum) {
return a >= b ? accum : SumRangeAux(a + 1, b, accum + a);
}
int SumRange(int a, int b) {
return SumRangeAux(a + 1, b, 0);
}
int main() {
int a = 12, b = 16;
printf ("%d\n", SumRange(a, b));
return 0;
}
No, hai ragione, la mia non è tail-recursion. La soluzione iniziale immagino possa essere definita tail-recursion ma non usa minimamente la ricorsione, si passa direttamente il puntatore al risultato in giro. Non ha per niente senso così.
Se vuoi qualcosa con la tail-recursion l'unica cosa che mi viene in mente è
#include <stdio.h>
int sommaTraInteri(int myB, int, int);
int main(){
int mA=12;
int mB=16;
printf("\n%d\n",sommaTraInteri(mB, mA+1, 0));
}
int sommaTraInteri(int myB, int cur, int tot) {
if(cur>=myB)
return tot;
return sommaTraInteri( myB, cur+1, tot + cur);
}
Almeno usi i valori di ritorno ma mi sembra abbastanza brutto.
La mia versione finale è:
#include <stdio.h>
int sommaTraInteri(int myA, int myB);
int main(){
int mA=12;
int mB=16;
printf("\n%d\n",sommaTraInteri(mA+1, mB));
}
int sommaTraInteri(int myA, int myB) {
if(myA==myB)
return 0;
return myA + sommaTraInteri( myA + 1 , myB );
}
C'è una formula facile da ricordare che permette di sommarli senza ricorsione o cicli. Però tiene conto anche degli estremi quindi nel tuo caso ci si deve ricordare di aggiungere e sottrarre 1.
#include <stdio.h>
int sum(int from, int to) {
return ((to * to) - (from * from) + from + to) / 2;
}
int main(int argc, char** argv) {
printf("%d", sum(12 + 1, 16 - 1));
}
Almeno usi i valori di ritorno ma mi sembra abbastanza brutto.
Sì beh non è tanto questione di bello o brutto. Sono due soluzioni molto diverse in termini di complessità di spazio, ed è bene conoscere questi aspetti, soprattutto se uno sta facendo esercizi per imparare.
AnonimoVeneziano
06-09-2011, 09:09
Puoi darmi qualche dettaglio in più? Con l'esempio 12-16 mi da 42 che è la risposta giusta se non ho capito male il problema.
EDIT : non ho letto bene :D
AnonimoVeneziano
06-09-2011, 09:14
tranquillo che sono esercitazioni a caso che sto rabattando da internet giusto per fare qualcosa.
in pratica hai tolto il passaggio per riferimento e fatto un "trenino" di int con il return, sembra più corta in effetti ...
EDIT: il programma ha una logica errata, mi da un risultato sbagliato
La logica è sbagliata almeno per un motivo : Nel caso "if" tu non ritorni un valore, infatti con capisco come faccia a funzionarti in alcuni casi :confused: (forse piglia qualcos'altro dallo stack ... che a volte potrebbe essere anche la cosa giusta o il registro EAX usato per il valore di ritorno viene usato anche per la somma e quindi rimane impostato all'uscita dell'ultima "sommaTraInteri" oppure ancora viene impostato dal return del caso else ...)
#include <stdio.h>
int sommaTraInteri(int myA, int myB, int*, int*);
int main(){
int mA=12;
int mB=16;
int sum=0;
int cur=mA+1;
printf("\n%d\n",sommaTraInteri(mA,mB,&sum,&cur));
}
int sommaTraInteri(int myA, int myB, int *sum, int *cur){
if(*cur>myA && *cur<myB){
*sum=*sum+*cur;
*cur=*cur+1;
sommaTraInteri(myA,myB,sum,cur);
} else return *sum;
}
La linea in grassetto dovrebbe essere:
return sommaTraInteri(...blah) ;
Sì beh non è tanto questione di bello o brutto. Sono due soluzioni molto diverse in termini di complessità di spazio, ed è bene conoscere questi aspetti, soprattutto se uno sta facendo esercizi per imparare.
La cosa più importante prima è scrivere qualcosa di corretto, tail o no viene dopo, molto dopo.
Inoltre per come la vedo io, se devi scrivere codice tail-recursive, a meno che non ti venga naturale farlo, tantovale usare direttamente l'iterazione.
La via più naturale, per come la vedo io, è usare la ricorsione classica con lo stack delle chiamate, anche se questo può essere meno efficiente, ma secondo me è utile per capire bene il meccanismo.
La cosa più importante prima è scrivere qualcosa di corretto, tail o no viene dopo, molto dopo.
Su questo non ci piove.
Inoltre per come la vedo io, se devi scrivere codice tail-recursive, a meno che non ti venga naturale farlo, tantovale usare direttamente l'iterazione.
La via più naturale, per come la vedo io, è usare la ricorsione classica con lo stack delle chiamate, anche se questo può essere meno efficiente, ma secondo me è utile per capire bene il meccanismo.
No ma io non sto difendendo una soluzione piuttosto che un'altra. Dico solo che è bene sapere riconoscere e capire pro e contro di entrambi gli approcci. Altrimenti si finisce a calcolare fibonacci con complessità esponenziale solo perché "il prof. mi ha insegnato che la ricorsione è così".
E alla fine in termini pratici dipende dal linguaggio: in C usare la ricorsione in questo modo non è il modo idiomatico di esprimere questo algoritmo. In Haskell magari la situazione cambia... e allora è bene sapere la differenza tra i vari approcci e non solo avere "qualcosa che funziona".
AnonimoVeneziano
06-09-2011, 13:58
In Haskell magari la situazione cambia... e allora è bene sapere la differenza tra i vari approcci e non solo avere "qualcosa che funziona".
lol :: Int -> Int -> Int
lol a b | a < (b-1) = (a+1) + k
| a >= b-1 = 0
where k = lol (a+1) b
main = do
putStrLn $ show $ lol 20 25
:sofico:
per la cronaca la logica del programma di Kenger va corretta con un "return 0":
int sommaTraInteri(int myA, int myB, int cur) {
if(cur>myA && cur<myB)
return cur + sommaTraInteri(myA, myB, cur+1);
else
return 0;
}
la funzione corretta è questa.
Sì beh non è tanto questione di bello o brutto. Sono due soluzioni molto diverse in termini di complessità di spazio, ed è bene conoscere questi aspetti, soprattutto se uno sta facendo esercizi per imparare.
Scusa, mi sono espresso male. Per me in programmazione brutto vuol dire che stai facendo qualcosa di sbagliato o che stai usando un concetto( la ricorsione ) senza usarlo davvero (nel primo caso) o usarlo in un modo poco elegante (il mio primo modo). Bello è un modo funzionale, elegante o ottimale per fare qualcosa! :D
per la cronaca la logica del programma di Kenger va corretta con un "return 0":
int sommaTraInteri(int myA, int myB, int cur) {
if(cur>myA && cur<myB)
return cur + sommaTraInteri(myA, myB, cur+1);
else
return 0;
}
la funzione corretta è questa.
Si, è uguale all'ultima versione che ti ho fornito!
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.