Strona główna » Algorytmy » Artykuły » Ile dróg do sukcesu?
 

Ile dróg do sukcesu?

https://mattomatti.com/a0124

Zadanie

Znajdź ile jest sposobów na osiągnięcie pewnego wyniku wiedząc, że podczas każdego etapu można zdobyć 3, 5 lub 10 punktów. W rozwiązaniu nie rozróżniamy w jakiej kolejności były zdobywane punkty tj. czy w ostatecznej odpowiedzi zostało najpierw zdobyte 3 czy 5 punktów.

Implementacja

Rozwiązanie rekurencyjne

Idea

Zadanie można rozwiązać w sposób rekurencyjny. Każdy krok polegałby na odjęciu od aktualnej wartości docelowej kolejno 3, 5 i 10. W celu wyeliminowania rozpoznawania np. ścieżek (3, 5) i (5, 3) jako różnych należałoby dodać warunek, że w każdym kolejnym kroku zdobywamy nie więcej punktów niż w poprzednim. Tego typu rozwiązanie ma bardzo wysoką złożoność czasową, ponieważ w każdym kroku może dojść do rozwidlenia na trzy w każdym kroku co powoduje, że algorytm w najgorszym przypadku może być rzędu O(3n).

Kod

Funkcja ileSposobow() przyjmuje dwa argumenty: n - aktualna wartość do osiagnięcia oraz max - ile zostało odjęte w poprzednim kroku. Początkowo wartość max jest 10, aby nie ograniczać metody wyboru punktów algorytmowi. Oto jej kod:

  1. int ileSposobow(int n, int max = 10) {
  2.   if (n == 0) return 1;
  3.   if (n < 3) return 0;
  4.   int sposobow = 0;
  5.   if (max >= 3)
  6.     sposobow += ileSposobow(n - 3, 3);
  7.   if (max >= 5)
  8.     sposobow += ileSposobow(n - 5, 5);
  9.   if (max >= 10)
  10.     sposobow += ileSposobow(n - 10, 10);
  11.   return sposobow;
  12. }

(2.) Jeśli wskazana wartość n wynosi 0 to znaczy, że zostało znalezione rozwiązanie, a warunkiem stopu (3.) jest osiągnięcie wartości poniżej 3, mniejszej od 0. Mając wartości 3, 5 i 10 osiągnięcie 1 lub 2 jest niemożliwe. W dalszej części kodu (4.) rozpoczynamy zliczanie sposobów. (5. - 10.) Dla każdego możliwego rozwidlenia sprawdzamy czy w poprzednim kroku nie zostało wzięte mniej. Na koniec (11.) zostaje zwrócony obliczony wynik.

Programowanie Dynamiczne

Idea

Zadanie można rozwiązać w czasie liniowym. Idea polega na tym, że deklarujemy tablicę dla etapów od 0 do n włącznie. Początkowo przyjmujemy warunek, że na uzyskanie wartości 0 jest jeden sposób (tj. nie brać niczego). Następnie w tablicy oznaczamy, że wartość k możemy uzyskać na tyle sposobów więcej ile ma wartość k-3. Oczywiście uzupełnianie rozpoczyna się tak, aby nie wykroczyć poza granicę tabeli. Dla każdej wartości 3, 5 i 10 tablica jest uzupełniana oddzielnie.

Kod

Funkcja ileSposobow() przyjmuje tylko argument n - wartość do osiągnięcia. Oto kod:

  1. int ileSposobow(int n) {
  2.   if (n < 3) return 0;
  3.   int* tab = new int[n + 1];
  4.   for (int i = 0; i <= n; i++)
  5.     tab[i] = 0;
  6.   tab[0] = 1;
  7.   for (int i = 3; i <= n; i++)
  8.     tab[i] += tab[i - 3];
  9.   for (int i = 5; i <= n; i++)
  10.     tab[i] += tab[i - 5];
  11.   for (int i = 10; i <= n; i++)
  12.     tab[i] += tab[i - 10];
  13.   return tab[n];
  14. }

Na początku (2.) dla n<3 można zwrócić 0 bez obliczania czegokolwiek. Dla pozostałych przypadków: (3. - 5.) deklarujemy tablicę i uzupełniamy zerami prócz (6.) przyjętego warunku dla n = 0. W dalszej części (6. - 11.) uzupełniamy tablicę zgodnie z ideą. Na koniec (12.) zwracamy wartość zapisaną w ostatniej komórce tablicy.

Na początku (2.) dla n<3 można zwrócić 0 bez obliczania czegokolwiek. Dla pozostałych przypadków: (3. - 5.) deklarujemy tablicę i uzupełniamy zerami prócz (6.) przyjętego warunku dla n = 0. W dalszej części (6. - 11.) uzupełniamy tablicę zgodnie z ideą. Na koniec (12.) zwracamy wartość zapisaną w ostatniej komórce tablicy.

Na początku (2. - 3.) dla n<3 można zwrócić 0 bez obliczania czegokolwiek. Dla pozostałych przypadków: (4. - 5.) deklarujemy tablicę i uzupełniamy zerami prócz (6.) przyjętego warunku dla n = 0. W dalszej części (6. - 11.) uzupełniamy tablicę zgodnie z ideą. Na koniec (12.) zwracamy wartość zapisaną w ostatniej komórce tablicy.

Testowanie funkcji

Poniżej został przedstawiony fragment kodu, który pozwala przetestować użytkownikowi działanie funkcji ileSposobow():

  1. int main() {
  2.   int n;
  3.   cout << "Okresl wartosc do osiagniecia\n n = ";
  4.   cin >> n;
  5.   cout << ileSposobow(n);
  6.   system("pause");
  7.   return 0;
  8. }

Zadania

Zadanie 1

Napis funkcję ileSposobow(), która pozwoli na określenie wartości punktów możliwych do zdobycia w kolejnych etapach. Przyjmujemy, że na wejściu użytkownik podaje wartość docelową n oraz k, a następnie posortowaną listę k wartości. Przykładowo:

  1. 15 4
  2. 2 5 13 21