Wstęp do programowania / Ćwiczenia 2: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
(Dolozenie zadania o rozkladzie na skladniki, wywalenie parsera)
(Hetmany)
Linia 326: Linia 326:
 
'''Wskazówka 1'''  
 
'''Wskazówka 1'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
W tablicach logicznych pamiętamy zajętość kolumn i obu rodzajówprzekątnych, kolejnego hetmana ustawiamy w kolejnym wierszu jeśli sięda, jeśli nie wracamy.  
+
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.  
  
 
Rozwiązanie jest ładnie opisane w [[dużym Wirthcie]], str. 155-160.  
 
Rozwiązanie jest ładnie opisane w [[dużym Wirthcie]], str. 155-160.  
Linia 337: Linia 337:
 
'''Rozwiązanie 1'''  
 
'''Rozwiązanie 1'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 +
'''procedure''' Hetmany(N:integer);
 +
// N >= 1
 +
'''var'''
 +
  wiersze:'''array'''[1..N] '''of''' integer;
 +
  kolumny:'''array'''[1..N] '''of''' boolean;
 +
  przekgd:'''array'''[-(N-1)..N-1] '''of''' boolean; // przekątne \ o stałej różnicy
 +
  przekdg:'''array'''[2..2*N] '''of''' boolean;      // przekątne / o stałej sumie
 +
 
 +
  '''procedure''' ustaw(k,i:integer);
 +
  // 1 <= k,i <= N
 +
  '''begin'''
 +
    wiersze[k]:=i;
 +
    kolumny[i]:=true;
 +
    przekgd[k-i]:=true; 
 +
    przekdg[k+i]:=true; 
 +
  '''end'''; // ustaw
 +
 
 +
  '''procedure''' odstaw(k,i:integer);
 +
  // 1 <= k,i <= N
 +
  '''begin'''
 +
    wiersze[k]:=0;
 +
    kolumny[i]:=false;
 +
    przekgd[k-i]:=false; 
 +
    przekdg[k+i]:=false; 
 +
  '''end'''; // odstaw
 +
   
 +
  '''function''' wolne(k,i:integer):boolean
 +
  // 1 <= k,i <= N
 +
  '''begin'''
 +
    wolne:='''not''' kolumny[i] & '''not''' przekgd[k-i] & '''not''' przekdg[k+i]
 +
  '''end'''; // wolne
 +
 +
  '''var''' jest:boolean;
 +
 +
  '''procedure''' wypisz;
 +
  '''var''' i:integer;
 +
  '''begin'''
 +
    jest:=true;
 +
    write('Ustawienie: ')
 +
    '''for''' i:=1 '''to''' N; '''do''' write(i,':',wiersze[i],' ')
 +
    writeln;
 +
  '''end'''; // wypisz
 +
 +
  '''procedure''' rozstaw(k:integer);
 +
  '''var''' i:integer;
 +
  '''begin'''
 +
    '''if''' k=N+1 '''then'''
 +
      wypisz
 +
    '''else'''
 +
      '''for''' i:=1 '''to''' N '''do'''
 +
        '''if''' wolne(k,i) '''then''' '''begin'''
 +
  ustaw(k,i);
 +
  rozstaw(k+1);
 +
  odstaw(k,i);
 +
        '''end'''
 +
  '''end'''; // rozstaw
 +
 +
'''var''' i:integer;
 +
'''begin''' // Hetmany
 +
  '''for''' i:=1 '''to''' N '''do''' wiersze[i]:=0;
 +
  '''for''' i:=1 '''to''' N '''do''' kolumny[i]:=false;
 +
  '''for''' i:=-(N-1) '''to''' N-1 '''do''' przekgd[i]:=false;
 +
  '''for''' i:=2 '''to''' 2*N '''do''' przekdg[i]:=false;
 +
  jest:=false;
 +
  rozstaw(i);
 +
  '''if''' '''not''' jest '''then''' writeln('Nie znaleziono żadnego ustawienia')
 +
'''end''' // Hetmany
 +
 +
''Koszt czasowy:'' wykładniczy względem N
 +
 +
''Koszt pamięciowy:'' liniowy względem N
 +
 +
''Opis:'' Aby ustawić N hetmanów, każdy z nich musi stać w osobnym wierszu. Dlatego główna procedurą rekurencyjna 'rozstaw' próbuje ustawić k-tego hetmana w wierszu k w kolejnych kolumnach. Jeśli to się uda (wolne(k,i)=true) zaznacza zajętość odpowiedniej kolumny i przekątnych i wywołuje się rekurencyjnie aby rozstawić pozostałe hetmany. Po powrocie z wywołania rekurencyjnego, kolumna i przekątne są zwalniane i pętla for próbuje ustawić k-tego hetmana w kolejnej kolumnie.
 +
 +
Jeśli nie ma już żadnych hetmanów do rozstawiania (k=N+1) oznacza to, że N jest już ustawionych - pozostaje ich wypisać. Przy okazji zmienna 'jest' rejestruje czy jakiekolwiek rozwiązanie zostało wypisane. Jeśli nie, główna procedura 'Hetmany' wypisuje stosowny komunikat.
  
 
</div>
 
</div>
Linia 347: Linia 422:
 
'''Wskazówka 1'''  
 
'''Wskazówka 1'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Zamiast rozwiązania naiwnego wymajającego <math>n^2</math> mnożeń zróbmy trochę
+
Zamiast rozwiązania naiwnego wymajającego <math>n^2</math> 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 <math>p(x)</math> i <math>q(x)</math> podzielimy na dolna i górną część<br>
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 <math>p(x)</math> i <math>q(x)</math> podzielimy na dolna i górną część<br>
 
 
<math>p(x) = p_l(x) + p_h(x)*x^{N/2}</math> i analogicznie  
 
<math>p(x) = p_l(x) + p_h(x)*x^{N/2}</math> i analogicznie  
 
<math>q(x) = q_l(x) + q_h(x)*x^{N/2}</math>, to ich iloczyn można zapisać tak:<br>
 
<math>q(x) = q_l(x) + q_h(x)*x^{N/2}</math>, to ich iloczyn można zapisać tak:<br>
Linia 384: Linia 458:
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
  
  procedure Suma(maxN:integer; n:integer);
+
  procedure Suma(n:integer);
  // 1 <= n <= maxN
+
  // 1 <= n
 
   
 
   
   procedure rozklad(var T:array[1..maxN] of integer; ti,k,m:integer)
+
   procedure rozklad(var T:array[1..n] of integer; ti,k,m:integer)
   // 0 <= ti <= maxN
+
   // 0 <= ti <= n
 
   // ti > 0 --> k=T[ti]
 
   // ti > 0 --> k=T[ti]
 
   // 0 <= m
 
   // 0 <= m
Linia 408: Linia 482:
 
   end //rozklad
 
   end //rozklad
 
   
 
   
  var T:array[1..maxN] of integer;
+
  var T:array[1..n] of integer;
 
  begin    
 
  begin    
 
   rozklad(T,0,n,n);
 
   rozklad(T,0,n,n);
Linia 415: Linia 489:
 
''Koszt czasowy:'' wykładniczy względem n
 
''Koszt czasowy:'' wykładniczy względem n
  
''Koszt pamięciowy:'' liniowy względem maxN
+
''Koszt pamięciowy:'' liniowy względem n
  
 
''Opis:'' Funkcja rekurencyjna 'rozkład' przegląda wszystkie nierosnące rozkłady liczby m używające składników niewiększych niż k. Ponieważ w tablicy T[1..ti] jest już nierosnący ciąg składników o sumie n-m, wydłużenie go o dowolny taki rozkład m będzie dawać poprawny rozkład n.
 
''Opis:'' Funkcja rekurencyjna 'rozkład' przegląda wszystkie nierosnące rozkłady liczby m używające składników niewiększych niż k. Ponieważ w tablicy T[1..ti] jest już nierosnący ciąg składników o sumie n-m, wydłużenie go o dowolny taki rozkład m będzie dawać poprawny rozkład n.

Wersja z 15:37, 20 lip 2006

To są ćwiczenia z rekurencji.

Zadanie 1 (Labirynt)

Czy istnieje ścieżka miedzy wskazanymi punktami (i1,j1) i (i2,j2) w labiryncie reprezentowanym przez prostokątną tablicę liczb całkowitych o rozmiarze M×N, zawierającą zera (ściana) i jedynki (droga)? Zakładamy, że nie można przechodzić z pola na pole po skosie (np. z (2,5) na (3,6)), a tylko w czterech podstawowych kierunkach (np. z (2,5) na (3,5), (2,4) itd.)

Wskazówka 1

Rozwiązanie 1

Pytanko 1:

Pytanko 2:

Pytanko 3: (trudniejsze)

Odpowiedź:

Dla ciekawskich:

Zadanie 2 (Z górki na pazurki)

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

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

Tak jak w poprzednim zadaniu poruszać się można tylko w czterech kierunkach podstawowych, nie po przekątnej.

Wskazówka 1

Rozwiązanie 1

Rozwiązanie 2

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

Rozwiązanie 1

Pytanko 1

Odpowiedź

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 1

Zadanie 5 (Mnożenie wielomianów)

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

Wskazówka 1

Zadanie 6 (Suma składników)

Napisz procedurę, która wypisze dla zadanej liczby n jej wszystkie rozkłady na sumy nieujemnych liczb naturalnych większych od 1 ustawionych w kolejności nierosnącej. Np. dla n = 3: 3 = 3 3 = 2+1 3 = 1+1+1 Można założyć, że n jest mniejsza lub równa pewnej stałej maxN.

Wskazówka 1

Wskazówka 2

Rozwiązanie 1