Podzielność

Wstęp

Weźmy dwie dowolne liczby całkowite a i b. b jest dzielnikiem a wtedy i tylko wtedy, gdy iloraz a i b też jest liczbą całkowitą.

Dzielenie małych liczb nie jest problematyczne. Problemy pojawiają się z dużymi liczbami. Jednak jest szereg sztuczek, które potrafią pomóc, aby szybko określić czy liczba a dzieli się przez b. Tego typu sztuczki stosuje się raczej podczas liczenia na kartce niż podczas pisania programu, ponieważ moc komputerów pozwala na bezpośrednio sprawdzanie reszty z dzielenia a przez dowolne b tak jak to zostało pokazane poniżej:

1. bool _div(int a, int b) {
2.   return (a % b == 0);
3. }

Implementacja

Podzielność przez 2

Najprostsza i typowa implementacja wygląda następująca:

1. bool div2(int a) {
2.   return (a % 2 == 0);
3. }

Ostatnia liczba jest jedną z podanych na liście {0, 2, 4, 6, 8}.

1.   return (a % 10 == 0 || a % 10 == 2 || a % 10 == 4 || a % 10 == 6 || a % 10 == 8);

Jednak można tą regułę sformułować jako: ostatnia liczba jest parzysta:

1.   return ((a % 10) % 2 == 0);

Rzadko spotykanym, ale poprawnym rozwiązaniem w przypadku sprawdzania dzielenia przez dwa są operacje na bitach. Używając koniunkcji na podanej liczbie oraz 1 otrzymujemy tylko 1 bit, który odpowiada za parzystość. Jest to zdecydowania najszybsza metoda na sprawdzenie parzystości - nie jest wykonywane dzielenie.

1.   return ((a & 1) == 0);

Podzielność przez 3

Suma cyfr jest podzielna przez 3.

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

W podanym przykładzie (2.) deklarujemy dodatkową zmienną s, która odpowiada za sumę cyfr oraz (3.) która pobiera ostatnią cyfrę, dodaje do sumy i ucina ją i tak w kółko, aż liczba osiągnie 0. Na sam koniec (6.) sprawdzamy podzielność sumy przez 3.

Zadanie możemy rozwiązać metodą rekurencyjną. Najprostsza implementacja wyglądałaby tak:

1.   return (a > 0) ? div3b(a / 10, s + a % 10) : (s % 3 == 0);

Dwa poprzednie rozwiązania działają, ale mogą być niestabilne - w obu wciąż może dojść do próby dzielenia większej liczby niż to co przewiduje najbardziej pojemna zmienna. Można to poprawić dodając dodatkowo warunek, że jeżeli liczba jest większa od 10 to ma ponownie zsumować cyfry, aż uzyskamy liczbę mniejszą niż 10.

1. bool div3c(int a, int s = 0) {
2.   return (a > 0) ? div3b(a / 10, s + a % 10) : (s > 9) ? div3b(s) : (s % 3 == 0);
3. }

Podzielność przez 4

Ostatnie dwie liczby są podzielne przez 4.

1. bool div4(int a) {
2.   return ((a % 100) % 4 == 0);
3. }

Podzielność przez 5

Ostatnia liczba jest jedną z podanych na liście {0, 5}.

1. bool div5a(int a) {
2.   return (a % 10 == 0 || a % 10 == 5);
3. }

Jednak tak samo jak w przypadku sprawdzania podzielności przez 2 - o wiele lepiej jest sprawdzić pobraną cyfrę funkcją modulo:

1. bool div5b(int a) {
2.   return ((a % 10) % 5 == 0);
3. }

Podzielność przez 6

6 to liczba złożona 6 = 2 * 3, więc musi być podzielna przez 2 i 3. Najlepszym sposobem jest wykorzystanie dotychczas stworzonych funkcji:

1. bool div6(int a) {
2.   return (div2(a) && div3(a));
3. }

Podzielność przez 7

Podwojona ostatnia cyfra i odjęta od reszty liczby da 0 lub liczbę podzielną przez 7.

1. bool div7a(int a) {
2.   return (((a / 10) - 2 * (a % 10)) == 0 || ((a / 10) - 2 * (a % 10)) % 7 == 0);
3. }

Definicja podzielności jest prawidłowa, ale wystarczy ją nieco uogólnić, aby poprawić kod. W przypadku 0%7 zawsze otrzymamy 0:

1. bool div7b(int a) {
2.   return (((a / 10) - 2 * (a % 10)) % 7 == 0);
3. }

Podzielność przez 8

Trzy ostatnie liczby muszą być podzielne przez 8. Biorąc pod uwagę podzielność przez 4 łatwo zauważyć, że dla podzielności 2ⁿ należy pobrać n ostatnich cyfr i sprawdzić ich podzielność przez 2ⁿ. Wtedy dla podzielności przez 8 kod będzie wyglądał następująco:

1. bool div8(int a) {
2.   return ((a % 1000) % 8 == 0);
3. }

Podzielność przez 9

Suma cyfr liczby jest podzielna przez 9. Warto tutaj wykorzystać szkielet funkcji stworzony na potrzeby sprawdzenia podzielności przez 3 i zmianę w (7.) linijce sprawdzenia podzielności.

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

Do wykonania tego zadania można wykorzystać nie tylko metodę iteracji, ale również rekurencji:

1. bool div9b(int a, int s = 0) {
2.   return (a > 0) ? div9b(a / 10, s + a % 10) : (s > 9) ? div9b(s) : (s % 9 == 0);
3. }

Podzielność przez 10

Ostatnia cyfra to 0. Kod powinien być oczywisty:

1. bool div10(int a) {
2.   return (a % 10 == 0);
3. }

Podzielność przez 11

Suma co drugiej liczby i odjęcie sumy pozostałych cyfry da 0 lub liczbę podzielną przez 11.

Wykorzystamy tu szkielet funkcji na podzielność przez 3, ale dodamy drugą zmienną zliczającą oraz zmienną logiczną, która będzie wskazywała do której zmiennej należy dodać aktualnie cyfrę.

1. bool div11a(int a) {
2.   int s = 0, s2 = 0;
3.   bool u = false;
4.   while (a > 0) {
5.     if (u)
6.       s += a % 10;
7.     else
8.       s2 += a % 10;
9.     a /= 10;
10.     u = !u;
11.   }
12.   return ((s - s2) % 11 == 0);
13. }

Jest to moment w którym możemy wykorzystać znajomość funkcji swap(), aby co pętle zmieniać pozycję zmiennych. Dzięki temu nie musimy deklarować zmiennej logicznej i pisać dwóch linijek na dodawanie.

1. bool div11b(int a) {
2.   int s = 0, s2 = 0;
3.   while (a > 0) {
4.     swap(s, s2);
5.     s += a % 10;
6.     a /= 10;
7.   }
8.   return ((s - s2) % 11 == 0);
9. }

Z drugiej strony rozwiązywanie rekurencyjne pozwala na zamianę miejscami zmiennych przy kolejnych wywołaniach dzięki czemu kod staje się jeszcze bardziej przejrzysty:

1. bool div11c(int a, int s = 0, int s2 = 0) {
2.   return (a > 0) ? div11c(a / 10, s2 + a % 10, s) : ((s - s2) % 11 == 0);
3. }

Podzielność przez 12

Liczba jest podzielna przez 3 i 4. Tutaj warto zwrócić uwagę, że 12 jest kolejną nie pierwszą liczbą co powoduje, że należy wywołać odpowiednie testy na podzielność przez liczby pierwsze.

1. bool div12(int a) {
2.   return (div3(a) && div4(a));
3. }

Testowanie funkcji

Podsumowując, istnieje wiele sposobów na sprawdzanie podzielności. Wiele z nich można zastosować mając liczbę przechowywaną w postaci łańcuchu znaków. Dla chętnych, w celu sprawdzenia poprawności rozwiązań zamieszczam cały kod źródłowy.

1. string msg(bool a) {
2.   return (a) ? "TAK" : "NIE";
3. }
5. int main() {
6.   for (int i = 0; i < 100; i++) {
7.     cout << i << " " << msg(div11b(i)) << endl;
8.   }
9.   system("PAUSE");
10.   return 0;
11. }

• Kod źródłowy Implementacja