Suma Cyfr Liczb

Zadanie

Napisz algorytm, który policzy sumę wszystkich cyfr w pewnym, określonym zakresie od 0 do n. Zastosuj technikę programowanie dynamicznego, aby uzyskać jak najbardziej optymalne rozwiązanie.

Przykład

Przykładowo jeśli n = 9 to poprawnym wynikiem jest 1+2+3+4+5+6+7+8+9=45. Z kolei dla 120 syma cyfr liczb wynosi 1023.

Implementacja

Rozwiązanie Naiwne

Najprostszy sposób do obliczenia sumy wszystkich cyfr każdej liczby z zakresu polega na napisaniu dwóch funkcji - jedna wylicza sumę cyfr dla konkretnej liczby, a druga sumuje wszystkie wyniki dla każdej liczyby z zakresu.

1. int SumaCyfr(int a) {
2.   int suma = 0;
3.   while (a > 0) {
4.     suma += a % 10;
5.     a /= 10;
6.   }
7.   return suma;
8. }
10. int SumujCyfry(int n) {
11.   int suma = 0;
12.   for (int i = 0; i <= n; i++) {
13.     suma += SumaCyfr(i);
14.   }
15.   return suma;
16. }

Przedstawione wyżej rozwiązanie daje zawsze poprawne rozwiązanie, ale niestety wymaga bardzo dużo czasu na obliczenia ze względu na wysoką złożoność, która jest w tym przypadku kwadratowa O(n²).

Rozwiązanie Optymalne

Zauważmy, że pewne sumy można wyliczyć bezpośrednio przed uruchomieniem funkcji zliczającej. W ten sposób można pomijać pewne zakresy liczb i od razu wyliczyć ich sumę. Sumy zostaną przygotowane dla wartości 9, 99, 999,.. Wyliczanie w nieskończoność nie ma sensu, więc wartość zostanie obliczona maksymalnie dla n-1 dziewiątek, gdzie n - to długość liczby. Przykładowo wyliczając dla liczby 120 obliczymy następujące wartości:

Powyższe wartości są wyliczane z wzoru rekurencyjnego. Otóż dla liczb od 1 do 9 jest to 45 co można obliczyć ze wzoru na sumę ciągu arytmetycznego. Rozszerzając do 99 wiadomo, że mamy po dziesięć liczb typu 0x, 1x, .., 9x oraz wiadomo, że dla takiego kompletu cykl cyfry jedności powtórzy się 10 razy, a więc a(n) = a(n-1) * 10 + 45 * 10 ^{n - 1}, gdzie a(0) = 0.

Podczas obliczania sumy dla np. 300 można policzyć sumę 0xx + 1xx + 2xx, gdzie xx to liczby zmieniające się od 00 do 99, więc wystarczy pobrać najbardziej znaczącą cyfrę i pomożyć ją przez obliczoną wcześniej wartość dla 99. Należy jednak dodać też sumę od 0 do najbardziej znaczącej cyfry i ją samą pomnożoną przez liczbę po jej usunięciu (przykładowo dla 321 byłoby to 3 * 21). Obliczanie sumy będzie odbywać się rekurencyjnie poprzez dodanie liczb powstałych dla ciągów bez najbardziej znaczącej cyfry.

Oto przykładowy kod:

1. int SumujCyfryRek(int a, int * pom) {
2.   if (a < 10) {
3.     return a * (a + 1) / 2;
4.   }
5.   int dl = log10(a) + 1;
6.   int mn = pow(10, dl - 1);
7.   int cyfra = a / mn;
8.   int suma = cyfra * pom[dl - 1];
9.   suma += cyfra * (cyfra - 1) / 2 * mn;
10.   suma += cyfra * (1 + a % mn);
11.   return suma + SumujCyfryRek(a % mn, pom);
12. }
14. int SumujCyfry(int n) {
15.   int dl = log10(n) + 1;
16.   int * pom = new int[dl] {0};
17.   for (int i = 1; i < dl; i++) {
18.     pom[i] = pom[i - 1] * 10 + 45 * (int)pow(10, i - 1);
19.   }
20.   return SumujCyfryRek(n, pom);
21. }

Funkcja SumujCyfry() ma za zadanie obliczyć potrzebne wartości, a następnie wywołać rekurencyjne obliczanie sumy. W tym przypadku złożoność maleje, ponieważ funkcja zostanie wywołana tyle razy ile cyfra ma liczb, a każde wywołanie to z góry ustalone operacje arytmetyczne, a więc algorytm ma złożoność liniową O(n).

Testowanie funkcji

W celu przetestowania napisanego rozwiązania można skorzystać z poniższego fragmentu kodu.

1. int main () {
2.   int n;
3.   cout << "Podaj zakres liczb:\n n = ";
4.   cin >> n;
5.   int suma = SumujCyfry(n);
6.   cout << "Suma cyfr wynosi: " << suma;
7.   system("pause");
8.   return 0;
9. }

• Kod źródłowy Implementacja