Strona główna » Algorytmy » Artykuły » Dokładny Iloczyn Cyfr
 

Dokładny Iloczyn Cyfr

https://mattomatti.com/a0226

Zadanie

Dana jest pewna liczba naturalna. Znajdź najmniejszą, co najmniej dwucyfrową liczbę, której iloczyn cyfr będzie identyczny co dana liczba. Jeśli taka liczba nie istnieje to należy zwrócić wartość -1.

Przykład

Przykładowo dla liczby 12 jej odpowiednikiem będzie 26, ponieważ 2·6 = 12. Innym przykładem jest 64. Tej liczbie odpowiada 88, bo 8·8 = 64. Część liczb nie ma odpowiedników jak np. 13.

Analiza Zadania

Jeśli dana liczba a ma zostać wyrażona jako iloczyn co najmniej dwóch cyfr to znaczy, że musi być podzielna tylko przez cyfry od 1 do 9. Wynikowa liczba ma być jak najmniejsza, więc znalezione dzielniki należy ustawić od najmniejszej cyfry do największej. Warto pamiętać, że cyfra 1 nie zmieni wartości wyrażenia, więc nie powinna występować w zapisie! Wyjątkiem jest jednak przypadek, gdy trzeba ją dostawić, aby liczba była co najmniej dwucyfrowa. Po znalezieniu wszystkich dzielników należy sprawdzić czy ich iloczyn wynosi tyle co liczba.

Warto dodatkowo zauważyć, że odpowiednika nigdy nie będą mieć liczby, które są liczbą pierwszą lub są podzielne przez liczbę pierwszą większą od 9.

Implementacja

Poniższa funkcja SzukajLiczby() wyszykuje liczby, której iloczyn cyfr wyniesie tyle co dany argument a.

C++C#
Python
  1. def SzukajLiczby(a):
  2. w = 0
  3. mn = 1
  4. for i in range(9, 1, -1):
  5. while (a % i == 0):
  6. w += mn * i
  7. mn *= 10
  8. a //= i
  9. if (mn == 10):
  10. w += 10
  11. return w if a == 1 else -1

Funkcja na początek deklaruje dwie zmienne w do przechowywania aktualnego wyniku oraz mn - zmienna pomocnicza, aby dopisywać cyfry na początek wyniku. Następnie dla każdego potencjalnego dzielnika 9, 8, .., 2 sprawdzamy czy dzieli liczbę. Jeśli tak to należy dzielić liczbę przez niego tak długo, aż to możliwe. Wynik jest aktualizowany na bieżąco poprzez dodanie mnożnika mn razy znaleziony dzielnik. Oczywiście należy pamiętać, aby zaktualizować mnożnik i podzielić liczbę. Przed zwróceniem wyniku sprawdzamy czy ma odpowiednią długość. Jeśli nie to dodajemy 10 (tj. dostawiamy z przodu jedynką, która nie zmieni iloczynu). Na koniec, aby sprawdzić czy iloczyn cyfr jest równy liczbie przyrównujemy ją do 1. Wynika to z faktu, że w pętli była dzielona przez kolejne dzielniki.

Testowanie funkcji

W celu przetestowania napisanej funkcji można skorzystać z poniższego fragmentu kodu, który zapyta o liczbę, a następnie wypisze jej odpowiednik. Jeśli to jednak niemożliwe to wypisze stosowny komunikat.

C++C#
Python
  1. a = int(input("Podaj liczbę\n a = "))
  2. wynik = SzukajLiczby(a)
  3. if (wynik == -1):
  4. print("Nie istnieje odpowiadająca liczba!")
  5. else:
  6. print("Odpowiadająca liczba", wynik)