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:

C++C#
Python
  1. def ileSposobow(n, max=10):
  2.   if (n == 0):
  3.     return 1;
  4.   if (n < 3):
  5.     return 0;
  6.   sposobow = 0;
  7.   if (max >= 3):
  8.     sposobow += ileSposobow(n - 3, 3);
  9.   if (max >= 5):
  10.     sposobow += ileSposobow(n - 5, 5);
  11.   if (max >= 10):
  12.     sposobow += ileSposobow(n - 10, 10);
  13.   return sposobow;

(2. - 3.) Jeśli wskazana wartość n wynosi 0 to znaczy, że zostało znalezione rozwiązanie, a warunkiem stopu (4. - 5.) 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 (6.) rozpoczynamy zliczanie sposobów. (7. - 12.) Dla każdego możliwego rozwidlenia sprawdzamy czy w poprzednim kroku nie zostało wzięte mniej. Na koniec (13.) 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:

C++C#
Python
  1. def ileSposobow(n):
  2.   if (n < 3):
  3.     return 0;
  4.   tab = [0] * (n + 1)
  5.   tab[0] = 1
  6.   for i in range(3, n + 1):
  7.     tab[i] += tab[i - 3]
  8.   for i in range(5, n + 1):
  9.     tab[i] += tab[i - 5]
  10.   for i in range(10, n + 1):
  11.     tab[i] += tab[i - 10]
  12.   return tab[n]

Testowanie funkcji

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

C++C#
Python
  1. n = int(input('Określ wartości do osiągnięcia\n n = '))
  2. print(ileSposobow(n))

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