Strona główna » Algorytmy » Artykuły » Ile kroków do celu?
 

Ile kroków do celu?

https://mattomatti.com/a0045

Zadanie

Zadana jest do przejścia pewna odległość x. Jednak podczas przechodzenia obowiązuje zasada, że w i-tym ruchu należy przejść odległość o długości i. Napisz program, który dla dowolnej, dodatniej odległości x znajdzie:

  1. ile najmniej kroków potrzeba, aby dojść do celu
  2. ile jest różnych tras

Przykłady

Załóżmy, że do przejścia jest odległość x = 3. Wystarczą wtedy dwa ruchy 2 + 1 = 3. Jednak już dla x = 4 sytuacja się nieco komplikuje, ponieważ najpierw trzeba się cofnąć o 1, a dopiero potem kolejno dwa roki wykonać do przodu. Wtedy -1 + 2 + 3 = 4.

Implementacja

Strategia

Zauważmy, że trasa do wybranego celu zawsze istnieje. Każdą dowolną odległość można pokonać przesuwając się o jeden. W tym przypadku jednak o 1 można przesunąć się tylko w pierwszym ruchu. Jednak różnica dwóch kolejnych liczb to 1, więc przechodząc do tyłu o n i do przodu o n + 1 to uzyskamy przejście o 1.

Podczas przesuwania należy pamiętać, że można się przesunąć o odległosć do przodu jak i do tyłu. Do szukania najkrótszej trasy jak również ile jest różnych tras warto zastosować rekurencję. W ten sposób zagwanrantowane zostanie znalezienie optymalnej trasy, albo wszystkich możliwych tras.

Najmniej kroków

Rozpocznijmy od struktury rekurencji. Po pierwsze potrzebny jest warunek stopu. W przypadku tego zadania można przyjąć, że jeśli wartość bezwzględna od miejsca startu jest większa niż odległość docelowa x to dalsze wyszukiwanie można pominąć. Oczywiście rekurencja zostanie przerwana w momencie, gdy osiągniemy żądaną odległość. Wtedy program ma za zadanie zwrócić ile kroków potrzebował i porównać z innym wynikami. Dla n kroków może być 2n - 1 różnych tras, ponieważ w każdym kroku decydujemy czy krok jest do przodu czy do tyłu.

Poniżej została przedstawiona przykładowa implementacja funkcju ileDoCelu(). Domyślnie przyjmuje jeden argument cel, który odpowiada odległości x. Następnie jest aktualna odległość aktualny, która stwierdza w jakiej odległości od początku aktualnie się znajdujemy oraz krok - wartość ostatniego wykonanego kroku.

  1. int ileDoCelu(int cel, int aktualny = 0, int krok = 0) {
  2.   if (abs(aktualny) > cel)
  3.     return INT_MAX;
  4.   if (aktualny == cel)
  5.     return krok;
  6.   int naLewo = ileDoCelu(cel, aktualny - krok - 1, krok + 1);
  7.   int naPrawo = ileDoCelu(cel, aktualny + krok + 1, krok + 1);
  8.   return naLewo < naPrawo ? naLewo : naPrawo;
  9. }

(2.) Na początku upewniamy się, że jesteśmy w odpowiedniej odległości. Jeśli nie to (3.) zwracamy największą możliwą wartość zmiennej, ponieważ nie zostanie ona wybrana podczas szukania najmniejszej odległości. Następnie (4.) sprawdzamy czy cel został osiagnięty. Jeśli tak to (5.) zwracamy ile kroków zostało wykonanych. Wystarczy zwrócić wartość krok, ponieważ określa ilość kroków ostatnio wykonanych. Jeśli rekurencja nie zostanie przerwana to należy obliczyć długość trasy po zrobieniu kroku (6.) do tyłu (w lewo) i (7.) do przodu (w prawo). Oczywiście należy (8.) zwrócić mniejszą wartość. W ten sposób szukana najkrótsza trasa zostaje znaleziona.

Ile tras?

Szukają wszystkich możliwych tras należy zauważyć, że jest ich nieskończenie wiele. Najpierw można przejść k razy do przodu lub do tyłu, a następnie przechodzić o 1 krok w odpowiednią stronę. Z tego powodu ograniczamy się jedynie do tras dla których wartość absolutna odległości od pozycji początkowej jest nie większa niż wartość docelowa x.

Struktura implementacji jest bardzo podobna jak w poprzednim przypadku:

  1. int ileTras(int cel, int aktualny = 0, int krok = 0) {
  2.   if (abs(aktualny) > cel)
  3.     return 0;
  4.   if (aktualny == cel)
  5.     return 1;
  6.   int w = 0;
  7.   w += ileTras(cel, aktualny - krok - 1, krok + 1);
  8.   w += ileTras(cel, aktualny + krok + 1, krok + 1);
  9.   return w;
  10. }

Tym razem zmieniają się wartości, które zwracamy. Dla (2.) niepoprawnej trasy (3.) zwrócimy 0, a z kolei po (4.) osiagnięciu punktu docelowego (5.) zwrócimy 1. (6. - 9.) Wszystkie uzyskane wartości należy zsumować. Tym razem chcemy wiedzieć ile jest tras, a nie jaka jest najkrótsza.

Testowanie funkcji

Przykładowo w celu wypisania jaka jest najmniejsza ilość kroków potrzebnych do przejścia pewnej odległości x wystarczy poniższy fragment kodu. Kod zadziała dla drugiej funkcji ileTras() jeśli zmieni się wywoływana funkcję.

  1. int main () {
  2.   int x;
  3.   cout << "Podaj odleglosc do przejscia\n x = ";
  4.   cin >> x;
  5.   cout << ileDoCelu(x) << endl;
  6.   system("pause");
  7.   return 0;
  8. }

Zadania

Zadanie 1

Napisz funkcję pokazTrasy(), która wypisze wszystkie prawidłowe trasy, którymi można przejść odległość x. Przetestuj działanie funkcji. Przykładowo dla odległości x = 3 istnieją następujące trasy:

  1. -1 2 -3 4 -5 6
  2. 1 -2 3 -4 5
  3. 1 2