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.

C++C#
Python
  1. def sumujCyfry(a):
  2.   suma = 0
  3.   while (a > 0):
  4.     suma += a % 10
  5.     a = int(a / 10)
  6.   return suma

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:

C++C#
Python
  1. def szukajLiczb(n):
  2.   for i in range(n + 1):
  3.     s0 = sumujCyfry(i)
  4.     s1 = sumujCyfry(s0)
  5.     if (i + s0 + s1 == n):
  6.       print(i, end = ' ')

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:

C++C#
Python
  1. def szukajLiczb(n):
  2.   max = (math.log10(n) + 1) * 9
  3.   dane = []
  4.   for i in range(n + 1):
  5.     s0 = sumujCyfry(i)
  6.     if (i <= max):
  7.       dane.append(s0)
  8.     if (i + s0 + dane[s0] == n):
  9.       print(i, end = ' ')

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.

C++C#
Python
  1. n = int(input("Podaj sumę do osiągnięcia\n n = "))
  2. print("Liczby spełniające równanie:")
  3. szukajLiczb(n)