Ć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 roziązania

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.