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

Liczby Skromne

Definicja

Liczba Skromna n to taka liczba naturalna, której cyfry można pogrupować w dwie liczby a i b w taki sposób, że złączenie a i b daje n oraz, że mod b = a.

Przykład

Najmniejszą liczbą Skromną jest 13, ponieważ można ją rozdzielić na a = 1 i b = 3. Liczby te spełniają nierówność 13 mod 3 = 1. Innym przykładem jest liczba 824. Można ją rozdzielić na a = 8 oraz b = 24. Wtedy 824 mod 24 = 8.

Ciąg liczb

Liczby Skromne można ustawić w następujący ciąg: 13, 19, 23, 26, 29, 39, 46, 49, 59, 69, 79, 89, 103, 109, 111, ..

Inne Informacje

Nie istnieją Liczby Skromne jednocyfrowe, ponieważ liczba wtedy skład się z jednej cyfry i nie ma możliwości podzielenia cyfr na dwie części.

Ciekawym faktem jest to, że dla liczb o co najmniej trzech cyfrach liczby o wszystkich cyfrach takich samych (różnych od zera) zawsze są liczbami skromnymi. W przypadku, gdy liczba składa się z cyfry c to ma postać L = c1...cn - 1cn. Dla takiej liczby a = c1, a b = c1c2...cn - 1. Ile razy liczba b zmieści się w L? Zawsze dokładnie 10 razy. Wtedy mod b = c. To kończy dowód.

Implementacja

Zadanie

Napisz program, który sprawdzi czy podana liczba jest liczbą Skromną. Przetestuj działanie programu dla kilku przypadków i pamiętaj o odpowiednich komunikatach.

Strategia rozwiązania

Podział Liczby Skromnej na dwie grupy niekoniecznie polega na wybraniu do a jednej cyfry, a do b wszystkie pozostałe. Z tego powodu należy rozpatrzeć wszystkie możliwe przypadki podziału. Dla liczby o n-cyfrach jest n - 1 możliwości podziału na dwie grupy.

W celu wybrania podziału liczby n na a i b w i-tej iteracji należy obliczyć w następujący sposób: oblicz L = 10i. Teraz na tego podstawie oblicz ze wzoru b = n mod L, a a = (n - b)/L. Podany wzór na a jest równoważny podzieleniu n przez L i odrzuceniu części ułamkowej.

Dla liczby 9243 program wykona kolejno następujące operacje. Na początek określamy, że potrzebne będą trzy iteracje, a oto ich obliczenia:

iLbaczy spełnia?
1109243 mod 10 = 39249243 mod 3 = 0 ≠ 924
21009243 mod 100 = 43929243 mod 43 = 41 ≠ 92
310009243 mod 1000 = 24399243 mod 243 = 9

Liczba 9243 spełnia dla podziału a = 9 i b = 243.

Rozwiązanie

Poniższa funkcja czySkromna() zwraca wartość logiczną, która stwierdza czy przekazany argument n jest Liczbą Skromną.

C++
C#
  1. bool czySkromna(int n) {
  2.   int dl = log10(n);
  3.   int mn = 10;
  4.   for (int i = 0; i < dl; i++) {
  5.     int a = n / mn;
  6.     int b = n % mn;
  7.     if (b != 0 && n % b == a)
  8.       return true;
  9.     mn *= 10;
  10.   }
  11.   return false;
  12. }

(2.) Oblicz ile jest możliwych podziałów i (3.) przygotuj mnożnik do wybierania cyfr. W celu zaoszczędzenia mocy obliczeniowej będzie on w każdej pętli aktualizowany, a nie wyliczany za każdym razem od nowa. (4.) Dla każdego podziału oblicz (5.) a i (6.) b, a potem (6. - 7.) jeśli warunek jest spełniony to zwróć prawdę. W przeciwnym razie (8.) zaktualizuj mnożnik i przejdź do następnej iteracji. Na koniec (10.) zwróć fałsz jeśli działanie funkcji nie zostanie przerwane wcześniej.

Złożoność powyższego algorytmu jest liniowa O(n), gdzie n to liczba cyfr w danej liczbie. Proces ten można zoptymalizować: patrz Zadanie 1.

Testowanie funkcji

W celu przetestowania napisanej funkcji można skorzystać z poniższego kodu, która wczyta liczbę od użytkownika, sprawdzi czy jest ona Skromna i wypisze stosowny komunikat.

C++
C#
  1. int main() {
  2.   int n;
  3.   cout << "Podaj liczbe do sprawdzenia:\n n = ";
  4.   cin >> n;
  5.   bool w = czySkromna(n);
  6.   cout << "Liczba " << (w ? "" : "nie ") << "jest Skromna";
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Zadanie 1

Zoptymalizuj proces wyszukiwania podziału. Skorzystaj z faktu, że n mod b < b. (Pozwala to w przybliżeniu przyśpieszyć działanie sprawdzania dwukrotnie.) Przetestuj działanie napisanego programu.