Wstęp do programowania / Ćwiczenia 2

Ta strona zawiera podstawowe zadania na tablice.

Ogladaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__

Zadanie 1 (Flaga polska)

Tablica A typu array[1..N] of integer (N > 0) wypełniona zerami i jedynkami reprezentuje ciąg N urn w których znajdują się żetony białe (0) i czerwone (1). Podaj algorytm działania automatu przestawiającego żetony w urnach tak, by najpierw były żetony czerwone, potem białe. Robot może wykonywać dwa rodzaje operacji:

• Kol(i) - podaje kolor żetonu w i-tej urnie (1 ≤ i ≤ n)
• Z(i,j) - zamienia żetony z i-tej i j-tej urny (1 ≤ i,j ≤ n)

Uwagi:

1. Operacja Kol jest bardzo kosztowna, więc zależy nam na tym by kolor każdego żetonu był sprawdzany co najwyżej raz.
2. Robot potrafi zapamiętać tylko kilka wartości z przedziału 0..N+1.
3. Nie można założyć, że występuje choć jeden żeton w każdym z kolorów.

Wskazówka 1

Należy przesuwać się indeksem c od początku tablicy zaś indeksem b od końca. Intencją jest utrzymywanie następującego niezmmiennika: wszystkie elementy tablicy o indeksach mniejszych od c są czerwone, zaś wiekszych od b są białe. Indeksy c i b będą się do siebie zbliżać i ostatecznie gdy c będzie równe b to tablica będzie uporządkowana.

Rozwiązanie 1

program FlagaPolska1(N:integer; A:array[1..N] of integer);
//Tablica A jest wypełniona zerami i jedynkami 
const bialy = 0;
      czerwony = 1;
var b,c : integer;
begin
  c:=1; b:=n;
  while c < b do 
    if Kol(c)=czerwony then c:=c+1
    else begin
      Z(c,b);
      b:=b-1;
    end;
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Wskazówka 2

Rozwiązanie 1 optymalizuje liczbę sprawdzeń kolorów, ale może niepotrzebnie zamieniać białe z białymi. Można tego uniknąć wprowadzając dodatkową pętlę po białych od końca tablicy.

Rozwiązanie 2

program FlagaPolska2(N:integer; A:array[1..N] of integer);
//Tablica A jest wypełniona zerami i jedynkami 
const bialy = 0;
      czerwony = 1;
var b,c : integer;
begin
  c:=1; b:=n;
  while c < b do 
    if Kol(c)=czerwony then c:=c+1
    else begin
      while Kol(b)=biały and (c<b) do b:=b-1;	//pętla po białych od końca tablicy
      if c<b then begin
        Z(c,b);
        b:=b-1;
      end;
    end;
end.

W rozwiązaniu 2 są dwie zagnieżdżone pętle while. Trzeba zwrócić uwagę, że gdyby nie warunek c<b to w przypadku tablicy zawierającej same białe żetony doszłoby do wyjścia poza zakres (odwołanie do Kol(0)).

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Wskazówka 3

W Rozwiązaniu 2 można uniknąć zagnieżdżonych while'i, trzeba jednak uważać aby nie sprawdzać kilka razy koloru tego samego żetonu.

Rozwiązanie 3

program FlagaPolska3(N:integer; A:array[1..N] of integer);
//Tablica A jest wypełniona zerami i jedynkami 
const bialy = 0;
      czerwony = 1;
var b,c,kb,kc : integer;
begin
  c:=1; kc:=Kol(c);
  b:=n; kc:=Kol(b);
  while c < b do 
    if kc=czerwony then begin 
      c:=c+1;
      kc:=Kol(c);
    end
    else 
      if kb=biały then begin
        b:=b-1;
        kb:=Kol(b);
      end 
      else begin
        Z(c,b);
        c:=c+1; 
        b:=b-1;
        if c < b then begin
          kc:=Kol(c);
          kb:=Kol(b);
        end;; 
      end;
end.

W rozwiązaniu 3 każdy żeton jest sprawdzany co najwyżej raz, a każda zamiana ustawia na dobrych miejscach 2 żetony (inaczej mówiąc tych żetonów nie trzeba już będzie przestawiać). A więc wszystkich zamian jest co najwyżej N div 2. Alternatywne rozwiązanie, unikające zagnieżdżonych pętli jest poniżej.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Wskazówka 4

Alternatywne rozwiązanie, unikające zagnieżdżonych pętli jest poniżej. Tu oba indeksy b i c przesuwają się od początku tablicy a niezmiennikiem jest to, że wszystkie elementy tablicy o indeksach mniejszych od c są czerwone, zaś te o indeksach wiekszych równych od c i miejszych od b są białe.

Rozwiązanie 4

program FlagaPolska4(N:integer; A:array[1..N] of integer);
//Tablica A jest wypełniona zerami i jedynkami 
const bialy = 0;
      czerwony = 1;
var b,c : integer;
begin
  c:=1; b:=1;
  while c <= N do 
    if Kol(b)=biały then b:=b+1
    else begin
       Z(c,b);
       b:=b+1;
       c:=c+1;
    end;
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Pytanko 1

Dla jakich danych algorytm przedstawiony w Rozwiązaniu 4 dokona N-1 zamian?

Pytanko 2

Jak trzeba by zmienić powyższe rozwiązania, gdyby zamiana Z(i,j) była dozwolona tylko dla i <> j ?

Zadanie 2 (Flaga trójkolorowa)

Dana jest tablica A typu array[1..N] of integer (N > 0). Należy tak poprzestawiać w niej elementy, żeby najpierw były elementy ujemne, potem równe zero, a na końcu dodatnie.

Wskazówka 1

Rozwiązanie dla flagi trójkolorowej jest uogólnieniem rozwiązania dla flagi dwukolorowej. Rozwiązanie 1 poniżej jest kombinacją rozwiązań 3 i 4 z zadania 1; zaś Rozwiązanie 2 poniżej jest bezpośrednim uogólnieniem rozwiązania 4 z zadania 1. Jeśli chodzi o liczbę zamian to lepsze wydaje się Rozwiązanie 1, gdyż od razu na dobre (ostateczne) miejsca trafiają elementy ujemne i dodatnie.

Rozwiązanie 1

program FlagaTrójkolorowa(N:integer; A:array[1..N] of integer);
var m,r,w,pom : integer;
begin
  m:=1; r:=1; w:=N;
  while r <= w do 
    if A[r]=0 then r:=r+1			//przedłużamy segment liczb dodatnich	
    else 
      if A[r]<0 then begin			
        pom:=A[r]; A[r]:=A[m]; A[m]:=pom;	//zamieniamy wartości w A[r] i A[m], po zamianie A[r]=0 i A[m] < 0  
        m:=m+1;					//więc zwiększamy oba indeksy r i m
        r:=r+1;
      end
      else begin
        pom:=A[r]; A[r]:=A[w]; A[w]:=pom;	//zamieniamy wartości w A[r] i A[w]
        w:=w-1;					//po zamianie A[w]>0,  ale o A[r] nic nie wiemy
      end;			     
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Rozwiązanie 2

program FlagaTrójkolorowa(N:integer; A:array[1..N] of integer);
var m,r,w,pom : integer;
begin
  m:=1; r:=1; w:=1;
  while w <= N do 
    if A[w]>0 then w:=w+1			//przedłużamy segment liczb dodatnich
    else 
      if A[w]=0 then begin
        pom:=A[r]; A[r]:=A[w]; A[w]:=pom;	//zamieniamy wartości w A[r] i A[w], po zamianie A[r]=0, A[w] >0 
        w:=w+1;					//więc zwiększamy oba indeksy r i w
        r:=r+1;					
      end
      else begin				//zamieniamy cyklicznie A[m], A[r] i A[w]
        pom:=A[m]; A[m]:=A[w]; A[w]:=A[r]; A[r]:=pom; 
        m:=m+1;
        r:=r+1;
        w:=w+1; 
      end;
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Zadanie 3 (Najdłuższe plateau)

Napisz program znajdujący w zadanej tablicy A typu array[1..N] of integer, N > 0, długość najdłuższego stałego segmentu (spójnego fragmentu tablicy).

Wskazówka 1

Zadanie to można rozwiązać używając dwóch pętli; zewnętrznej (po możliwych początkach segmentu) i wewnętrznej (w której szukamy końca segmentu stałego).

Rozwiązanie 1

program NajdłuższePlateau1(N:integer; A:array[1..N] of integer);
var l,p,w,maks: integer;
begin
  l:=1; w:=A[l]; maks:=1; 
  while l < N do begin
    p:=l+1; koniec:=false;
    while (p <= N) and (not koniec) do		//dopóki jesteśmy w tablicy i poruszamy się wewnątrz segmentu stałego
      if A[p]=w then p:=p+1
      else koniec:=true;
    maks:=max(maks, p-l);			//poprawiamy maks 
    l:=p;
    if l <= N then w:=A[l];			//ustawiamy nowy początek segmentu
  end;
 end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Wskazówka 2

Dokładnie to samo rozwiązanie można zapisać używając jednej pętli.

Rozwiązanie 2

program NajdłuższePlateau2(N:integer; A:array[1..N] of integer);
var w,p,dl,maks: integer;
begin
  w:=A[1]; dl:=1; p:=2; maks:=1; 
  for p:=2 to N do begin
    if A[p]=w then dl:=dl+1
    else begin
      maks:=max(maks, dl);
      dl:=1;
    end;
  end;
  maks:=max(maks, dl);
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Pytanko 1

Czy przedostatnia linia programu w Rozwiązaniu 2 jest potrzebna? Co by było gdyby jej nie było ?

Inna wersja zadania

A co było gdyby tablica była posortowana ?

Wskazówka 3

Podczas przechodzenia tablicy indeksem i od lewej do prawej, zmiana maks - dotychczas odnalezionej wartości najdłuższego plateau - zachodzi tylko wtedy gdy A[i] wydłuża ostatnie plateau do długości maks+1. Ponieważ tablica jest posortowana to wystarczy porównywać wartości A[i] i A[i-maks].

Rozwiązanie 3

program NajdłuższePlateau3(N:integer; A:array[1..N] of integer);
var i,maks: integer;
begin
  maks:=1;
  for i:=2 to N do 
    if A[i]=A[i-maks] then maks:=maks+1;
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Zadanie 4 (Segment o maksymalnej sumie)

Napisz program znajdujący w zadanej tablicy A typu array[1..N] of integer, N > 0, maksymalną sumę segmentu (spójnego fragmentu tablicy). Przyjmujemy, że segment pusty ma sumę 0.

Wskazówka 1

Najprostsze rozwiązanie to dla wszystkich możliwych segmentów policzyć ich sumę.

Rozwiązanie 1

program SegmentOMaksymalnejSumie1(N:integer; A:array[1..N] of integer);
var l,p,j,suma,maks: integer;
begin
  maks:=0;
  for l:=1 to N do begin		//wybieramy początek segmentu
    for p:=l to N do begin		//wybieramy koniec
      suma:=0;
      for j:=l to p do suma:=suma+A[j];	//liczymy sumę
      maks:=max(maks,suma);
    end;
  end;
end.

Koszt czasowy: sześcienny względem N

Koszt pamięciowy: stały

Wskazówka 2

W powyższym rozwiązaniu sumę pewnych segmantów liczy się wiele razy. Lepiej, dla danego początku l obliczać po kolei sumy coraz dłuższych segmentów zaczynających sie w l.

Rozwiązanie 2

program SegmentOMaksymalnejSumie2(N:integer; A:array[1..N] of integer);
var l,p,suma, maks: integer;
begin
  maks:=0;
  for l:=1 to N do begin
    suma:=0;
    for p:=l to N do begin
      suma:=suma+A[p]; 
      maks:=max(maks,suma);
    end;
  end;
end.

Koszt czasowy: kwadratowy względem N

Koszt pamięciowy: stały

Wskazówka 3

Niech Pref(i) oznacza sumę elemetów tablicy od 1 do i włącznie. Suma segmentu od l do p to oczywiście Pref(p) - Pref(l-1). Maksymalną sumę segmentu kończącego się w p uzyskamy odejmując od Pref(p) minimalne Pref(i) gdzie i przebiega [1..p].

Rozwiązanie 3

program  SegmentOMaksymalnejSumie3(N:integer; A:array[1..N] of integer);
var mini_pref,biez_pref,maks,i: integer;
begin
  maks:=0;
  mini_pref:=0
  biez_pref:=0;
  for i:=1 to N do begin
    biez_pref:=biez_pref+A[i]);
    mini_pref:=min(mini_pref,biez_pref);
    maks:=max(maks, biez_pref-mini_pref);
  end;
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Wskazówka 4

Poniższe rozwiązanie opiera się na spostrzeżeniu, że jeśli suma pewnego segmentu o początku w l i końcu w p jest ujemna, lub nawet równa zero, to nie ma sensu tego segmantu przedłużać. Co więcej wszystkie segmenty o początkach pomiędzy l i p będą podsegmentami tego dotychczas rozpatrywanego, więc nie ma sensu ich rozważać przy poszukiwaniu segmantu o maksymalnej sumie. Jedyną sensowną możliwością jest rozpatrywanie segmentów które zaczynają się od p+1.

Rozwiązanie 4

program  SegmentOMaksymalnejSumie4(N:integer; A:array[1..N] of integer);
var l,p,i,biez,maks: integer;
begin
  l:=1;
  p:=2;
  suma:=A[l];   
  maks:=max(0,suma);
  while p <= N do
    if suma+A[p] <= 0 then begin
      l:=p+1;
      suma:=A[l];
      p:=l+1;
      maks:=max(0,suma);
    else begin
      suma:=suma+A[p];
      maks:max(0,suma);
      p:=p+1;
    end;
end.

Ponieważ jest to rozwiązanie działające w czasie liniowym od N (p zwiększa się w każdym obrocie pętli) a wszystkich segmentów jest kwadratowo wiele, powstaje wątpliwość czy przypadkiem nie omijamy segmentu a maksymalnej sumie. To trzeba by udowodnić. Temat ten będzie poruszany w module o niezmiennikach i logice Hoare'a.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Rozwiązanie 5

Poniżej znajduje się inaczej (zwięźlej) zapisane Rozwiązanie 4. W tym rozwiązaniu nie odwołujemy się bezpośrednio do początku i końca aktualnego segmentu, a tylko do jego sumy (biez).

program  SegmentOMaksymalnejSumie5(N:integer; A:array[1..N] of integer);
var i,biez,maks: integer;
begin
  maks:=0;
  biez:=0;
  for i:=1 to N do begin
    biez:=max(0,biez+A[i]);
    maks:=max(maks, biez);
  end;
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Zadanie 5 (Część wspólna zbiorów)

Dane są dwie tablice A i B typu array[1..N] of integer, N > 0. Obie są posortowane rosnąco. Należy traktując A i B jako reprezentacje dwu zbiorów wypisać (operacją write) cześć wspólną tych zbiorów.

Wskazówka 1

Będziemy przesuwać się po tablicach od prawej do lewej indeksami ia i ib. Za każdym obrotem pętli przesuwamy ten indeks pod którym jest miejsza wartość, lub oba gdy mają takie same wartości.

Rozwiązanie 1

program CzęśćWspólna(N:integer; A,B:array[1..N] of integer);
//Tablice A i B są posortowane rosnąco
var ia,ib: integer;
begin
  ia:=1; ib:=1;
  while (ia <= N) and (ib <= N) do 
    if A[ia] < B[ib] then ia:=ia+1
    else 
      if A[ia] > B[ib] then ib:=ib+1;
      else begin
         write(A{ia], ' ');
         ia:=ia+1;
         ib:=ib+1;
      end;
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Zadanie 6 (Suma zbiorów)

Dane są dwie tablice A i B typu array[1..N] of integer, N > 0. Obie są posortowane rosnąco. Należy traktując A i B jako reprezentacje dwu zbiorów wypisać (operacją write) sumę tych zbiorów.

Wskazówka 1

Dopóki istnieją elementy w obu tablicach przesuwamy się tak jak przy obliczaniu części wspólnej, potem obługujemy końcówki tablic.

Rozwiązanie 1

program Suma(N:integer; A,B:array[1..N] of integer);
//Tablice A i B są posortowane rosnąco
var ia,ib: integer;
begin
  ia:=1; ib:=1; 
  while (ia <= N) and (ib <= N) do	//dopóki są elementy w obu tablicach
    if A[ia] < B[ib] then begin
      write(A{ia], ' ');
      ia:=ia+1;
    end
    else 
      if A[ia] > B[ib] then begin
        write(B{ib], ' ');
        ib:=ib+1;
      end 
      else begin
        write(A{ia], ' ');
        ia:=ia+1;
        ib:=ib+1;
      end;
  while ia <= N do write(A{ia], ' ');	//obsługa końcówki A
  while ib <= N do write(B{ib], ' ');	//obsługa końcówki B
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Pytanko 1

Z dwóch pętli while obsługujących końcówki tablic A i B w Rozwiązaniu 1 wykona się co najwyżej jedna. W jakich sytuacjach nie wykona się żadna z nich ?

Wskazówka 2

Można próbować modyfikować rozwiązanie zadania o części wspólnej, tak by oddać analogię między sumą i częścią wspólną zbiorów. Prowadziłoby to do warunku (ia <= N) or (ib <= N) w głównej pętli while. Trzeba jednak na nowo zdefiniować co to znaczy że pod danym indeksem jest mniejsza wartość niż pod innym indeksem, w sytuacji gdy jeden z tych indeksów może być większy od N.

Rozwiązanie 2

program Suma(N:integer; A,B:array[1..N] of integer);
//Tablice A i B są posortowane rosnąco
var ia,ib: integer;
function mniejsze(ia,ib: integer):boolean;		//funkcja porównująca wartości w ia i ib
begin
  mniejsze:=false;
  if (ib > N) and (ia <= N) then  mniejsze:=true
  else if (ib <= N) and (ia <= N) then  
    if A[ia] < B[ib] then mniejsze:=true
end;    
begin						//główny program
  ia:=1; 
  ib:=1; 
  while (ia <= N) or (ib <= N) do 
    if mniejsze(ia,ib) then begin
      write(A{ia], ' ');
      ia:=ia+1;
    end
    else 
      if mniejsze(ib,ia) then begin
        write(B{ib], ' ');
        ib:=ib+1;
      end 
      else begin
         write(A{ia], ' ');
         ia:=ia+1;
         ib:=ib+1;
      end;
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Zadanie 7 (Podciąg)

Dane są dwie tablice A typu array[1..N] of integer i B typu array[1..M] of integer, N, M > 0. Napisz program sprawdzający, czy A jest podciągiem B (tzn. czy istnieje funkcja f, rosnąca, z 1..N w 1..M, t. ze A[i]=B[f(i)]).

Wskazówka 1

Każdy element tablcy A musi odnależć swoją kopię w tablicy B. Przechodząc tablicę A od lewej do prawej i szukamy odpowiednika A[i] w części B, która jeszcze nie została odwiedzona.

Rozwiązanie 1

program Podciąg(N,M:integer; A:array[1..N] of integer; B:array[1..M] of integer);
var ia,ib: integer;
    istnieje: boolean;
begin
  if N > M then istnieje:=false	//bo funkcja f miała być rosnąca
  else begin
    ia:=1;ib:=1;
    while (ia <= N) and (ib <= M) do
      if A[ia] <> B[ib] then ib:=ib+1;
      else begin
        ia:=ia+1;
        ib:=ib+1;
      end;
    istnieje:=(ia>N);
    if istnieje then write('Tablica A jest podciągiem tablicy B);
  end;
end.

Koszt czasowy: liniowy względem N+M

Koszt pamięciowy: stały

Zadanie 8 (Odwracanie tablicy)

Dana tablica A typu array[0..N-1] of integer, N > 1. Napisz program odwracający kolejność elementów w A.

Wskazówka 1

Należy zamienić element 0 z N-1, 2 z N-2 itd.

Rozwiązanie 1

program Odwracanie1(N:integer; A:array[0..N-1] of integer);
var l,pom: integer;
begin
  l:=0; 
  while l < (N div 2) do begin
    pom:=A[l];
    A[p]:=A[N-1-l];
    A[N-1-l]:=pom;
    l:=l+1;
  end;
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Wskazówka 2

To samo co w Rozwiązaniu 1 można zrobić używjąc dwóch indeksów l i p na oznaczenie elemnetów z lewej i prawej strony tablicy. W ten sposób na pewno nie pomylimy się wyliczając element z którym ma się zamienić l (czy to N-1-l, N-l, N-(l+1) itp.) i warunek w while.

Rozwiązanie 2

program Odwracanie2(N:integer; A:array[0..N-1] of integer);
var l,p,pom: integer;
begin
  l:=0; p:=N-1;
  while l < p do begin
    pom:=A[l];
    A[l]:=A[p];
    A[p]:=pom;
    l:=l+1;
    p:=p-1;
  end;
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Można też odwracać jedynie część tablicy, pomiędzy indeksami l i p. Zapiszmy to w formie procedury

procedure OdwracanieTablicy(var A: array[0..N-1] of integer; l,p:integer);
var pom: integer;
begin
  while l < p do begin
    pom:=A[l];
    A[l]:=A[p];
    A[p]:=pom;
    l:=l+1;
    p:=p-1;
  end;
end. 

Zadanie 9 (Przesunięcie cykliczne)

Dana tablica A typu array[0..N-1] of integer, N > 1, i liczba naturalna k > 1. Napisz program realizujący przesunięcie cykliczne w prawo o k pól, czyli przesuwający zawartość pola A[i] na A[(i+k) mod N] dla każdego i < N.

Wskazówka 1

Najprościej rozwiązać to zadanie używając dodatkowej pamięci rozmiaru N.

Rozwiązanie 1

program Przesuń1(N,k:integer; A:array[1..N] of integer);
var i: integer;
  P: array[0..N-1] of integer;
begin
  for i:=0 to' N-1 do P[(i+k) mod N]:=A[i];
  for i:=0 to' N-1 do A[i]:=P[i];
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: liniowy względem N

Wskazówka 2

Można też skorzystać z rozkladu permutacji na cykle. Długość każdego takiego cyklu wynosi N/nwd(N,k) a na dodatek pierwsze nwd(N,k) elementów tablicy należy do różnych cykli. Dodatkowym kosztem jest oczywiście obliczenie nwd.

Rozwiązanie 2

program Przesuń2(N,k:integer; A:array[1..N] of integer);
// k > 1
var dl_cyklu,ile_cykli: integer;
begin
  ile_cykli:=nwd(N,k);
  dl_cyklu:=N/nwd(N,k);
  for i:=0 to ile_cykli-1 do begin
    akt:=A[i];			       //na akt zapamiętujemy wartość do przesunięcia
    nast:=(i+k) mod N;                 //obliczamy dla niej nowe miejsce nast
    for j:=1 to dl_cyklu do begin
      pom:=A[nast];		       //wstawiamy akt na A[nast]
      A[nast]:=akt;
      akt:=pom;	                       //to co tam było będzie nowym akt
      nast:=(nast+k) mod N;            //obliczamy nowe nast
    end;
  end;
end.

Koszt czasowy: liniowy względem N + koszt nwd

Koszt pamięciowy: stały

Wskazówka 3

Można też zauważyć, że przesunięcie cykliczne o k w prawo można zrealizować poprzez trzy odwrócenia pewnych segmentów tablicy.

Rozwiązanie 3

program Przesun3(N,k:integer; A:array[1..N] of integer);
// k > 1
begin
  OdwracanieTablicy(A,0,N-k-1);
  OdwracanieTablicy(A,N-k,N-1);
  OdwracanieTablicy(A,0,N-1);
end.

Procedura OdwracanieTablicy pochodzi z Zadania 8. Poprawność tego rozwiązania można uzasadnić poniższym rysunekiem. W pierwszej linii jest aryginalna tablica, a w kolejnych tablica po kolejnych wywolaniach procedury OdwracanieTablicy.

  a(0)     a(1)    ...        ...    a(N-k-1) a(N-k)    ...        a(N-1)
a(N-k-1) a(N-k-2)  ...        ...     a(0)    a(N-k)    ...        a(N-1)
a(N-k-1) a(N-k-2)  ...        ...     a(0)    a(N-1)    ...        a(N-k)
 a(N-k)  a(N-k+1)  ... a(N-1) a(0)    ...     ...       a(N-k-2)  a(N-k-1) 

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Zadanie 10 (Następna permutacja)

Tablica A typu array[1..N] of integer, N > 0, zawiera pewną permutację liczb 1.. N. Napisz program wpisujący do A następną leksykograficznie permutację. Zakładamy, że permutacja w A nie jest ostatnia leksykograficznie.

Przykład Dla N=3 kolejne permutacje w porządku leksykograficznym wyglądają nastepująco:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Wskazówka 1

Zastanów się która część talicy pozostanie taka sama w następnej permutacji.

Rozwiązanie 1

program NastępnaPermutacja(N:integer; A:array[1..N] of integer);
//Permutacja zapisana w A nie jest ostatnia leksykograficznie
var i,k,pom: integer;
begin
  i:=N-1;
  while i >= 1 do if A[i] > A[i+1] then i:=i-1;
  if i >= 1 then begin
    k:=N;
    while k >= i do if A[k] < A[i] then k:=k-1;
    pom:=A[i];
    A[i]:=A[k];
    A[k]:=pom;
    OdwracanieTablicy(A,i,N);
  end;
end.

Procedura OdwracanieTablicy pochodzi z Zadania 8.

Najpierw szukamy od tyłu pierwszego elementu, takiego że A[i] < A[i+1] (tu korzystamy z założenia że to nie ostatnia permutacja), potem szukamy na prawo od i najmniejszego większego od niego elementu k (uwaga: dużo wygodniej to robić od prawej strony!), potem zamieniamy te elementy i odwracamy kolejność elementów na prawo od i.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Zadanie 11 (Segment o danej sumie)

Tablica A typu array[1..N] of integer, N > 0, zawiera tylko liczby dodatnie. Napisz program który dla danego W typu integer sprawdza czy w A istnieje segment o sumie W (czyli czy istnieją l, p takie, że W$=A[l]+...+A[p-1]$).

Wskazówka 1

Podobnie jak w zadaniu o segmencie o maksymalnej sumie można dla danego początku l obliczać po kolei sumy coraz dłuższych segmentów zaczynających sie w l.

Rozwiązanie 1

program SegmentODanejSumie1(N,W:integer; A:array[1..N] of integer);
//Tablica A zawiera tylko liczby dodatnie
var l,p,suma: integer;
    znalezione: boolean;
begin
  if W < 0 then znalezione:=false 
  else begin
    maks:=0;
    l:=1;
    znalezione:=false;
    while (l <= N) and (not znalezione) do begin
      p:=l;
      suma:=0;
      while (p <=  N) and (suma < W) do begin
          suma:=suma+A[p]; 
          p:=p+1;
      end;  
      znalezione:=(suma=W);
      l:=l+1;
    end;  //while
  end;  //else
  if znalezione then write('W tablicy A istnieje segment o sumie W); 
end.

Koszt czasowy: kwadratowy względem N

Koszt pamięciowy: stały

Wskazówka 2

Podobnie jak w zadaniu o segmencie o maksymalnej sumie możliwe też jest rozwiązanie o liniowym koszcie czasowym.

Rozwiązanie 2

program SegmentODanejSumie2(N,W:integer; A:array[1..N] of integer);
//Tablica A zawiera tylko liczby dodatnie
var l,p,suma: integer;
    znalezione: boolean;
begin
  if W < 0 then znalezione:=false 
  else begin
    l:=1; p:=1;
    suma:=0;
    while (suma <> W) and (p <= N) do
      if suma < W then begin		//jeśli suma jest za mała to przesuwamy prawy koniec segmentu
        suma:=suma+A[p];
        p:=p+1;
      end
      else begin			//jeśli za duża to przesuwamy lewy koniec segmentu
        suma:= suma-A[l];
        l:=l+1;
      end;
    while (suma > W) do begin           //jeśli suma nadal za duża to próbujemy ją zmniejszyć
      suma:= suma-A[l];
      l:=l-1;
    end;
    znalezione:=(suma=W);
  end;  //else
  if znalezione then write('W tablicy A istnieje segment o sumie W); 
end.

Ponieważ jest to rozwiązanie działające w czasie liniowym od N (l+p zwiększa się w każdym obrocie pętli) a wszystkich segmentów jest kwadratowo wiele, powstaje wątpliwość czy przypadkiem nie omijamy segmentu a maksymalnej sumie. To trzeba by udowodnić. Wrócimy do tego problemu w module o niezmiennikach i logice Hoare'a.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Zadanie 12 (Głosowanie większościowe)

Dana jest tablica A typu array[1..N] of integer, N > 0. Sprawdzić czy jest w niej element wystepujący więcej niż N/2 razy i jeśli tak wskaż go.

Wskazówka 1

Najprościej jest dla każdego elementu policzyć liczbę wystąpień w tablicy. Jest to oczywiście rozwiązanie o kwadratowym koszcie czasowym.

Rozwiązanie 1

program Głosowanie1(N:integer; A:array[1..N] of integer);
var i,j,ile,indeks_lidera: integer;
begin
  i:=1;
  indeks_lidera:=0;
  while (i < (N+1) div 2) and (indeks_lidera=0) do begin
    ile:=0;
    for j:=1 to N do if A[i]=A[j] then ile:=ile+1;
    if (ile >= N div 2 + 1) then indeks_lidera:=i;
  end;
  if indeks_lidera <> 0 then write('Liderem jest: ', A[indeks_lidera]);
end.

Ponieważ lider musi mieć co najmiej N div 2 + 1 wystąpień w tablicy, to wystarczy go szukać na ((N+1) div 2) pierwszych pozycjach tablicy A.

Koszt czasowy: kwadratowy względem N

Koszt pamięciowy: stały

Wskazówka 2

To zadanie ma też (piękne) rozwiązanie liniowe. Składa się ono z dwóch faz. W pierwszej wyznaczamy takie kand, że jeśli jest lider, to jest nim kand, w drugiej (banalnej) sprawdzamy czy kand wygrał.

Rozwiązanie 2

program Głosowanie2(N,W:integer; A:array[1..N] of integer);
var ile,i,kand,lider: integer;
begin
  kand:=A[1];		//szukamy kandydata na lidera
  ile := 1;
  for i:=2 to N do begin	
    if A[i]=kand then ile:=ile+1
    else
      if ile > 0 then ile:=ile-1
      else begin
        kand:=A[i];
        ile:=1;
      end;
  end;
  ile:=0;		//sprawdzamy czy kandydat jest liderem
  for i:=1 to do 
    if A[i]=kand then ile:=ile+1; 
  if (ile >= (N div 2 + 1) then begin 
    lider:=kand;
    write('Liderem jest: ', kand);
  end 
  else 
    lider:=0;
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Zadanie 13 (Arytmetyka liczb wielocyfrowych)

Liczby wielocyfrowe będą reprezentowane w tablicach typu liczba=array[0..N-1] of integer, N > 1, w taki sposób, że najmniej znacząca cyfra jest pod indeksem 0. Rozpatrujemy liczby przy podstawie b > 1. Napisz procedury obliczające:

1. sumę liczb A i B do C. Jeśli wynik nie zmieści się w C to wartość C nie ma znaczenia. Zmienna przepełnienie wskazuje czy do niego doszło czy nie.
2. różnicę A i B do C. Jeśli wynik miałby byc liczbą ujemną to wartość C nie ma znaczenia. Zmienna ujemny wskazuje jaki jest znak wyniku.
3. iloczyn A i B do C (C powinno być tablicą dwa razy dłuższą niż A i B, żeby móc pomieścić wynik).

Rozwiązanie 1

const N=100; 
  b=10; 
type liczba = array[0..N-1] of integer;
  dwa_liczba = array[0..2*N-1] of integer;

Poniżej treści procedur Suma, Roznica, Iloczyn:

procedure Suma(A,B:liczba, var C:liczba, var:przepełnienie:boolean);
//Sumujemy liczby zapisane w A i B do C; zmienna przepełnienie staje się true gdy wynik nie mieści się w C.
var p: integer;
begin
  p:=0;
  for i:=0 to N-1 do begin
    C[i]:=A[i]+B[i]+p;
    if C[i] >= b then begin
      C[i]:=C[i]-b;
      p:=1;
    end
    else p:=0;
  end;
  przepełnienie:=(p=1);
end;

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

procedure Różnica(A,B:liczba, var C:liczba, var:ujemny:boolean);
//Odejmujemy od liczby zapisanej w A liczbę z B. Wynik zapisujemy w C, zmienna ujemny informuje o znaku wyniku.
var p: integer;
begin
  p:=0;
  for i:=0 to N-1 do begin
    C[i]:=(A[i]-p)-B[i];
    if C[i] < 0 then begin
      C[i]:=C[i]+b;
      p:=1;
    end
    else p:=0;
  end;
  ujemny:=(p=1);
end;

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

procedure Iloczyn(A,B:liczba, var C:dwa_liczba);
//Iloczyn liczb zapisanych w A i B zapisujemy w C. 
var p,i,j: integer;
begin
  p:=0;
  for i:=0 to 2*N-1 do C[i]:=0;
  for i:=0 to N-1 do begin
    for j:=1 to N-1 do begin
      w:=A[i]*B[j]+p+C[i+j];
      C[i+j]:=w mod b;
      p:=w div b;
    end;
    C[i+N]:=p;
    p:=0;
  end;
end;

Koszt czasowy: kwadratowy względem N

Koszt pamięciowy: stały

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

Właściwą funkcję rekurencyjną szukającą drogi zamknij w funkcji-otoczce, która poza wywołaniem funkcji rekurencyjnej sprawdzi poprawność argumentów, przygotuje i/lub posprząta tablicę z labiryntem, zinterpretuje wynik funkcji rekurencyjnej itp. oraz będzie przechowywać dane wspólne dla wszystkich wywołań funkcji rekurencyjnej.

Rozwiązanie 1

function Labirynt(M,N:integer; var A:array[1..M,1..N] of integer; i1,j1,i2,j2:integer):boolean;
// M,N >= 1
// A zawiera 0 (ściana) i 1 (droga)

  function szukaj(i,j:integer):boolean;
  // 1 <= i <= M
  // 1 <= j <= N
  var jest:boolean;
  begin
    if (i=i2) and (j=j2) then 
      jest:=true 
    else begin
      jest:=false;
      if A[i,j]>0 then begin
        A[i,j]:=-1;
        if i>1 then jest:=szukaj(i-1,j);
        if not jest and (i<M) then jest:=szukaj(i+1,j);
        if not jest and (j>1) then jest:=szukaj(i,j-1);
        if not jest and (j<N) then jest:=szukaj(i,j+1);
      end
    end;
    szukaj:=jest
  end; // szukaj
  
var i,j:integer;
begin // Labirynt
  if not((1<=i1) and (i1<=M) and (1<=j1) and (j1<=N) and
    (1<=i2) and (i2<=M) and (1<=j2) and (j2<=N)) then
    Labirynt:=false
  else
  begin
    Labirynt:=szukaj(i1,j1);  
    for i:=1 to M do 
      for j:=1 to N do 
        if A[i,j]=-1 then A[i,j]:=1
  end
end; // Labirynt

Koszt czasowy: liniowy względem rozmiaru A (czyli M×N)

Koszt pamięciowy: liniowy względem rozmiaru A

Opis: Przeszukujemy wgłąb tablicę zaznaczając odwiedzone pola poprzez ustawienie ich wartości na -1. Dzięki temu nie zapętlimy się, ani nie przetwarzamy wielokrotnie tych samych pól.

Dyskusja: Funkcja 'Labirynt' jest otoczką, która sprawdza poprawność parametrów, wywołuje właściwą funkcję rekurencyjną 'szukaj' oraz sprząta po niej zaznaczenia w tablicy A.

Wewnętrzna funkcja rekurencyjna 'szukaj' ma za zadanie znaleźć ścieżkę z punktu (i,j) do punktu (i2,j2) po niezaznaczonych polach w tablicy A. Korzysta ona z kilku nazw zadeklarowanych przez otoczkę (M, N, A, i2, j2), dlatego nie są one parametrami wywołania funkcji 'szukaj'.

Funkcja 'szukaj':

1. sprawdza czy punkt (i,j) nie jest poszukiwanym końcem (w tym przypadku zwraca true),
2. sprawdza czy punkt (i,j) nie jest ścianą lub punktem odwiedzonym wcześniej (w tym przypadku zwraca false),
3. zaznacza punkt (i,j) jako odwiedzony
4. próbuje szukać drogi z punktów sąsiednich dla punktu (i,j), o ile sąsiedzi Ci istnieją.

Zauważ, że testy 1 i 2, mogłyby być wykonane przed każdym wywołaniem funkcji 'szukaj' w punkcie 4 (oraz w otoczce) zamiast na jej początku, jednak prowadziłoby to do wielokrotnego pisania bardzo podobnych fragmentów programu, co łatwo prowadzi do błędów. Oczywiście nie zmniejszyłoby to złożoności czasowej i pamięciowej.

Podobnie, jak testy 1 i 2, testy istnienia sąsiadów (i>1), (i<M) itp. w punkcie 4 mogłyby być wykonane na początku funkcji 'szukaj' (wtedy nie zakładalibyśmy, że (i,j) jest poprawnym punktem w tablicy), ale nie mając wiedzy w którą stronę ostatnio poszliśmy, musielibyśmy dla sprawdzić pełną poprawność obu współrzędnych (i,j), czyli w sumie sprawdzalibyśmy 4 warunki. W aktualnej wersji sprawdzamy tylko 1 warunek.

Poprawność rozwiązania: Oczywiste jest, że jeśli funkcja 'Labirynt' da wynik true, to ścieżka z (i1,j1) do (i2,j2) istnieje. Mniej oczywiste jest, że jeśli funkcja da wynik false, to ścieżka na pewno nie istnieje.

Aby przeprowadzić dowód przez sprzeczność, załóżmy, że funkcja 'szukaj' wywołana w funkcji 'Labirynt' dała wynik false, a ścieżka z (i1,j1) do (i2,j2) istnieje. W takim razie A[i1,j1]=-1 a A[i2,j2]=1. Wynika z tego, że ścieżka z (i1,j1) do (i2,j2) w którymś miejścu opuszcza zaznaczoną część tablicy, czyli istnieją dwa sąsiednie pola (i,j) i (i',j') na tej ścieżce, takie że A[i,j]=-1, A[i',j']=1. Z tego wynika, że funkcja szukaj została (w czasie działania programu) wywołana z parametrami (i,j), ale nie została wywołana z parametrami (i',j'). Jest to niemożliwe, bo pola te sąsiadują ze sobą i wywołanie dla (i,j) wywołałoby rekurencyjnie 'szukaj' dla (i',j').

Pytanko 1:

Ile razy maksymalnie może być wywołana funkcja 'szukaj' dla tego samego punktu?

Pytanko 2:

Jak przerobić przedstawione rozwiązanie na program wypisujący na ekran ścieżkę pomiędzy punktami (i1,j1) i (i2,j2), o ile taka ścieżka istnieje. Czy wypisana ścieżka będzie najkrótsza z możliwych ?

Pytanko 3: (trudniejsze)

Co by się stało, gdybyśmy usuwali zaznaczenie wychodząc z funkcji 'szukaj'? Czy program dalej by działał? Jeśli tak, to jaką by miał złożoność?

Odpowiedź:

Program dalej by działał, ale miałby wykładniczą złożoność czasową zamiast liniowej (złożoność pamięciowa pozostałaby liniowa). W tej wersji program wielokrotnie przeszukiwałby sąsiadów pól, o których już z wcześniejszych obliczeń wiadomo, że nie da się z nich dojść do punktu końcowego.

Dla ciekawskich:

Rozwiązanie przedstawione powyżej polega na przeszukiwaniu wgłąb grafu reprezentującego labirynt. Inne, równie dobre rozwiązanie polega na przeszukiwaniu tego grafu wszerz, zwanego również metodą płonącego lasu. Wymaga ono użycia struktury danych -- kolejki. Rozwiązanie to łatwo przerobić na program wypisujący najkrótszą ścieżkę pomiędzy punktami (i1,j1) i (i2,j2), o ile taka ścieżka istnieje.

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

Zadanie to należy rozwiązywać tak jak poprzednie. Jedyną różnicą jest to jak należy decydować czy z danego pola można przejść do sąsiedniego: oprócz zaznaczenia trzeba wziąć pod uwagę różnicę wysokości.

Rozwiązanie 1

function Zjazd1(M,N:integer; var A:array[1..M,1..N] of integer; i1,j1,i2,j2:integer):boolean;
// M,N >= 1
// A zawiera liczby > 0

  function szukaj(h,i,j:integer):boolean;
  // 0 < h
  // 1 <= i <= M
  // 1 <= j <= N
  var jest:boolean;
    hpom:integer;
  begin
    jest:=false;
    if (A[i,j]>0) and (h>A[i,j]) begin // h>=A[i,j] w wariancie II
      if (i=i2) and (j=j2) then 
        jest:=true 
      else begin
        hpom:=A[i,j];
        A[i,j]:=-A[i,j];
        if i>1 then jest:=szukaj(hpom,i-1,j);
        if not jest and (i<M) then jest:=szukaj(hpom,i+1,j);
        if not jest and (j>1) then jest:=szukaj(hpom,i,j-1);
        if not jest and (j<N) then jest:=szukaj(hpom,i,j+1);
      end
    end;
    szukaj:=jest
  end; // szukaj
  
var i,j:integer;
begin // Zjazd1
  if not((1<=i1) and (i1<=M) and (1<=j1) and (j1<=N) and
    (1<=i2) and (i2<=M) and (1<=j2) and (j2<=N)) then
    Zajzd:=false
  else
  begin
    Zjazd:=szukaj(A[i1,j1]+1,i1,j1); // wystarczy szukaj(A[i1,j1],i1,j1) w wariancie II
    for i:=1 to M do 
      for j:=1 to N do 
        if A[i,j]<0 then A[i,j]:=-A[i,j]
  end
end; // Zjazd1

Koszt czasowy: liniowy względem rozmiaru A (czyli M×N)

Koszt pamięciowy: liniowy względem rozmiaru A

Opis: Podobnie jak w poprzednim zadaniu, przeszukujemy tablicę wgłąb, jednak przechodzimy tylko do tych pól sąsiednich, które mają mniejszą (odpowiednio: mniejszą lub równą) wysokość.

Dyskusja: Tak jak w rozwiązaniu poprzedniego zadania, istnienie sąsiada na planszy badamy przed wywołaniem rekurencyjnym, a poprawność przejścia na początku wywołania. Służy nam do tego dodatkowy parametr 'h', który oznacza wysokość poprzedniego pola. Dlatego pierwsze wywołanie funkcji 'szukaj' ma pierwszy parametr A[i1,j1]+1 (w wariancie I). Uwaga! Funkcja ta nie zadziała, jeśli A[i1,j1]=MaxInt (czyli maksymalnej możliwej wartości typu integer). Poniżej przedstawione jest rozwiązanie bez tego mankamentu.

Rozwiązanie 2

function Zjazd2(M,N:integer; var A:array[1..M,1..N] of integer; i1,j1,i2,j2:integer):boolean;
// M,N >= 1
// A zawiera liczby > 0

  function wdol(h,i,j:integer):boolean;
  // sprawdza czy pole (i,j) nie jest zaznaczone i
  // czy przejscie z pola o wysokosci h na pole (i,j) jest rzeczywiscie w dół
  // 1 <= i <= M
  // 1 <= j <= N
  begin
    wdol:=(A[i,j]>0) and (h>A[i,j]) // h>=A[i,j] w wariancie II
  end; //wdol

  function szukaj(i,j:integer):boolean;
  // 1 <= i <= M
  // 1 <= j <= N
  var jest:boolean;
    hpom:integer;
  begin
    if (i=i2) and (j=j2) then 
      jest:=true 
    else begin
      jest:=false;
      hpom:=A[i,j];
      A[i,j]:=-hpom;
      if i>1 then if wdol(hpom,i-1,j) then jest:=szukaj(i-1,j);
      if not jest and (i<M) then if wdol(hpom,i+1,j) then jest:=szukaj(i+1,j);
      if not jest and (j>1) then if wdol(hpom,i,j-1) then jest:=szukaj(i,j-1);
      if not jest and (j<N) then if wdol(hpom,i,j+1) then jest:=szukaj(i,j+1);
    end;
    szukaj:=jest
  end; // szukaj
  
var i,j:integer;
begin // Zjazd2
  if not((1<=i1) and (i1<=M) and (1<=j1) and (j1<=N) and
    (1<=i2) and (i2<=M) and (1<=j2) and (j2<=N)) then
    Zajzd:=false
  else
  begin
    Zjazd:=szukaj(i1,j1); 
    for i:=1 to M do 
      for j:=1 to N do 
        if A[i,j]<0 then A[i,j]:=-A[i,j]
  end
end; // Zjazd2

Koszt czasowy: liniowy względem rozmiaru A (czyli M×N)

Koszt pamięciowy: liniowy względem rozmiaru A

Opis: Rozwiązanie jest bardzo podobne do poprzedniego. Różnica polega na przeniesieniu kodu z początku funkcji 'szukaj' do osobnej funkcji 'wdol'. Funkcja ta jest używana jako test dopuszczający do rekurencyjnego wywołania funkcji 'szukaj'.

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

• Dozwolone ruchy najlepiej reprezentować w tablicy typu TDozwRuchow = array[1..3, 1..3] of boolean, (przekątna nie ma znaczenia).
• Zastanów się, jaki warunek musi być spełniony przez tablicę dozwolonych ruchów, aby zadanie miało rozwiązanie.
• Użyj funkcji-otoczki do wstępnego sprawdzenia czy istnieje rozwiązanie oraz do pamiętania tablicy dozwolonych ruchów w czasie działania funkcji rekurencyjnej.

Rozwiązanie 1

type Paleczki = 1..3;

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

  procedure Rob(Skad, Dokad, Pom: Paleczki; Ile: Integer);
  // Pom jest zawsze rowne 6-Skad-Dokad, ale z parametrem jest czytelniej
  begin
    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, Pom, Ile-1);
        Przenies(Pom, Dokad);
        Rob(Skad, Dokad, Pom, Ile-1);
      end
  end; //Rob

  function CzyDaSie(Skad, Dokad, Pom: Paleczki):boolean
  begin
    if not Dozw[Skad, Dokad] and not (Dozw[Skad, Pom] and Dozw[Pom, Dokad]) then begin
      writeln('Nie da sie przełożyć krążka z ',Skad,' na ',Pom);
      CzyDaSie:=false
    end
    else
      CzyDaSie:=false
  end // CzyDaSie     

var ok:boolean
begin // Hanoi
  ok:=true;
  for i:=1 to 2 do for j:=i+1 to 3 do
    ok:=ok and CzyDaSie(i,j,6-i-j) and CzyDaSie(j,i,6-i-j);
  if ok then Rob(Skad,Dokad,6-Skad-Dokad,Ile);
end; // Hanoi

Koszt czasowy: wykładniczy ze względu na Ile

Koszt pamięciowy: liniowy ze względu na Ile

Omówienie: Zauważ, że dużo łatwiej jest rozwiązać to zadanie sformułowane w sposób ogólny, niż gdy powie się, że zabroniony jest konkretny ruch (np. 1 → 2).

Pytanko 1

Jaki przypadek jest najgorszy i ile trzeba wykonać wtedy ruchów?

Odpowiedź

Najgorszy przypadek, to taki, gdy przerwane jest połączenie Skąd-Dokąd w obie strony. Wtedy trzeba wykonać $3^{Ile}-1$ ruchów)

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

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.

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

Rozwiązanie 1

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.

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

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 połowę mniejszych wielomianów. W sumie uzyskamy liczbę mnożeń rzędu $n^{lg3}$. Szczególy można znaleźć w Sedgewick Algorithms in C++, str. 527-530.

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

Wskazówka 1

Użyj dodatkowej tablicy do przechowywania początków rozkładów. Uważaj, aby nie kopiować tej tablicy przy każdym wywołaniu rekurencyjnym!

Wskazówka 2

Funkcja rekurencyjna powinna mieć parametr wskazujący jak duże składniki mogą być użyte do rozkładu pozostałej liczby.

Rozwiązanie 1

procedure Suma(n:integer);
// 1 <= n

  procedure rozklad(var T:array[1..n] of integer; ti,k,m:integer)
  // 0 <= ti <= n
  // ti > 0 --> k=T[ti]
  // 0 <= m
  // m=0 --> ti > 0
  var i:integer
  begin
    if m=0 then begin
      writeln(n,' = ');
      for i=1 to ti-1 do write(T[i],'+');
      writeln(T[ti])
    end         
    else begin
      ti:=ti+1;
      for i=min(k,m) downto 1 do begin
        T[ti]:=i;
        rozklad(T,ti,i,m-i);
      end
    end
  end //rozklad

var T:array[1..n] of integer;
begin     
  rozklad(T,0,n,n);
end // Suma

Koszt czasowy: wykładniczy względem n

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.

Istotnie, jeśli m=0, w tablicy jest już gotowy rozkład n, więc wypisujemy go. W przeciwnym razie zwiekszamy ti, wszystkie liczby i, które mogą znaleźć się w tym miejscu rozkładu umieszczamy kolejno w T[ti] i wywołujemy rekurencyjnie funkcję 'rozklad', aby do wydłużonego rozkładu dopisała wszystkie rozkłady m-i o pierwszym składniku nieprzekraczającym i.

Zwróć uwagę, że tablica T przekazywana jest przez zmienną i dlatego jej zawartość nie jest kopiowana. Tablica T mogłaby też być zmienną globalną (dla procedury 'Suma'), ponieważ i tak wszystkie wywołania funkcji rozklad korzystają z tej samej tablicy zadeklarowanej w głównej części procedury 'Suma'.

Zauważ, że można by też tak napisać procedurę 'rozklad', aby nigdy nie wywoływała się rekurencyjnie dla m=0. Wypisywanie pełnego rozkładu miałoby miejsce wtedy, gdy min(k,m)=m (czyli k>=m) i oczywiscie petla 'for' zaczynalaby sie w takim przypadku od m-1.

Druga możliwa modyfikacja polega na zrezygnowaniu z parametru k, ponieważ k albo jest równe T[ti], albo m jeśli ti=0. Mozna by też użyć strażnika T[0]=n i zawsze mielibyśmy k=T[ti].

Poza wspomnianymi modyfikacjami całą procedurę 'rozkład' można by napisać w sposób rosnący, tzn. zamiast generować coraz mniejsze składniki - generować coraz większe, aż osiągniemy, bądź przekroczymy n. W takim wypadku składniki należałoby wypisywać w odwrotnej kolejności.