Ćwiczenia do Modułu 1

Ta strona będzie zawierać podstawowe zadania na tablice.

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). Należy podać algorytm działania automatu przestawiającego żetony w urnach tak, by najpierw były żetony białe, potem czerwone. 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.

Możliwe rozwiązania zadania 1

Rozwiązanie 1

program FlagaPolska1(N,A);
const bialy = 0;
            czerwony = 1;
var b,c : integer;
begin
  b:=1; c:=n;
  while b < c do 
    if Kol(b)=bialy then b:=b+1
    else begin
      Z(c,b);
      c:=c-1;
    end;
end.

Rozwiązanie 1 optymalizuje liczbę sprawdzeń kolorów, ale może niepotrzebnie zamieniać czerwone z czerwonymi. Mozna tego uniknąć wprowadzając dodatkową pętlę po czerwonych od końca tablicy.

Rozwiązanie 2

program FlagaPolska2(N,A);
const bialy = 0;
            czerwony = 1;
var b,c : integer;
begin
  b:=1; c:=n;
  while b < c do 
    if Kol(b)=bialy then b:=b+1
    else begin
      while Kol(c)=czerwony and (b<c) do c:=c-1;
      if b<c then begin
        Z(c,b);
        c:=c-1;
      end;
    end;
end.

W rozwiązaniu 2 są dwie zagnieżdżone pętle while. Trzeba zwrócić uwagę, że gdyby nie warunek b<c to w przypadku tablicy zawierającej same białe żetony doszłoby do wyjścia poza zakres (odwołanie do Kol(0)). 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,A);
const bialy = 0;
            czerwony = 1;
var b,c : integer;
begin
  b:=1; kb:=Kol(b);
  c:=n; kc:=Kol(c);
  while b < c do 
    if kb=bialy then begin 
      b:=b+1;
      kb:=Kol(b);
    end
    else 
      if kc=czerwony then begin
        c:=c-1;
        kc:=Kol(c);
      end 
      else begin
        Z(c,b);
        b:=b+1; 
        c:=c-1;
        if b < c then begin
          kb:=Kol(b);
          kc:=Kol(c);
        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 (czyli zamian jest co najwyżej N div 2). Alternatywne rozwiązanie, unikające zagnieżdżonych pętli jest poniżej. Jednak dla tablicy złożonej z jednego żetonu czerwonego i potem samych białych będzie potrzeba N-1 zamian.

Rozwiązanie 4

program FlagaPolska4(N,A);
const bialy = 0;
            czerwony = 1;
var b,c : integer;
begin
  b:=1; c:=1;
  while b <= N do 
    if Kol(c)=czerwony then c:=c+1
    else begin
       Z(c,b);
       b:=b+1;
       c:=c+1;
    end;
end.