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.

  1. int IloczynCyfr(int a) {
  2.   if (a < 0)
  3.     return 0;
  4.   int dl = (int)log10(a) + 1;
  5.   int wynik = 1;
  6.   while (dl > 0)
  7.   {
  8.     wynik *= a % 10;
  9.     a /= 10;
  10.     dl--;
  11.   }
  12.   return wynik;
  13. }

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.

  1. int SzukajLiczby(int min, int max) {
  2.   int wynik = min;
  3.   for (int i = log10(max) + 1; i >= 0; i--) {
  4.     int teraz = max / pow(10, i) - 1;
  5.     for (int j = 0; j < i; j++) {
  6.       teraz = teraz * 10 + 9;
  7.     }
  8.     int iloczyn = IloczynCyfr(teraz);
  9.     if (teraz < max && teraz > min
  10.         && iloczyn > IloczynCyfr(wynik)) {
  11.       wynik = teraz;
  12.     }
  13.   }
  14.   return wynik;
  15. }

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

  1. int main () {
  2.   int min, max;
  3.   cout << "Podaj zakres\n min = ";
  4.   cin >> min;
  5.   cout << " max = ";
  6.   cin >> max;
  7.   int wynik = SzukajLiczby(min, max);
  8.   cout << "Wynik to " << wynik;
  9.   system("pause");
  10.   return 0;
  11. }