Liczby Wampiryczne

Definicja

Liczba Wampiryczna jest to taka liczba a, która ma parzystą liczbę cyfr. Na podstawie cyfr liczby a można utworzyć dwie liczby x i y, długości równej połowie długości liczby a. Pomnożone przez siebie dają a. Wartości x i y są nazywane kłami (ang. fang).

Przykład

Najmniejszą liczbą Wampiryczną jest 1260, ponieważ z cyfr tej liczby można utworzyć x = 21 oraz y = 60. Iloczyn x i y jest to liczba 1260. Liczby Wampiryczne mogą mieć więcej niż jeden zestaw x i y. Przykładem takiej liczby jest 125460. Z jej cyfr można utworzyć pary (x, y) = {(204, 615), (246, 510)}.

Implementacja

Poniżej zostały przedstawione dwa sposoby na sprawdzenie czy liczba a jest liczbą Wampiryczną. Pierwsze z nich ma podejście kombinatoryczne, które okazują się mało efektywne dla coraz to większych liczb. Drugie podejście wykorzystuje zależności matematyczne, aby zoptymalizować proces sprawdzania.

Podejście kombinatoryczne

Z definicji wynika, że liczby x i y mają te same cyfry co a, dlatego można sprawdzić wszystkie kombinacje ułożenia cyfr liczby a. Dla każdej kombinacji następnie należy pomnożyć dwie części liczby a po rozsunięciu ich w połowie. Metoda ta nie jest niestety efektywna, ponieważ w trakcie poszukiwania rozwiązania należy przejrzeć n! przypadków.

Główna funkcja

Zgodnie ze strategią funkcja czyWampiryczna() ma wstępnie sprawdzić czy liczba będzie miała jakiekolwiek szanse.

1. bool czyWampiryczna(int a) {
2.   int dl = log10(a) + 1;
3.   if (dl % 2 == 0) {
4.     int* data = new int[dl];
5.     int kopia_a = a;
6.     for (int i = dl - 1; i >= 0; i--) {
7.       data[i] = kopia_a % 10;
8.       kopia_a /= 10;
9.     }
10.     bool wynik = szukajKombinacji(a, data, dl);
11.     delete data;
12.     return wynik;
13.   }
14.   return false;
15. }

(2.) Oblicz długość liczby a. (3.) Dalsze sprawdzanie przeprowadź tylko, gdy długość jest parzysta. (Jeśli jest nieparzysta to (14.).) Utwórz (4. - 9.) listę cyfr liczby a. (10.) Rozpocznij poszukiwania jakiejkolwiek prawidłowej kombinacji i zapamiętaj wynik. (11.) Zdealokuj listę i (12.) zwróć wynik.

Szukanie kombinacji

Poszukiwanie kombinacji przeprowadza funkcja szukajKombinacji(), która potrzebuje a - sprawdzaną liczbę, data - listę cyfr, dl - długość liczby oraz i, który element jest aktualnie ustalany.

1. bool szukajKombinacji(int a, int* data, int dl, int i = 0) {
2.   if (i == dl) {
3.     if (data[0] == 0 && data[dl/2] == 0)
4.       return false;
5.     int fanga = odczytajLiczbe(data, 0, double(dl) / 2);
6.     int fangb = odczytajLiczbe(data, double(dl) / 2, double(dl) / 2);
7.     return (fanga * fangb == a);
8.   }

(2.) Jeśli program uzyskał pełną kombinacje to (3.) sprawdź czy obie liczby mają długość równej połowie długości liczby a. Jeśli nie to (4.) zwróć, że kombinacja jest nieprawidłowa. W przeciwnym wypadku (5. - 6.) pobierz obie liczby z kombinacji i (7.) zwróć wynik porównania pomnożenia pobranych wartości oraz liczby a.

9.   else {
10.     for (int j = i; j < dl; j++) {
11.       zamienDane(data, i, j);
12.       if (szukajKombinacji(a, data, dl, i + 1))
13.         return true;
14.       zamienDane(data, i, j);
15.     }
16.   }
17.   return false;
18. }

(9.) W przypadku, gdy trwa poszukiwanie kombinacji (nie wszystkie pola zostały ustalone) to: (10. - 15.) ustal kolejny element i ponownie (12.) wywołaj szukajKombinacji() z nowymi danymi. Tylko jeśli funkcja zwróci prawdę to (13.) też zwróć prawdę. Jeśli zostały sprawdzone wszystkie kombinacje i nie została zwrócona prawda to (17.) zwróć fałsz.

Funkcje pomocnicze

W trakcie pisania powyższego rozwiązania zostały użyte dwie funkcje pomocnicze. Pierwsza z nich zamienDane() zamieniała dwie wartości na liście.

1. void zamienDane(int* data, int poz1, int poz2) {
2.   int temp = data[poz1];
3.   data[poz1] = data[poz2];
4.   data[poz2] = temp;
5. }

Druga funkcja pomocnicza pomaga odczytać dl kolejnych wartości z podanej listy data począwszy od pozycji poz:

1. int odczytajLiczbe(int* data, int poz, int dl) {
2.   int a = 0;
3.   for (int i = poz; i < poz + dl; i++)
4.     a = (a * 10) + data[i];
5.   return a;
6. }

Podejście matematyczne

Istnieje możliwość optymalizacji poprzedniego rozwiązania. Po pierwsze nie ma potrzeby sprawdzania wszystkich kombinacji. Można wyznaczyć wszystkie dzielniki liczby a, które mają długość równą połowie długości a. Czyli dla liczby długości 2k należy znaleźć dzielniki w przedziale [10^{k - 1}, 10^k).

Ponadto w takim przypadku wystarczy policzyć ile jest każdej cyfry w liczbie a oraz w znalezionych liczbach x i y. To pozwala zaoszczędzić pamięć poprzez uniezależnienie długości listy od długości liczby a. (W podejściu kombinatorycznym wykorzystanie pamięci rosło liniowo).

Główna funkcja

1. bool czyWampiryczna(int a) {
2.   int dl = dlugoscLiczby(a);
3.   if (dl % 2 == 0) {
4.     int dlpol = dl / 2;
5.     int* cyfry = listaCyfr(a);
6.     int zakres_od = pow(10, dlpol - 1);
7.     int zakres_do = pow(10, dlpol);
8.     if (zakres_od == 0)
9.       zakres_od++;

(2.) Policz długość liczby a i (3.) sprawdź czy ma parzystą liczbę cyfr. (4.) W celu uproszczenia zapisu oblicz połowę liczby dl. (5.) Utwórz listę cyfr liczby a i (6. - 7.) wyznacz przedział w którym będą szukane dzielniki liczby a. (8.) Sprawdź czy zakres nie rozpoczyna się od zera. Jeśli tak to (9.) większy dolny zakres.

1.     for (; zakres_od < zakres_do; zakres_od++) {
2.       if (a % zakres_od == 0 && dlugoscLiczby(a / zakres_od) == dlpol) {
3.         int rozw = (zakres_od * pow(10, dlpol)) + (a / zakres_od);
4.         int* cyfry_rozw = listaCyfr(rozw);
5.         bool wynik = true;
6.         for (int i = 0; i < 10; i++)
7.           wynik &= (cyfry[i] == cyfry_rozw[i]);
8.         delete cyfry_rozw;
9.         if (wynik) {
10.           delete cyfry;
11.           return wynik;
12.         }
13.       }
14.     }
15.     delete cyfry;
16.   }
17.   return false;
18. }

Następnie (10.) dla każdej liczby z zakresu (11.) sprawdź czy jest ona dzielnikiem a oraz czy jej długość to połowa długości a. Jeśli tak to (12.) Wyznacz liczbę, która jest złożeniem znalezionych wartości x = dzielnik oraz y = a / dzielnik. (13.) Policz ile jest każdej z cyfr. (14.) Przypuść, że jest tyle samo każdej z cyfr w a co w znalezionym rozkładzie. (15. - 16.) Porównaj ilości cyfr a i rozw. (17.) Dealokuj pamięć potrzebną pod cyfry znalezionego rozkładu. (18.) Jeśli wynik jest prawdziwy to (19.) zdealokuj pamięć i (20.) zwróć wynik (tj. prawdę). Jeśli jednak po przejrzeniu całego zakresu nie znajdzie się ani jedna para to (24.) usuń informacje o liczbie a i (26.) zwróć fałsz.

Funkcje pomocnicze

W celu uproszczenia kodu napisana została funkcja listaCyfr(), która dla danej liczby a zwraca listę, która zawiera ile sztuk każdej cyfry ma liczba a.

1. int* listaCyfr(int a) {
2.   int* cyfry = new int[10];
3.   for (int i = 0; i < 10; i++)
4.     cyfry[i] = 0;
5.   do {
6.     cyfry[a % 10]++;
7.     a /= 10;
8.   } while (a > 0);
9.   return cyfry;
10. }

Ze względu na wykorzystanie w dwóch miejscach obliczanie długości liczby też zostało zapisane jako oddzielna funkcja dlugoscLiczby():

1. int dlugoscLiczby(int a) {
2.   return log10(a) + 1;
3. }

Porównanie złożoności

Obydwie metody prawidłowo wypisują kolejne liczby wampiryczne. Warto zwrócić uwagę, że drugie rozwiązanie działa ponad 10 razy szybciej od pierwszego. Pierwsze rozwiązanie kombinatoryczne wykonuje dla sprawdzanej liczby n! sprawdzeń utworzonej kombinacji. Druga funkcja działa szybciej, ponieważ sprawdza jedynie określony zakres i nie zgaduje dzielników a, a je wyznacza. Nawet zakładając, że co druga wartość zakresu to dzielnik to zostanie wykonane maksymalnie wykonane porównań.

W tabeli dla Metody I zostały wypisane ile zostało znalezionych kombinacji do sprawdzenia. W metodzie II odpowiednikiem jest ilość pierwszych dzielników liczby a.

Jak widać Metoda II okazuje się początkowo mniej efektywna niż Metoda I. Jednak bardzo szybko się okazuje, że Metoda II może być nawet 433 razy szybsza dla liczb 10 cyfrowych!

Testowanie funkcji

W celu wypisania wszystkich liczb Wampirycznych z przedziału [1, 200000] wystarczy poniższa funkcja main().

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

• Kod źródłowy Podejście kombinatoryczne
• Kod źródłowy Podejście matematyczne

Zadania

Zadanie 1

Napisz program, który wczyta od użytkownika liczbę a, a następnie wypisze pary liczb, które świadczą o tym, że a jest wampiryczna. Jeśli liczba a nie jest wampiryczna to należy wypisać na ekran stosowny komunikat.

Przykładowo dla liczby 125460 zostanie wypisane:

1. 125460 = 204*615 = 246*510

• Kod źródłowy Zadanie 1