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 n 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 = c₁...c_n - 1c_n. Dla takiej liczby a = c₁, a b = c₁c₂...c_n - 1. Ile razy liczba b zmieści się w L? Zawsze dokładnie 10 razy. Wtedy L 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 = 10ⁱ. 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:

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ą.

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.

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. }

• Kod źródłowy Implementacja

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.

• Kod źródłowy Zadanie 1