Strona główna » Algorytmy » Teoria Liczb » Liczby Kaprekara
 

Liczby Kaprekara

https://mattomatti.com/a79

Definicja

Liczby Kaprekara są podzbiorem liczby naturalnych. Ich właściwością jest fakt, że kwadrat liczby Kaprekara k można podzielić na dwie części, które po zsumowaniu wynoszą dokładnie k. Jednak prawa strona liczby nie może wynosić 0.

Przykład

Przykładowo liczbą Kaprekara jest k = 55, ponieważ jest liczbą Kaprekara.

Implementacja

Czy liczba Kaprekara?

Pierwszą funkcją, która zostanie zaimplementowana pozwoli sprawdzić czy dana liczba a ma przedstawione w definicji właściwości. W rozwiązaniu biblioteka cmath nie będzie wykorzystywana.

  1. bool czyKaprekar(int a) {
  2.   int a2 = a * a;
  3.   int mn = 10;
  4.   for (int i = 1; i <= policzCyfry(a2); i++) {
  5.     if (a2 / mn + a2 % mn == a && a2 % mn != 0) {
  6.       return true;
  7.     }
  8.     mn *= 10;
  9.   }
  10.   return false;
  11. }

(1.) Funkcja czyKaprekar() przyjmuje jeden argument a, który określa liczbę do sprawdzenia, a wynikiem jest wartość logiczna czy a jest liczbą Kaprekara. (2.) Wyliczenie kwadratu liczby a. (3.) Zmienna mn pozwoli wybierać odpowiednie fragmenty liczby. (4.) Dla każdego możliwego podziału liczby: (5.) policz sumą obu części i (6.) jeśli są równej liczbie podanej w argumencie to (7.) zwróć, że jest to liczba Kaprekara. (9.) Jeśli w danym kroku równość nie zaszła to pomnóż mn o 10. (11.) Po zakończeniu pętli, o ile nie została wcześniej zwrócona prawda, zostanie zwrócony fałsz.

W trakcie sprawdzania została wykorzystana funkcja policzCyfry(), która potrafi policzyć z ilu cyfr składa się przekazana do funkcji liczba:

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

Inne podejście

Funkcję sprawdzająca czy dana liczba jest liczbą Kaprekara można napisać bez funkcji zliczającej ile cyfr ma dana liczba. Pozwala na to fakt, że jeśli lewa strona liczby osiągnie 0 to nie ma sensu sprawdzanie dalszych podziałów, ponieważ lewa strona już zawsze będzie 0. Należy jednak pamiętać, że istnieje przypadek k = 1, gdzie .

  1. bool czyKaprekar(int a) {
  2.   int a2 = a * a;
  3.   int mn = 1;
  4.   while(a2 * 10 / mn != 0) {
  5.     if (a2 / mn + a2 % mn == a && a2 % mn != 0) {
  6.       return true;
  7.     }
  8.     mn *= 10;
  9.   }
  10.   return false;
  11. }

(1.) Nagłówek funkcji pozostaje niezmieniony. (2.) Wyliczenie kwadratu liczby a i (3.) ustalenie mnożnika mn. (4.) Dopóki lewa strona w poprzedniej iteracji nie była zerowa to (5.) sprawdź czy podczas tego podziału można stwierdzić czy liczba jest liczbą Kaprekara. Jeśli tak to (6.) zwróć prawdę. W przeciwnym wypadku (8.) zwiększ mnożnik mn. Tak samo jak w poprzedniej wersji funkcji jeśli pętla zostanie zakończona to należy (10.) zwrócić fałsz.

Testowanie funkcji

W celu wypisania wszystkich liczb Kaprekara z zakresu [1, 10000] można posłużyć się następującą funkcją main():

  1. int main () {
  2.   for (int i = 1; i < 10000; i++) {
  3.     if (czyKaprekar(i)) {
  4.       cout << i << endl;
  5.     }
  6.   }
  7.   system("pause");
  8.   return 0;
  9. }

Ćwiczenia

Zadanie 1

Napisz program, który po wczytaniu liczby k od użytkownika stwierdzi czy dana liczba jest liczbą Kaprekara. W przypadku, gdy liczba taką nie jest powinien zostać wyświetlony komunikat "To nie jest liczba Kaprekara". W przeciwnym wypadku program powinien wypisać, która z kolei jest dana liczba Kaprekara. Przykładowo liczba 45 jest 3 liczbą Kaprekara.