Strona główna » Algorytmy » Teoria Liczb » Trwałość liczb
 

Trwałość liczb

Wstęp

Trwałość liczby określamy jako ilość powtórzeń procesu, aby z danej liczby a uzyskać cyfrę. Proces polega na sumowaniu cyfr danej liczby. Podczas wyszukiwania trwałości dowolnej liczby a należy przeprowadzić sumowanie cyfr. Jeśli wynikiem nie jest cyfra to należy za a przyjąć wynik sumowania, a następnie powtórzyć instrukcje. Cyfra uzyskana na końcu wyliczania trwałości liczby nosi nazwę pierwiastka cyfrowego. Przyjmujemy, że wszystkie cyfry dane jako liczb a mają trwałość 0.

Przykład

Przyjmijmy, że liczba a = 123. Wtedy Pierwsze sumowanie zwróci 6. Oznacza to, że liczba ma trwałość 1, a jej pierwiastkiem cyfrowym jest 6. Jednak już w przypadku a = 9999 pierwsze sumowanie zwróci 36. Oznacza to, że trzeba jeszcze raz zsumować cyfry. W rezultacie otrzymujemy, że pierwiastkiem cyfrowym jest 9, a trwałość wynosi 2. Warto zauważyć, że liczba 20 i 10 mają trwałość 1, ale np. 19 ma trwałość 2.

Implementacja

Funkcja pomocnicza

Ze względu na fakt, że funkcja wyliczająca trwałość oraz pierwiastek cyfrowy będą korzystać z funkcji sumującej cyfry danej liczby to zostanie ona wyodrębniona jako oddzielna funkcja. Będzie ona nazywać się sumDigits() i będzie przyjmować jeden argument a, a zwracać będzie sumę cyfr danej liczby a.:

C++
C#
  1. int sumDigits(int a) {
  2.   int w = 0;
  3.   do {
  4.     w += a % 10;
  5.   } while ((a /= 10) > 0);
  6.   return w;
  7. }

(2.) Ustal sumę cyfr na 0. (3. - 5.) Dopóki istnieją cyfry do zsumowania to je dodaj. (6.) Na koniec zwróć sumę cyfr liczby a.

Trwałość

Wyliczanie trwałości będzie odbywać się przy pomocy rekurencji. Warunkiem zatrzymania będzie uzyskanie sumy cyfr liczby jako pojedynczej cyfry.

C++
C#
  1. int countPersistance(int a) {
  2.   if (a < 10)
  3.     return 0;
  4.   int w = sumDigits(a);
  5.   return 1 + ((w < 10) ? 0 : countPersistance(w));
  6. }

(2.) W przypadku podania cyfry należy (3.) zwrócić trwałość 0. (4.) Dla pozostałych liczb należy wyliczyć sumę cyfr, a następnie (5.) zwrócić, że sumowanie się odbyło i jeśli suma cyfr nie jest cyfrą to należy proces ponowić przekazując wyliczoną wartość.

Pierwiastek cyfrowy

W celu poruszenia szarych komórek szukanie pierwiastka cyfrowego nie odbędzie się rekurencyjnie, a poprzez użycie pętli do .. while.

C++
C#
  1. int countDigitalRoot(int a) {
  2.   do {
  3.     a = sumDigits(a);
  4.   } while (a >= 10);
  5.   return a;
  6. }

Testowanie funkcji

Napisane do tej pory funkcje można przetestować przy pomocy poniższego fragmentu kodu, która wczytuje od użytkownika liczbę a i wypisuje dla niej trwałość oraz pierwiastek cyfrowy.

C++
C#
  1. int main() {
  2.   int a;
  3.   cout << "Podaj liczbe do sprawdzenia\na = ";
  4.   cin >> a;
  5.   cout << "trwalosc: ";
  6.   cout << countPersistance(a);
  7.   cout << "\npierwiastek cyfrowy: ";
  8.   cout << countDigitalRoot(a) << endl;
  9.   system("pause");
  10.   return 0;
  11. }

Mniej obliczeń

Założenia

Warto zauważyć, że dla każdej liczby wykonywane są dwa razy dokładnie te same operacje. Z tego powodu warto utworzyć dodatkowy typ danych, który pomieści zarówno trwałość jak i pierwiastek. W ten sposób czas obliczeń dla dowolnej liczby a poprawi się dwukrotnie. W tym rozwiązaniu niezmieniona pozostaje funkcja sumDigits() do sumowania cyfr dowolnej liczby.

Struktura

Struktura musi jedynie zawierać dwa pola typu int. Prawidłowe opisania pozwoli później łatwiej wybrać dane ze zwróconego wyniku.

C++
C#
  1. struct persistance_data {
  2.   int persistance;
  3.   int digitalroot;
  4. };

Funkcja główna

Teraz główna funkcja będzie dalej przyjmować liczbę a, ale zwróci dane jako strukturę persistance.

C++
C#
  1. persistance_data checkPersistance(int a) {
  2.   persistance_data d;
  3.   d.persistance = 0;
  4.   if (a < 10) {
  5.     d.digitalroot = 0;
  6.   } else {
  7.     do {
  8.       d.persistance++;
  9.       a = sumDigits(a);
  10.     } while (a >= 10);
  11.     d.digitalroot = a;
  12.   }
  13.   return d;
  14. }

(2.) Zadeklaruj zmienną, która będzie przechowywać wynik i (3.) ustaw trwałość liczby na 0. (4.) Jeśli podane a to cyfra to (29.) ustaw pierwiastek cyfrowy na 0. Jednak (6.) dla każdej innej liczby a: (7. - 10.) wykonuj kolejne operacja sumowania cyfr, aż do uzyskania cyfry. W każdej iteracji należy pamiętać, aby zwiększyć atrybut trwałość w wyniku. (12.) Na koniec zwróć odpowiednią zmienną.

Testowanie funkcji

Po zmianie sposobu zwracania informacji należy delikatnie zmodyfikować program testujący:

C++
C#
  1. int main() {
  2.   int a;
  3.   cout << "Podaj liczbe do sprawdzenia\na = ";
  4.   cin >> a;
  5.   persistance_data d = checkPersistance(a);
  6.   cout << "trwalosc: ";
  7.   cout << d.persistance;
  8.   cout << "\npierwiastek cyfrowy: ";
  9.   cout << d.digitalroot << endl;
  10.   system("pause");
  11.   return 0;

Zadania

Zadanie 1

Napisz algorytm, który wypisze na ekran ciąg liczb, gdzie k-ta wypisana liczba będzie najmniejszą liczbą o trwałości k. Przetestuj działanie aplikacji dla trwałości 0, 1, 2 oraz 3. Prawidłowym wynikiem wypisanym na ekran powinno być:

  1. 0
  2. 10
  3. 19
  4. 199

Najmniejsza liczba o trwałości k = 4 wynosi 19999999999999999999999. Z tego powodu nie jest zalecane, aby testować program dla wartości k = 3, ponieważ pomimo długich obliczeń wartości liczb bardzo szybko przekroczą zakres podstawowych zmiennych.