Strona główna » Algorytmy » Artykuły » Zwycięski Rzut
 

Zwycięski Rzut

https://mattomatti.com/a0143

Zadanie

Rzucamy n kostkami o k ścianach. Ile jest możliwych przypadków, że na kostkach suma oczek wyniesie x? Zakładamy, że ściany kostki są ponumerowane od 1 do k. Rozwiąż zadanie stosując jak najbardziej optymalną metodę wyznaczenia rozwiązania.

Przykład

Przypuśćmy, że mamy n = 3 kostki sześcienne k = 6 (tj. po sześć ścian) i chcemy osiagnąć sumę x = 5. Można to zrobić na następujące sposoby:

Rzut 1Rzut 2Rzut 3
311
221
212
131
122
113

Jak można zauważyć rzucając trzema sześciennymi kostkami sumę x = 5 można osiągnąć na 6 różnych sposobów.

Analiza zadania

Szukanie wszystkich możliwych rozwiązań ze sprawdzaniem na sam koniec czy suma oczek jest odpowiednia rośnie potęgowo kn. Jak nietrudno się domyśleć nawet dla małych wartości n i k wartość ta zaczyna bardzo szybko rosnąć. Większość przypadków jest jednak identyczna, więc nie ma potrzeby wyznaczania tych samych wartości w kółko.

W przykładzie wyszło, że jest 6 różnych rozwiązań. Jednak jesli dobrze się przyjrzeć w rzeczywistości unikalnych zestawów oczek na kostkach są tylko dwa. Są to np. {2, 1, 2} oraz {1, 1, 3}. Generując wszystkie możliwe przestawienia elementów otrzymamy wszystkie 6 rozwiązań. W zadaniu nie interesuje nas jak wyglądają rozwiązanie, a tylko ile ich jest. Jak jednak najprościej wyznaczyć wszystkie takie grupy?

Najprostszą metodą jest umieszczenie w kodzie warunku, że każda kolejna liczba oczek jest taka sama lub mniejsza. To gwarantuje, że zostanie znalezione rozwiązanie {3, 1, 1}, ale nie {1, 3, 1} czy {1, 1, 3}. To znacząco ogranicza liczbę potrzebnych obliczeń. Ponadto warto pamiętać, że podczas losowanie każdej kolejnej kostki można sprawdzić czy jest możliwe osiągnięcie żądanej sumy. Jeśli nie to obliczenia można przerwać i przejść do następnego przypadku.

Przykład

W rozwiązaniu siłowym potrzebaby obliczyć sumę, aż 63 = 216 rozwiązań. Spróbujmy jednak ten problem ugryźć mając na uwadze podane wcześniej założenia.

Rzut 1Rzut 2Rzut 3Zostało
3--2, ok
33--1, przerywamy
32-0, ale nie w trzech rzutach, przerywamy
31-ok
3110, ok, doliczamy
2210, ok, doliczamy
2111, za mało, przerywamy
1--niemożliwe, bo maksymalna suma pozostała 2

W zależności od implementacji rzczywista liczba wywołań może się różnić, ale jak można zauważyć sprawdzanych rozwiązań jest znacząco mniej, bo tylko 3 (chodzi o sprawdzenia tylko dla 3 wykonanych rzutów) zamiast 216.

Rozwiązanie

Unikalne rozwiązanie

Jak wprowadzanie do pełnego rozwiązania rozpatrzmy prostszą funkcję, która policzy ile jest unikalnych rozwiązań. Funkcja liczRozwiazaniaUnikalne() optymalizuje proces wybierania kolejnych wyrzuconych oczek. Funkcja działa rekurencyjnie.

  1. int liczRozwiazaniaUnikalne(int n, int k, int x) {
  2.   if (n == 1)
  3.     return (x >= 1 && x <= k) ? 1 : 0;
  4.   else if (x < 0 || x < n || x > k*n)
  5.     return 0;
  6.   int ile = 0;
  7.   for (int i = min(x, k); i >= 1; i--)
  8.     ile += liczRozwiazaniaUnikalne(n - 1, i, x - i);
  9.   return ile;
  10. }

(2.) Jeśli została tylko jedna kostka do wyrzucenia to (3.) zwróć jeden jeśli pozostała suma x jest możliwa do wyrzucenia, a w przeciwnym 0. Dalsze obliczenia (4.) ograniczamy poprzez: sprawdzenie czy x jest nieosiągalny, bo jest ujemny, albo nie jest możliwe osiagnięcie sumy kontynuując rzuty wartości 1 lub wartości maksymalnych. W przypadku, gdy cel może zostać osiągnięty to: (6. - 8.) należy sprawdzić możliwe dalsze rzuty oczek i (9.) zwrócić ile zostało znalezionych rozwiązań. Warto tutaj zwrócić uwagę na to, że w każdym kolejnym wywołaniu zmniejszamy liczbę kostek n o 1, liczbę ścian ustawiamy na wartość ostatnio wyrzuconych oczek tj. i, a sumę x zmniejszamy o i oczek.

Wszystkie rozwiązania

Funkcja liczRozwiazania() będzie teraz liczyć ile jest możliwych rozwiązań licząc przekształcenia znalezionych unikalnych rozwiązań. Wykorzystane zostaną tutaj wzory z kombinatoryki. Jednak, aby móc z tego skorzystać trzeba pamiętać ile zostało wyrzuconych jakich oczek. Ze względu na to, że może być wyrzucone k różnych wartości to można zadeklarować tablicę liczników dla każdej z wartości.

  1. int liczRozwiazania(int n, int k, int x) {
  2.   int* liczniki = new int[k] {0};
  3.   int w = liczRozwiazania(n, k, x, liczniki, n, k);
  4.   delete liczniki;
  5.   return w;
  6. }

Ze względu na to, że potrzebna jest tablica liczników to główna funkcja ją deklaruje, zarządza nią i rozpoczyna wywołanie właściwej części funkcji liczRozwiazania(). W tej części została wykorzystana funkcja silnia() wyjaśniona tutaj.

  1. int liczRozwiazania(int n, int k, int x, int* liczniki, int _n, int _k) {
  2.   if (n == 1 && x >= 1 && x <= k) {
  3.     int w = silnia(_n);
  4.     liczniki[x - 1]++;
  5.     for (int i = 0; i < _k; i++)
  6.       w /= silnia(liczniki[i]);
  7.     liczniki[x - 1]--;
  8.     return w;
  9.   } else if (n == 1 || x < 0 || x < n || x > k*n)
  10.     return 0;
  11.   int ile = 0;
  12.   for (int i = min(x, k); i >= 1; i--) {
  13.     liczniki[i - 1]++;
  14.     ile += liczRozwiazania(n - 1, i, x - i, liczniki, _n, _k);
  15.     liczniki[i - 1]--;
  16.   }
  17.   return ile;
  18. }

(2.) Podobnie jak w poprzednim przypadku jeśli mamy ostatni rzut to sprawdzamy czy istnieje możliwe rozwiązanie. Jeśli tak to (3. - 7.) liczymy ile jest permutacji bez powtórzeń wylosowanych oczek i (8.) zwracamy obliczoną wartość. Jeśli jednak warunek nie jest spełniony to (9.) sprawdzamy czy dalsze obliczenia mają sens. Jeśli tak to (10. - 14.) wywołujemy kolejne rzuty kostek, ale pamiętając, że należy odpowiednio zwiększać liczniki. Na koniec wystarczy zwrócić wartość zmiennej ile.

Testowanie funkcji

W celu wczytania od użytkownika danych można posłużyć się poniższym fragmentem kodu:

  1. int main () {
  2.   int n, k, x;
  3.   cout << "Ile jest kostek?\n n = ";
  4.   cin >> n;
  5.   cout << "Ile scian maja kostki?\n k = ";
  6.   cin >> k;
  7.   cout << "Podaj sume oczek\n x = ";
  8.   cin >> x;
  9.   cout << "Znaleziono: " << liczRozwiazaniaUnikalne(n, k, x);
  10.   system("pause");
  11.   return 0;
  12. }