Το άθροισμα του Gauss

Ο Johann Carl Friedrich Gauss γεννήθηκε στις 30 Απριλίου 1777 και πέθανε στις 23 Φεβρουαρίου 1855. Ήταν γερμανός μαθηματικός που συνεισέφερε σε πολλά ερευνητικά πεδία της επιστήμης του, όπως η θεωρία αριθμών, η στατιστική, η μαθηματική ανάλυση, η διαφορική γεωμετρία, αλλά και συναφών επιστημών, όπως η γεωδαισία, η αστρονομία και η φυσική (ηλεκτροστατική, οπτική, γεωμαγνητισμός).

Όταν ήταν 10 μόλις ετών, μαθητής δημοτικού, ο δάσκαλος ζήτησε από την τάξη να υπολογίσουν το άθροισμα από το 1 ως το 100 (1+2+3+…+100). Εικάζουμε ότι ο δάσκαλος είχε δουλειά και θέλησε να απασχολήσει για ώρα τους μαθητές. Ο δάσκαλος δεν πέτυχε το σκοπό του, αφού ο Gauss σε λίγα δευτερόλεπτα απάντησε το αποτέλεσμα 5050!

Ας δούμε τι σκέφτηκε ο Gauss.

Το ζητούμενο ήταν:

S=1+2+3+...+98+99+100

Με βάση την αντιμεταθετική ιδιότητα (που τότε δεν τη γνώριζε φυσικά):

S=(1+100)+(2+99)+(3+98)+...

Άρα:

S=101+101+101+...

Δεδομένου ότι έπαιρνε τους αριθμούς ανα ζεύγη και τα ζεύγη του συνόλου [1,100] είναι 50:

S = 50 x 101= 5050

Αν δε γνωρίζαμε το Gauss θα ακολουθούσαμε την εξαντλητική μέθοδο, που αλγοριθμικά εκφράζεται ως εξής:

Αλγόριθμος WithoutGauss
 S  0
 Για i από 1 μέχρι 100
  S  S + i
 Τέλος_επανάληψης
 Εμφάνισε S
Τέλος WithoutGauss

 

Γενικεύοντας για οποιουδήποτε μήκους σειρά που ξεκινά από το 1 ο Gauss μας έδωσε το εξής:

Αλγόριθμος Gauss
 Διάβασε Ν  !όπου Ν είναι το μήκος της σειράς
 S  (N+1)*(N/2)
 Εμφάνισε S
Τέλος Gauss