La somma di tutti i numeri interi compresi tra due interi
Mi è capitato in questi giorni di dover risolvere questo problema: dati due numeri interi, il primo più piccolo del secondo, si vuole calcolare la somma di tutti gli interi compresi tra questi due estremi, inclusi i due estremi.
Sembrerebbe banale, ma dover eseguire questa operazione su estremi molto distanti tra loro può essere un’operazione ardua. Per questo motivo mi è stato chiesto di trovare una soluzione snella e di facile esecuzione.
La maggioranza dei comuni coder (programmatori) avrebbe fatto una interazione a partire dal primo estremo fino al secondo estremo e sommato, ad ogni interazione, il numero a quello precedente.
Inutile dire che questa, per quanto possa essere una soluzione funzionante, agli occhi di un’analista e sviluppatore è una soluzione orribile e poco funzionale.
Qui voglio mostrare come si dovrebbe approcciare a questo, ma in generale, a qualsiasi problema che debba essere risolto da un software. Alla fine di questo articolo avremo una soluzione elegante e funzionale al problema.
Per prima cosa ho iniziato a giocare con i numeri ed ho scoperto una proprietà che poi mi ha aiutato ad elaborare una funzione generale per risolvere il problema.
Ipotizziamo di voler fare la somma di tutti gli interi compresi tra 1 e 10, con questi ultimi inclusi. La somma è uguale a 55.
Una proprietà che ho scoperto è che se prendo i primi cinque numeri – 1, 2, 3, 4, 5 – e li sommo rispettivamente con gli altri cinque, inversamente ordinati – 10, 9, 8, 7, 6 – ho sempre lo stesso risultato e cioè 11. Quindi ho 5 coppie di risultati uguali.
1 + 10 = 11 2 + 9 = 11 3 + 8 = 11 4 + 7 = 11 5 + 6 = 11
Salta subito all’occhio che 11 e 55 hanno qualcosa in comune. Infatti 55 diviso 11 è uguale a 5; che guarda caso è uguale al numero di coppie che ho sommato.
Ora tutto questo ragionamento va reso una funzione matematica, e va anche verificato che funzioni in tutti i casi. In pratica, bisogna moltiplicare la somma di una coppia per il numero delle coppie.
La somma di una coppia è facile da calcolare, basta sommare i due numeri estremi – come suggerito dalla prima coppia che abbiamo scritto nell’esempio precedente – e cioè 1 + 10.
Per calcolare, invece, il numero delle coppie, bisogna calcolare la differenza tra l’estremo più grande e quello più piccolo e dividere per due. Tuttavia, facendo in questo modo, avremo il numero delle cifre a partire dall’estremo più piccolo, escluso quest’ultimo. Per cui, al risultato della differenza, aggiungeremo 1. Perciò avremo (10 – 1 + 1) / 2.
Moltiplicando tra loro la somma della coppia col risultato della differenza diviso due, avremo come risultato un numero che coincide con la somma di tutti i numeri interi compresi tra due interi.
Sostituiamo le variabili ai numeri così da scrivere una funzione matematica, per cui: (x+y) * [(y-x+1) / 2], dove x e y sono interi ed y è maggiore di x. Ovviamente questa funzione matematica, si può trasformare in qualsiasi momento in una funzione di un qualsiasi linguaggio di programmazione.
Che differenza tra l’interazione del coder! Immaginiamo di voler eseguire una interazione tra 1 e 1.000.000. Significa fare un ciclo per un milione di volte. La bellezza e l’eleganza di questa funzione matematica (frutto del ragionamento), invece, riduce il tutto ad una somma, una sottrazione, una divisione ed una moltiplicazione.
C’è differenza tra uno sviluppatore ed un programmatore, ti sei convinto ora?
ciao, mi chiamo Gianluca e faccio la 5° di un istituto tecnico informatico.. io stamattina ho fatto le olimpiadi di matematica e c’era un esercizio simile.
l’ho risolto nel seguente modo
se voglio sapere la somma di tutti i numeri da 1 a X eseguo la seguente formula:
somma=(x+1)*(x/2)
per esempio la somma dei numeri da 1 a 10 è 11*5=55
vedendo il tuo esempio:
somma da y a x compresi = [somma da 1 a x] – [somma da 1 a y]
somma=(x+1)*(x/2)-(y+1)*(y/2)
per esempio la somma dei numeri da 5 a 10 è (11*5)-(6*2.5) = 55-15 = 40
p.s. non servono le iterazioni adesso.. solo calcoli matematici
@Gianluca
Scusami, ma se hai avuto così tanta fretta nel fare questo post, allora devi anche incassare ciò che sto per dirti.
1)
L’eleganza della mia funzione è evidentemente superiore alla tua: faccio meno calcoli di te, perciò la mia è preferibile.
2)
Non vorrei dire una stupidaggine, ma ho provato la tua funzione con due estremi: x=5 e y=15. Applicando la tua funzione ho: (5+1)*(5/2) – (15+1)*(15/2). Per cui abbiamo: 6 * 2.5 – 16 * 7.5. Quindi: 15 – 120. Risultato: -105.
In realtà la somma di tutti gli interi è 110. Con la mia derivazione infatti abbiamo: (5+15) * [(15-5+1)/2]. Risolvendo abbiamo: 20 * (11/2). Quindi: 20 * 5.5. Totale: 110.
Risultato: non so se sei un genio, ma se a quella olimpiadi ci fossi stato io, avresti perso!
P.S.
La somma di tutti gli interi da 5 a 10 è 45 e non 40. Già li avrei potuto lasciar cadere la tua provocazione, ma mi sono divertito a smontarti. La prossima volta, sii più cauto!
va be ho sbagliato due cosine perchè ho ragionato in forma generale
sarebbe
somma da y a x compresi = [somma da 1 a x] – [somma da 1 a y]
somma=(y+1)*(y/2)-(x+1)*(x/2)
tu dici che La somma di tutti gli interi da 5 a 10 è 45 e non 40.
ma non è vero perchè devi contarte anche gli estremi..
infatti tu dici che la somma da 1 a 10 è 55 non 54 e quindi di conseguenza l’1 lo conti.
Tutti i tuoi calcoli effettuati con la mia formula sono giusti
sempre per il fatto che non includi il 5 nei calcoli..
(15+1)*(15/2) – (5+1)*(5/2)= 105 che è giusto!! perchè i numeri da 5 a 15 sono il 5,6,7,8,9,10,11,12,13,14,15
Inoltre alle olimpiadi ho totalizzato 14/16 e sono passato ai regionali
Mi sono divertito a smontarti..La prossima volta, sii più cauto!
P.S. la mia intenzione non era vantarmi ma condividere un ragionamento, ma siccome ti comporti da bambino e fai paragoni allora lasciamo perdere.
ciao
@Gianluca
Senti io non capisco quello che scrivi. Mi sembra di capire che metti in dubbio che la somma degli interi da 5 a 10 non è 45; e che la somma degli interi da 5 a 15 non è uguale a 110.
Cioè mi stai dicendo che 5+6+7+8+9+10 non è uguale a 45?
E mi stai anche dicendo che 5+6+7+8+9+10+11+12+13+14+15 non fa 110?
Hai provato a prendere un foglio o una calcolatrice e a farti i calcoli analiticamente, prima di riporre cieca fiducia alla tua miope equazione? Spero di aver capito male, altrimenti siamo veramente alla frutta.
Mo mi dici chi te lo fa fare di venire su questo blog a fare il “genio”? La tua soluzione andrà bene per quello che serve a te (il tuo 14/16 alle olimpiadi), ma è totalmente sbagliata per quello di cui si parla in questo articolo (e ti invito a leggere la traccia che ho scritto proprio all’inizio).
Vuoi vedere come Galilei ti da torto?
Facciamo un test facile facile. Poniamo x = 1 e y = 3. 1+2+3 è uguale a 6, non ci sono dubbi no? Non ci vuole la calcolatrice ora!
Applico la tua formula che è (y+1)*(y/2)-(x+1)*(x/2). Per cui sostituisco i valori alle variabili ed ho (3+1)*(3/2)-(1+1)*(1/2). Faccio le operazioni in parentesi: 4*1.5 – 2*0.5. Faccio le moltiplicazioni (che hanno la priorità): 6-1. Risultato: 5.
Applico la mia formula che è (x+y)*[(y-x+1)/2]. Per cui sostituisco i valori alle variabili ed ho (1+3)*[(3-1+1)/2]. Faccio le operazioni in parentesi tonda: 4*[3/2]. Faccio le operazioni in parentesi quadra: 4*1.5. Risultato: 6.
A chi ha dato ragione il metodo sperimentale di Galileo Galilei? A me dispiace, sei venuto a “smontarmi”, ma ti sei preso un’altra batosta! Forse semplicemente tu stai parlando di qualcosa che non ha alcuna attinenza in questo articolo.
Sii cauto, leggi prima, capisci di cosa si sta parlando e poi intervieni. E soprattutto, applica il metodo di Galilei per dimostrare i tuoi fatti!
Scusate bimbi, ma sapete che tale formula è stata ricavata da Gauss in seconda elementare? La maestra assegnò il seguente compito: calcolate la somma di tutti i numeri (naturali) da 0 a 100 e Gauss risolse il quesito in pochi minuti. La maestra rimase estasiata…
@francesco
Ti dimostro che la mia è più potente di quella di Gauss, ergo, non è quella di Gauss.
La formula di Gauss è: [N * (N+1)]/2. Questa formula è valida solo però per le somme di interi a partire da 0. Infatti per N si intendono i numeri Naturali, cioè i numeri interi non negativi (0, 1, 2, 3, 4, …).
La mia formula – che può essere resa anche [(Zx+Zy)*(Zy-Zx+1)]/2 – invece non si aspetta numeri naturali, ma numeri interi (o relativi). Si indicano, come indicato, con la lettera Z (…, -3, – 2, -1, 0, 1, 2, 3, …).
Se Zx fosse 1, la mia formula si potrebbe semplificare in [(Zy+1) * Zy]/2. Ovviamente se Zx è 1, di certo Zy sarà maggiore, quindi un numero Naturale. Quindi, la posso semplificare in [(N+1) * N]/2, che poi è la formula di Gauss. Ma è un caso particolare!
Ti do il benvenuto ufficiale al club del: riflettere prima di parlare!
P.S.
In realtà quella che io definisco “mia formula” è solo una formula che ho derivato da solo e che non mai letto o copiato da nessuna parte. Ciò non significa che non possa già esistere, anzi, non ne sarei affatto sorpreso.
Se qualcuno sapesse dare un nome a questa funzione, non esiti a commentare questo articolo.
Dario e Gianluca, gli Einstein del futuro
@digitaldeath
Mi aspettavo qualcosa di più illuminante!
Perché del futuro?
Ehm… Scusate: la formula di partenza, quella di Gianluca, che per inciso è quella dei numeri triangolari, è vecchia quanto Pitagora. D’altra parte quella di Dario è riproducibile a partire da quella originaria di Pitagora (vedi formula del 20 dicembre 2008) a patto di aggiungervi l’estremo inferiore. E non sono necessari esempi realizzati ad hoc per dimostrarlo.
Presto sul mio blog un post un po’ più esaustivo!
@Gianluigi
Qualcosa di costruttivo, finalmente!
Sebbene non capisca come la formula di Gauss (che è quella che poi utilizza Gianluca e che illustro qui) sia legata ai numeri triangolari (ma credo che sia per mia incompetenza), finalmente la strada verso la paternità (o maternità) della mia derivazione comincia a prendere una direzione.
Poiché ho intenzione di approfondire i numeri triangolari su Science Backstage, potrei anche non scrivere nulla, però: 3 è numero triangolare in quanto somma di 2 e 1, che disegnati ciascuno come pallini possono essere rappresentati su un triangolo. Stessa cosa per 6, che è somma di 3, 2 e 1. Ogni numero naturale è quindi triangolare se ha la forma n + (n-1) + … + 2 + 1 = n(n+1)/2.
E la scoperta originale è di quella geniale scuola matematica che era quella Pitagorica: poi ci sono volti altri geni per riscoprire quelle idee e tra questi, ovviamente, c’è anche Gauss!
P.S.: grazie per i commenti di ieri e speriamo di avere altre interessanti discussioni internettiane in futuro anche su altri argomenti!
@Gianluigi
Con piacere … sei già tra i miei feeds!
@DarCas
Gianluca: “somma da y a x compresi”, quindi suppone y<=x, cioè ha scambiato le variabili rispetto alla "tua" formula.
(x+y) * [(y-x+1) / 2] = (x*y-x^2+x+y^2-x*y+y)/2 = (y^2-x^2+x+y)/2 = [(y+1)*y-(x+1)*x]/2
State usando (male, imho) la stessa formula. Scritta (e implementata) così:
sum = (x+y)*(y-x+1)/2 tutte le operazioni sono "intere".
Certo, se in Y metti il valore di X e viceversa, e poi utilizzi la formula come dici tu, è vero è la stessa cosa.
Ma se osservi i commenti precedenti, vedrai che non è così, che i risultati miei contrastano con quelli dell’altro e che – sperimentazione galileiana alla mano – ho ragione io sulla formula.
Poi per quanto riguarda se è utilizzata bene o male, non saprei… andrebbe dimostrato con i fatti e non a parole… stiamo parlando di matematica non di filosofia, quindi ci vogliono le dimostrazioni!
@DarCas
Errore mio (analitico) e di Gianluca (concettuale): Col suo metodo elimina l’estremo inferiore della somma (es. 1+2+3+4+5 – (1+2) = 3+4+5).
(y^2-x^2+x+y)/2 = [(y+1)*y-(x-1)*x]/2 = [(y+1)*y-(x+1)*x+2x]/2 = x+[(y+1)*y-(x+1)*x]/2
Per il resto mi riferivo alla traduzione della formula in un linguaggio di programmazione tipizzato. Se fai la divisione per ultima, tutte le variabili e le operazioni sono tra interi, altrimenti devi considerare dei valori float.
@Roberto
Beh, se devi realizzare un software che debba girare sul computer dell’Apollo 11 allora posso darti ragione.
In un contesto moderno normale, non vedo quale implicazione può avere fare la divisione prima o dopo.
@DarCas
Forse mi sbaglio, ma se scrivi in C(o C++, forse anche C#)
int Somma( int x, int y)
{ return (x+y)*((y-x+1)/2);}
Il compilatore interpreta “/2″ come divisione tra interi, quindi avresti 3/2=1.
Dovresti come minimo riscriverlo così:
int Somma( int x, int y)
{ return (int) (x+y)*((y-x+1)/2.0);}
Per forzare l’operazione corretta. Io preferisco:
int Somma( int x, int y)
{ return (x+y)*(y-x+1)/2;}
Certo se metti la formula in una cella di excel non dovresti avere problemi, ma forse se la scrivi in VBA…
@Roberto
Ora ho capito cosa vuoi dire. Beh, direi che sei decisamente off topic.
Il compito di risolvere i problemi specifici di ogni linguaggio di programmazione è delegato ai programmatori. Io sono uno sviluppatore, a me interessa risolvere il problema in maniera astratto.
Mi posso anche cimentare nell’implementazione della soluzione in qualche linguaggio di programmazione, ma non era lo scopo di questo articolo.
Infatti, non trovi traccia di linguaggio o meta linguaggio, ma solo matematica… ed in matematica il problema che tu sollevi non si presenta.
@DarCas
Sono d’accordo sulla necessità di astrazione e soprattutto sull’importanza di uno studio matematico del problema prima della sua codifica. Forse sei stato solo un pò ingeneroso rispetto al coder medio. Col mio appunto voleva solo ricordare che anche una buona teoria richiede una certa attenzione e uno studio ulteriore, quando va messa in pratica.
E poi anche l’analisi numerica è una branca della matematica