Maksymalny Iloczyn

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

• Kod źródłowy Implementacja