Strona główna » Algorytmy » Teoria Liczb » Suma Cyfr Sumy Cyfr
 

Suma Cyfr Sumy Cyfr

https://mattomatti.com/a0135

Zadanie

Dla podanej wartości n znajdź wszystkie liczby całkowite dla których suma: tej liczby, sumy cyfr tej liczby oraz suma cyfr sumy cyfr tej liczby daje wartość n. Czyli w sumie trzeba znaleźć sumę. Zmieniając zapis słowny na zapis matematyczny otrzymujemy następujące równanie:

a + suma(a) + suma(suma(a)) = n, gdzie suma() oznacza funkcję, która zwraca sumę cyfr przekazanej liczby

Przykład

Przykładowo dla n = 123 istnieją trzy liczby spełniające podane równanie: 98, 107, 113. W tabelce zostało przedstawione odpowiednie liczby do zsumowania:

asuma(a)suma(suma(a))suma
98178123
10788123
11355123

Implementacja

Sumowanie cyfr

Sumowanie cyfr jest algorytmem liniowym, którego złożoność zależy od ilości cyfr w zapisie liczby. Im więcej liczba posiada cyfr tym więcej trzeba wykonać operacji arytmetycznych. Z tego powodu najbardziej kosztowną operacją w algorytmie jest obliczenie sumy cyfr.

  1. int sumujCyfry(int a) {
  2.   int suma = 0;
  3.   while (a > 0) {
  4.     suma += a % 10;
  5.     a /= 10;
  6.   }
  7.   return suma;
  8. }

Proste rozwiązanie

Suma trzech liczb musi wynieść n. W celu znalezienia wszystkich liczb należy sprawdzić wszystkie liczby od [0, n]. Dla każdej z nich należy wyznaczyć sumę cyfr i tej sumy sumę cyfr, a następnie sprawdzić warunek. Zadanie to realizuje poniższy kod:

  1. void szukajLiczb(int n) {
  2.   for (int i = 0; i <= n; i++) {
  3.     int s0 = sumujCyfry(i);
  4.     int s1 = sumujCyfry(s0);
  5.     if (i + s0 + s1 == n)
  6.       cout << i << " ";
  7.   }
  8. }

Optymalizacja

Sumowanie cyfr niektórych liczb jest wykonywane więcej niż jeden raz. Oznacza to, że można stworzyć pewien bufor w którym zostaną zapamiętane obliczone do tej pory wartości. Nie należy jednak zapisywać wszystkich obliczonych sum, ponieważ doprowadzi to z kolei do niepotrzebnie zwiększonego zużycia pamięci.

Jeśli liczba składa się z p cyfr to znaczy, że największa możliwa suma jej cyfr wynosi 9p. Czyli przed rozpoczęciem obliczeń należy przygotować 9p + 1 pozycji na zapisanie sum. Następnie suma cyfr sumy cyfr nie będzie obliczana poprzez dwukrotne wywołanie funkcji sumujCyfry(), a poprzez odczytanie odpowiedniej wartości z wypełnionej tablicy.

Poniższy kod realizuje przedstawione rozumowanie:

  1. void szukajLiczb(int n) {
  2.   int max = (log10(n) + 1) * 9;
  3.   int* dane = new int[max];
  4.   for (int i = 0; i <= n; i++) {
  5.     int s0 = sumujCyfry(i);
  6.     if (i <= max)
  7.       dane[i] = s0;
  8.     if (i + s0 + dane[s0] == n)
  9.       cout << i << " ";
  10.   }
  11. }

Testowanie funkcji

W celu przetestowanie działania kodu można skorzystać z poniższego fragmentu. Wczyta od użytkownika żądaną sumę n i rozpocznie obliczenia.

  1. int main () {
  2.   int n;
  3.   cout << "Podaj sume do osiagniecia\n n = ";
  4.   cin >> n;
  5.   cout << "Liczby spelniajace rownanie:\n";
  6.   szukajLiczb(n);
  7.   system("pause");
  8.   return 0;
  9. }