Strona główna » Algorytmy » Teoria Liczb » Maksymalny Iloczyn
 

Maksymalny Iloczyn

https://mattomatti.com/a0227

Zadanie

Napisz program, który dla podanego przedziału znajdzie liczbę, które iloczyn cyfr będzie największy. Przyjmujemy, że podany przedział jest poprawny i składa się z dwóch liczb naturalnych.

Przykład

Weźmy przykładowo zakres od 0 do 100. Liczbą o największym iloczynie cyfr jest 99. Zmieńmy zakres na 15 do 87. Wtedy największy iloczyn otrzymamy dla liczby 79. W przypadku zakresu [50, 50] wynikiem jest 50, ponieważ liczba jest spoza zakresu.

Analiza Problemu

W celu uzyskania jak największego iloczynu należałoby jak najwięcej pozycji zamienić na wartość 9, ponieważ jest to największa cyfra. Na pewno w docelowej liczbie nie ma potrzeby użycia 0 chyba, że nie ma innej możliwości. Strategia uzyskania największego iloczynu polega na sprawdzeniu wszystkich podziałów liczby na dwie części i zastąpienie prawej strony przez same cyfry 9. Jednak, aby liczba była realna należy lewą stronę zmniejszyć o 1. Przykładowo w liczbie 100 dzielimy na 1 | 99, a następnie zmniejszamy lewą stronę o 1. Otrzymujemy w ten sposób 99. Oczywiście każdą otrzymaną liczbę należy sprawdzić czy znajduje się w konkretnym zakresie. Jeśli nie to nie należy aktualizować wyniku! Dodatkowo warto zauważyć, że domyślnie zwracamy iloczyn cyfr maksimum.

Implementacja

Iloczyn Cyfr

Funkcja IloczynCyfr() zwraca dla podanej liczby a iloczyn jej cyfr. Dla liczb ujemnych zwracana jest wartość 0.

C++C#
Python
  1. def IloczynCyfr(a):
  2.   if a <= 0:
  3.     return 0
  4.   dl = math.log10(a) + 1
  5.   wynik = 1
  6.   while dl > 0:
  7.     wynik *= a % 10
  8.     a //= 10
  9.     dl -= 1
  10.   return wynik

Podczas wyliczania iloczynu cyfr należy pamiętać o kilku rzeczach: po pierwsze podana liczba nie musi być naturalna. Następnie należy uwzględni pomnożenie wszystkich cyfr przez siebie, a więc mnożenie dopóki liczba a jest większa od 0 zwróci niepoprawny wynik.

Iloczyn Cyfr

Do wyszukiwania liczby, która da największy iloczyn w podanym zakresie służy funkcja SzukajLiczby(), która przyjmuje jako argumenty zakres min oraz max.

C++C#
Python
  1. def SzukajLiczby(min, max):
  2.   wynik = min
  3.   for i in range(int(math.log10(max)) + 1, -1, -1):
  4.     teraz = max // int(math.pow(10, i)) - 1;
  5.     for j in range(0, i):
  6.       teraz = teraz * 10 + 9
  7.     iloczyn = IloczynCyfr(teraz)
  8.     if min < teraz < max and iloczyn > IloczynCyfr(wynik):
  9.       wynik = teraz
  10.   return wynik

Początkowo funkcja przyjmuje jako maksymalną wartość minimum, a następnie w pętli dzieli liczbę na dwie części poprzez wybór lewej i prawej strony. Lewa strona jest zmniejszana o jeden i do niej dopisywane jest tyle cyfr 9 ile cyfr ma prawa strona. Następnie obliczany jest iloczyn cyfr. Jeśli liczba znajduje się w zakresie i ma większy iloczyn niż dotychczasowy wynik to zostaje on zaktualizowany. Na koniec funkcja zwraca wynik.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu kodu, który wczyta zakres, a następnie wypisze szukaną liczbę.

C++C#
Python
  1. min = int(input("Podaj zakres\n min = "))
  2. max = int(input(" max = "))
  3. wynik = SzukajLiczby(min, max)
  4. print("Wynik to:", wynik)