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ą. Zapisać procedurę realizującą to zadanie przy zabronionych niektórych ruchach.

Wskazówka 1

1. Dużo łatwiej rozwiązać to zadanie przy powyższym sformułowaniu, niż gdy powie sie ze zabroniony jest konkretny ruch (np. 1-> 2).
2. Kiedy to zadanie ma jeszcze rozwiązanie (gdy na każdą wieżę i z każdej wieży istnieje co najmniej jeden dozwolony ruch).
3. Jak reprezentować dozwolone ruchy (TDozwRuchow = array[1..3, 1..3] of boolean, przekątna nie ma znaczenia).
4. Znów konieczna jest otoczka (dostarcza środowisko pamiętające dozwolone ruchy, czy w ogóle istnieje rozwiązanie).
5. Jaki przypadek jest najgorszy i ile trzeba wykonac ruchów (gdy przerwane jest połączenie Skąd-Dokąd w obie strony: 3^ile-1)

Rozwiązanie 1

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
      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; {Rob}
begin {Hanoi}
  ...
end; {Hanoi}

Zadanie 4 (Ustawianie hetmanów)

Napisz procedurę znajdująca wszystkie takie rozstawienia 8 hetmanów na szachownicy, by żadne dwa hetmany się nie atakowały.

Wskazówka 1

Rozwiązanie jest ładnie opisane w dużym Wirthcie 155-160. W tablicach logicznych pamiętamy zajętość kolumn i obu rodzajów przekątnych, kolejnego hetmana ustawiamy w kolejnym wierszu jeśli się da, jeśli nie wracamy.

Oczywiście lepiej uogólnić na N hetmanów na szachownicy N×N.

Zadanie 5 (Mnożenie wielomianów stopnia n-1)

Dane są dwie tablice (array[0..n-1] of real) reprezentujące dwa wielomiany. Należy obliczyć iloczyn tych wielomianów metodą dziel-i-zwyciężaj. Zakładamy, że N jest potęgą dwójki.

Wskazówka 1

Zamiast rozwiązania naiwnego wymajającego $n^2$ mnożeń zróbmy trochę lepsze (aczkolwiek nie najlepsze) polegające na podzieleniu wielomianów na dwie części. Cały pomysł polega na spostrzeżeniu, że jeśli zadane wielomiany $p(x)$ i $q(x)$ podzielimy na dolna i górną część
$p(x)=p_l(x)+p_h(x)*x^{n/2}$ i analogicznie $q(x)=q_l(x)+q_h(x)*x^{n/2}$, to ich iloczyn można zapisać tak:
$p(x)*q(x)=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 mnożeń o polowe mniejszych wielomianów. W sumie uzyskamy liczbę mnożeń rzędu $n^{lg3}$. Szczególny można znaleźć w Sedgewick Algorithms in C++ 527-530.

Uwagi ogólne:

• zwróćmy uwagę na kolejność wyliczania wyrażeń logicznych: standard Pascala jej nie definiuje, zatem AND może być liczony tak, ze najpierw liczy sie _oba_ argumenty a dopiero potem podaje wynik (nie można zakładać krótkiego liczenia od lewej do prawej). Przy wywołaniach rekurencyjnych to ważne szczególnie, bo nie chodzi tylko (czy aż) o poprawność (if (i>1) and (tab[i]<>x) jest błędem) ale o efektywność (if droga(i-1,j) or droga(i+1,j) or ... jest nieefektywne).
• podkreślmy wagę procedur otoczek: pozwalają użytkownikowi i nam widzieć nasze procedury z takimi parametrami jakie są 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ę rozszerzona (o nawiasy klamrowe { } ) gramatyka bezkontekstowa.

<program>	→	<deklaracja> 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>	→	< | <= | > | >= | <> | =

Wskazówka 1

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).