Wstęp do programowania / Ćwiczenia 2

To są ćwiczenia z rekurencji.

Zadanie 1 (Labirynt)

Czy istnieje droga miedzy wskazanymi punktami $(x_1,y_1)$ i $(x_2,y_2)$ w labiryncie reprezentowanym przez prostokątną tablicę liczb całkowitych A o rozmiarze n×m, zawierająca zera (droga) i jedynki (ściana)?

Wskazówka 1

W rozwiązaniu pojawia się funkcja-otoczka, która jako parametry ma (przekazywane przez zmienną) tablicę i 4 liczby opisujące początkowy i końcowy punkt drogi. Dzięki temu, że otoczka ma jako parametr tablicę, właściwa funkcja rekurencyjna już go nie potrzebuje, nie potrzebuje też parametrów określających punkt docelowy. Otoczka ponadto sprząta po funkcji rekurencyjnej (usuwa markowanie z tablicy), sprawdza czy nie startujemy/kończymy na ścianie lub poza tablicą.

Zapis rozwiązania bardzo się upraszcza jeśli założymy, że mamy ścianę dookoła labiryntu, jest to pewna forma strażnika.

Należy się też zastanowić, co by było, gdyby zamiast usuwać markowanie na końcu w otoczce, usuwać je lokalnie, wychodząc z rekurencji (tzn. gdy każde wywołanie startując markuje jedno pole i kończąc to pole odmarkowuje) (dalej by działało, ale z wykładniczym czasem). Należy wspomnieć o liniowym (wgl. wielkości danych, kwadratowym wzgl długości boku labiryntu) czasie rozwiązania i o innych możliwych rozwiązaniach (przeszukiwanie wszerz z kolejką).

Zadanie 2 (Z górki na pazurki)

W tablicy liczb całkowitych o rozmiarze n×m zapisana jest mapa gór (każdy punkt ma podaną dodatnią wysokość). Sprawdzić, czy da się przejść z punktu startowego do docelowego idąc:

• tylko w dół lub po płaskim
• tylko w dół

Wskazówka 1

W obu wariantach potrzebne jest markowanie (przez negację). W pierwszym zapobiega zapętleniu, w drugim czasowi wykładniczemu. Znów potrzebna jest funkcja otoczka.

Zadanie 3 (Wieże Hanoi z ograniczeniami)

Na wykładzie były wieże Hanoi. Ciekawa modyfikacja tego zadania polega na zabronieniu ruchów pomiędzy niektórymi pałeczkami, np. z pierwszej na drugą. Zapisac procedurę realizującą to zadanie przy zabronionych niektórych ruchach.

Uwagi: 1) Duzo latwiej rozwiazac to zadanie przy powyzszym sformułowaniu, niz gdy powie

   sie ze zabroniony jest konkretny ruch (np. 1-> 2).

2) Kiedy to zadanie ma jeszcze rozwiazanie (gdy na kazda wieze i z kazdej wiezy

   istnieje co najmniej jeden dozwolony ruch).

3) Jak reprezentowac dozwolone ruchy (TDozwRuchow = array[1..3, 1..3] of boolean,

   przekatna nie ma znaczenia).

4) Znow konieczna jest otoczka (dostarcza srodowisko pamietajace dozwolone ruchy,

   sprawdza czy w ogole istnieje rozwiazanie).

5) Algorytm:

   type Paleczki = 1..3;

   procedure Hanoi(Ile: integer; Skad, Dokad: Paleczki; Dozw:

TDozwRuchow);

     {...}
     procedure Rob(Skad, Dokad, Pom: Paleczki; Ile: Integer);
      begin
        {Pom oczywiscie jest rowne 6 - skad - dokad, ale chyba z

parametrem jest czytelniej}

        if Ile > 0 then
        begin
         if Dozw[Skad, Dokad]
         then
           begin
               Rob(Skad, Pom, Dokad, Ile-1);
               Przenies(Skad,Dokad);
               Rob(Pom, Dokad, Skad, Ile-1);
           end
         else
           begin
               Rob(Skad, Dokad, Pom, Ile-1);
               Przenies(Skad, Pom);
               Rob(Dokad, Skad, Ile-1);
               Przenies(Pom, Dokad);
               Rob(Skad, Dokad, Ile-1);
           end
      end;
 begin {Otoczka}
   ...
 end;

6) Jaki przypadek jest najgorszy i ile trzeba wykonac ruchow (gdy przerwane jest polaczenie

   Skad-Dokad w obie strony, 3^ile-1)

Zadanie 4 (Nawroty)

Napisz procedure znajdujaca wszystkie takie rozstawienia 8 hetmanow na

szachownicy, by zadne dwa hetmany sie nie atakowaly.

(rozwiazanie jest ladnie opisane w duzym Wirthcie 155-160, pamitamy w tablicach logicznych

zajetosc kolumn i obu rodzai przekatnych, kolejnego hetmana ustawiamy w

kolejnym

wierszu jesli sie da, jesli nie wracamy). Oczywiscie lepiej uogolnic na

N hetmanow na szachownicy

N*N.

Zadanie 5 (Mnozenie wielomianow stopnia n-1)

Dane sa dwie tablice (array[0..n-1] of real) reprezentujace dwa wielomiany. Nalezy obliczyc iloczyn tych wielomianow metoda dziel-i-zwyciezaj. Zakladamy, ze N jest potega dwojki.

Rozw.

Zamiast rozwiazania naiwnego wymagajacego n^2 mnozen zrobmy troche

lepsze

(aczkolwiek nie najlepsze) polegajace na podzieleniu wielomianow na
dwie czesci. Caly pomysl polega na spostrzezeniu, ze jesli zadane
wielomiany p(x) i q(x) podzielimy na dolna i gorna czesc (p(x) =
p_l(x) + p_h(x)*x^(n/2) i analogicznie q(x)), to ich iloczyn mozna
zapisac tak:
r_l(x)+(r_m(x)-r_l(x)-r_h(x))*x^(n/2)+r_h(x)*x^n, gdzie
r_l(x) = p_l(x)*q_l(x)
r_h(x) = p_h(x)*q_h(x)
r_m(x) = (p_h(x)+p_l(x))*(q_h(x)+q_l(x))
Czyli potrzebujemy 3 mnozen o polowe mniejszych wielomianow. W sumie
uzyskamy liczbe mnozen rzedu n^lg3. Szczegoly mozna znalezc w Sedgewick

Algorithms in C++ 527-530 (lub tegoz autora Algorithms in *)

Uwagi ogolne: - zwrocmy uwage na kolejnosc wyliczania wyrazen logicznych: standard Pascala jej nie definiuje,

 zatem AND moze byc liczony tak, ze najpierw liczy sie _oba_ argumenty

a dopiero potem podaje wynik

 (nie mozna zakladac krotkiego liczenia od lewej do prawej). Przy

wywolaniach rekurencyjnych

 to wazne szczegolnie, bo nie chodzi tylko (czy az) o poprawnosc (if

(i>1) and (tab[i]<>x) jest bledem)

 ale o efektywnosc (if droga(i-1,j) or droga(i+1,j) or ... jest

nieefektywne). - podkreslmy wage procedur otoczek: pozwalaja uzytkownikowi i nam widziec nasze procedury z takimi parametrami

 jakie sa potrzebne.

Zadanie 6 (Parser)

Dla zadanej poniżej gramatyki języka programowania (będącego uproszczoną wersją Pascala) napisz metodą zejść rekurencyjnych zestaw procedur weryfikujących poprawność programów zapisanych w tym języku. W przypadku napotkania błędu należy wypisać stosowny komunikat i zakończyć działanie. Należy założyć istnienie procedury GetSym(Symbol), która daje kolejny symbol (identyfikator, liczbę, operator (:=,<,>,<=,>=,=,<>), separator (;, ., (, ) ) z wejścia. Należy także zaprojektować odpowiedni typ danych do pamiętania symboli wejściowych.

Gramatyka: W opisie gramatyki występują następujące symbole:

 <nieterminal>
 terminal
 { coś }                                       wielokrotne (być może 0-krotne) wystąpienie cosia
 ->                                              rozdziela lewą część produkcji od prawej
 |                                                 rozdziela poszczególne produkcje

Jest to trochę roszerzona (o {}) gramatyka bezkontekstowa.

<program> -> <dekl> begin <ciąg instrukcji> end . <ciąg instrukcji> -> <instrukcja> { ; <instrukcja>} <deklaracja> -> var <zmienna> {, <zmienna>} ; <instrukcja> -> while <warunek> do <instrukcja> |

         if <warunek> then <instrukcja> else <instrukcja>   |
         begin <ciąg instrukcji> end                                      |

<zmienna> := <wyrażenie> <warunek> -> <składnik> {and <składnik>} <składnik> -> <czynnik> {or <czynnik>} <czynnik> -> true | false | not <czynnik> | <wyrażenie> <oprel> <wyrażenie> | ( <warunek> ) <wyrażenie> -> <zmienna> | <liczba> <oprel> -> < | <= | > | >= | <> | =

Rozw.

W tym zadaniu chodzi o przećwiczenie metody zejść rekurencyjnych (była na wykładzie). Niestety
na razie nie mamy dostatecznie ciekawych typów danych, żeby móc zapamiętać strukturę danych
programu (i np. po tem go wykonywać). Tym nie mniej zadanie jest pouczające. Typ danych który
ma być wymyślony to rekord z wariantami. Można uatrakcyjnić to zadanie każąc sprawdzać, czy każda
użyta zmienna była wcześniej zadeklarowana i czy nie była deklarowana kilkakrotnie (tablica
napisów).