[C] Somma interi da 2 a 30

[murder eyes]

So perfettamente a cosa si va incontro usando la ricorsione. se veniva chiesto di calcolare la somma per un numero enorme di elementi sicuramente non avrei postato il messaggio.
Ho scritto solo perchè il problema era fattibilissimo con la ricorsione e molto più conciso. Tutto qua.

[oregon]

D'accordo, ma la mia opinione era "generale", non legata all'esempio del numero 30 (che non puo' essere preso come un problema "reale" ma solamente come una "tipologia" di esempi).

Anche perche' in questo modo chi ha proposto il problema potrebbe farsi convinto che il suo e' "comunque" (cioe' per qualsiasi valore) risolvibile con la ricorsione e che, fino ad ora, nessuno gli ha dato la soluzione giusta ...

[unomichisiada]

Credo di aver trovato una soluzione generale con complessità O(1)

int sum2(int k,int n)
{
	k = (k+1)/2 *2;
	n = (n)/2 *2;
	if(k>n) 
		return 0;
	int tot = ((n + k) * ((n -k)/2 +1))/2;
	
	return tot;
}

Non l'ho testata assiduamente ma dovrebbe essere corretta.
Un programmino di test

#include <stdio.h>
int sum(int k,int n);
int sum2(int k,int n);
int main ()
{
int p = 6;
	printf("La somma O(n) e':\n");
	for(int i = p; i <= 130;i++)
		printf("%d ", sum(p,i));
	printf("\n\nLa somma O(1) e':\n");
	for(int i = p; i <= 130;i++)
		printf("%d ", sum2(p,i));
	
	return 0;
}
int sum(int k,int n)
{
	int num;
	int tot = 0;
	for (num=k;num<=n;num++)
	{
			if (num % 2 == 0)
			{
				 tot = tot + num;
			}
	}
	return tot;
}
int sum2(int k,int n)
{
	k = (k+1)/2 *2;
	n = (n)/2 *2;
	if(k>n) 
		return 0;
	int tot = ((n + k) * ((n -k)/2 +1))/2;
	
	return tot;
}

[fabi080]

Originariamente inviato da unomichisiada
Credo di aver trovato una soluzione generale con complessità O(1)

Senza offesa, ma il buon Gauss l'ha trovata alla tenera età di 8 anni...

http://it.wikipedia.org/wiki/Progressione_aritmetica

[unomichisiada]

Originariamente inviato da fabi080
Senza offesa, ma il buon Gauss l'ha trovata alla tenera età di 8 anni...

http://it.wikipedia.org/wiki/Progressione_aritmetica

Nessuna offesa!Mi sono rifatto a lui infatti, facendo solo alcune piccole modifiche,solo che nessun'altro in questa discussione ci aveva pensato ed ho postato!
Come si dice siamo nani che camminano sulle spalle di giganti!

[apax83]

Salve ragazzi....sono pax, nuovo di questo forum...e' il primo messaggio che posto!!!!

Sono Pienamente d'accordo con Luciano79 per quanto riguarda l'inizializzazione delle variabili in c e c++!!!!Sono fondamentali....

Tornando al problema credo che il seguente programma funzioni correttamente...in qualunque situazione...CREDO!!!

[CODE]
#include <stdio.h>


int main(){

int num,tot=0;

for(int n=0;n<=((X-2)/2);n++){
num=2*(n+1);
tot+=num;
}


return 0;
}

[\CODE]

La X nella condizione del for è la costante che rappresenta il punto di arrivo della somma, in questo caso 30!!!


Ciao Ciaojavascript:smilie('')
Ciauz

[unomichisiada]

Originariamente inviato da apax83
Salve ragazzi....sono pax, nuovo di questo forum...e' il primo messaggio che posto!!!!

Sono Pienamente d'accordo con Luciano79 per quanto riguarda l'inizializzazione delle variabili in c e c++!!!!Sono fondamentali....

Tornando al problema credo che il seguente programma funzioni correttamente...in qualunque situazione...CREDO!!!

[CODE]
#include <stdio.h>


int main(){

int num,tot=0;

for(int n=0;n<=((X-2)/2);n++){
num=2*(n+1);
tot+=num;
}


return 0;
}

[\CODE]

La X nella condizione del for è la costante che rappresenta il punto di arrivo della somma, in questo caso 30!!!


Ciao Ciaojavascript:smilie('')
Ciauz

Ehm...ha complessita O(n) però...dov'è la miglioria?

[apax83]

Beh in effetti non c'è una miglioria...la tua soluzione e' quella piu' efficente senza dubbio...ho solo proposto un alternativa concettualmente molto semplice basata sul calcolo algebrico dei numeri pari...in sole 7 righe di codice...

E' cmq una soluzione....
Bisogna poi valutare l'uso che se ne voglia fare...

[unomichisiada]

Originariamente inviato da apax83
Beh in effetti non c'è una miglioria...la tua soluzione e' quella piu' efficente senza dubbio...ho solo proposto un alternativa concettualmente molto semplice basata sul calcolo algebrico dei numeri pari...in sole 7 righe di codice...

E' cmq una soluzione....
Bisogna poi valutare l'uso che se ne voglia fare...

Capito!
Praticamente si può dire che non è neanche la mia soluzione, è più di gauss

[apax83]

Si hai ragione...ma io sono dell'idea che queste cose per quanto siano state teorizzate da altri,appartengono al nostro intelletto personale in quanto fondamenta di quello che oggi noi conosciamo....e cmq sei stato l'unico che fino ad ora ci aveva pensato....per cui.....???