Sumowanie liczb naturalnych od 1 do n [C++]

Często pojawia się potrzeba zsumowania licz z przedziału od 1 do n. Najprostszym sposobem jest wykorzystanie pętli.


Nasz kod rozwiązujący ten problem w ten sposób wyglądał by tak:

	#include <iostream>
	using namespace std;
	unsigned long long suma_naj(unsigned long long n){
	unsigned long long suma=0;
	while(n>0){
	suma+=n;
	n--;
	}
	return suma;
	}
	int main() {
	long long n;
	cin>>n;
	cout<<suma_naj(n);
	return 0;
	}

view raw Sum-1-to-n.cpp hosted with ❤ by GitHub

Mogło by się wydawać, że wszystko jest ok program spełnia swoje zadanie. Jednak jego działanie dla bardzo dużych liczb jest bardzo wolne. Dzięki pętli program wykonuje w kółko te same operacje n razy. Jeśli chcemy z sumować liczby od 1 do 10 to nie robi to wielkiej różnicy ale współczesnych komputerów. Jednak co w przypadku gdy zechcemy sumować liczby większe np. od 100 000. Jak sami możecie zauważyć takie podejście do problemu nie jest zbyt wydajne. Pytanie czy można coś poprawić ? Okazuje się, że tak :) Trzeba jednak zauważyć że liczby od 1 do n tworzą ciąg arytmetyczny o różnicy 1. Nasz program wygląda teraz tak:

	#include <iostream>
	using namespace std;
	unsigned long long suma_opty(unsigned long long n){
	return ((1+n)*n)/2;
	}
	int main() {
	long long n;
	cin>>n;
	cout<<suma_opty(n);
	return 0;
	}

view raw Optimum-algorithm-sum-number-1-to-n.cpp hosted with ❤ by GitHub

Szybkość działania tego algorytmu nie jest już zależna od wprowadzonego n. Nie ma żadnej pętli która wykonuje się określoną ilość razy.