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

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. static int SzukajLiczby(int min, int max)
  2. {
  3. int wynik = min;
  4. for (int i = (int)Math.Log10(max) + 1; i >= 0; i--)
  5. {
  6. int teraz = max / (int)Math.Pow(10, i) - 1;
  7. for (int j = 0; j < i; j++)
  8. {
  9. teraz = teraz * 10 + 9;
  10. }
  11. int iloczyn = IloczynCyfr(teraz);
  12. if (teraz < max && teraz > min
  13. && iloczyn > IloczynCyfr(wynik))
  14. {
  15. wynik = teraz;
  16. }
  17. }
  18. return wynik;
  19. }

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. static void Main(string[] args)
  2. {
  3. Console.Write("Podaj zakres\n min = ");
  4. int min = Convert.ToInt32(Console.ReadLine());
  5. Console.Write(" max = ");
  6. int max = Convert.ToInt32(Console.ReadLine());
  7. int wynik = SzukajLiczby(min, max);
  8. Console.WriteLine("Wynik to: " + wynik.ToString());
  9. Console.ReadKey();
  10. }