Redukcja do Cyfry

Wstęp

Napisz algorytm, który pozwoli zredukować liczbę do jednej cyfry poprzez ciągłe sumowanie cyfr kolejnych wyników. Zastanów się jak możnaby napisać optymalny algorytm, który rozwiąże podane zadanie.

Implementacja

Bezpośrednia

Najprostsze rozwiązanie polega na napisaniu funkcji, która zsumuje wszystkie cyfry podanej liczby. Jeśli suma nie będzie cyfrą to proces ten powtarzamy, aż do uzyskania pojedynczej cyfry. Jest to bezpośrednie podejście, które pozwala na uzyskanie wyniku dla dowolnej liczby. Można to zaimplementować używając zarówno rekurencji jak i zwykłej pętli.

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

Zaletą powyższego kodu jest jego prostota - łatwo wyszczególnić kolejne etapy. Wadą jest jednak liniowy czas działania programu. Dla bardzo dużych liczb pewne jest to, że pętla wywoła się co najmniej dwa razy.

Szybka

Przyjrzyjmy się jednak poniższemu kodu funkcji RedukujLiczbe(). W tym przypadku wynik jest zwracany bezpośrednio po sprawdzeniu zaledwie dwóch warunków dla dowolnej liczby.

1. int RedukujLiczbe(int a) {
2.   if (a == 0) {
3.     return 0;
4.   }
5.   a = a % 9;
6.   return (a == 0) ? 9 : a;
7. }

Na pierwszy rzut oka wydaje się, że to niemożliwe, aby wszystkie powyższe operacje udało się zastąpić przy pomocy jednej operacji dzielenia (dokładniej modulo). Poniższy dowód powinien trochę wyjaśnić:

Dowód

Przyjmijmy, że liczba a jest dowolna i składa się z n cyfr. Możemy ją zapisać jako sumę cyfr a = 10^n-1c_n-1 + 10^n-2c_n-2 + .. + 10c₁ + c₀. Wykonajmy teraz operację modulo:
10^n-1c_n-1 + 10^n-2c_n-2 + .. + 10c₁ + c₀ = k (mod 9)
Stosując operację modulo na sumę stosujemy ją do każdego czynnika oddzielnie:
(10^n-1c_n-1 mod 9) + (10^n-2c_n-2 mod 9) + .. + (10c₁ mod 9) + (c₀ mod 9) = k (mod 9)
Jak wiadomo 10 mod 9 = 1. Podobnie będzie dla 100 mod 9 = 1 itd. W ten sposób znikną wszystkie 10^k, ale zostaną cyfry modulo 9:
(c_n-1 mod 9) + (c_n-2 mod 9) + .. + (c₁ mod 9) + (c₀ mod 9) = k (mod 9)
To z kolei będzie się równać:
a mod 9 = c_n-1 + c_n-2 + .. + c₁ + c₀ mod 9 = k mod 9

Testowanie funkcji

Do przetestowania powyższego kodu można skorzystać z poniższego fragmentu programu:

1. int main () {
2.   int a;
3.   cout << "Podaj liczbe:\n a = ";
4.   cin >> a;
5.   int wynik = RedukujLiczbe(a);
6.   cout << "Po redukcji otrzymujemy: " << wynik;
7.   system("pause");
8.   return 0;
9. }

• Kod źródłowy Bezpośrednia
• Kod źródłowy Szybka