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

Zadanie 2 (Flaga holenderska)

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

Rozwiązanie 1

program FlagaHolenderska(N,A);
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
    else 
      if A[r]<0 then begin
        pom:=A[r]; A[r]:=A[m]; A[m]:=pom;
        m:=m+1;
        r:=r+1;
      end
      else begin
        pom:=A[r]; A[r]:=A[w]; A[w]:=pom;
        w:=w-1;
      end;
end.

Zadanie 3 (Najdłuższe plateau)

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

Możliwe rozwiązania zadania 3

Rozwiązanie 1

program NajdluzszePlateau1(N,A);
var p,w,k,maks: integer;
begin
  p:=1; w:=A[p]; maks:=1; 
  while p < N do begin
    k:=p+1; koniec:=false;
    while (k <= N) and (not koniec) do
      if A[k]=w then k:=k+1
      else koniec:=true;
    maks:=max(maks, k-p);
    p:=k;
    if p <= N then w:=A[p];
  end;
 end.

Rozwiązanie 2

program NajdluzszePlateau2(N,A);
var w,k,dl,maks: integer;
begin
  w:=A[1]; dl:=1; k:=2; maks:=1; 
  while k <= N do begin
    if A[k]=w then dl:=dl+1
    else begin
      maks:=max(maks, dl);
      dl:=1;
    end;
    k:=k+1;
  end;
 maks:=max(maks, dl);
end.

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

Zadanie 4 (Segment o maksymalnej sumie)

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

Możliwe rozwiązania zadania 4

Rozwiązanie trywialne, o kwadratowej złożoności:

Rozwiązanie 1

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

Rozwiązanie liniowe:

Rozwiązanie 1

program NajdluzszePlateau2(N,A);
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.

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

Dane są dwie tablice A i B typu array[1..N] of integer, N > 1. 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.

Rozwiązanie 1

program CescWspolna(N,A,B);
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.

Zadanie 6 (Suma zbiorów)

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

Możliwe rozwiązania zadania 6

Rozwiązanie 1

program Suma(N,A,B);
var ia,ib: integer;
begin
ia:=1; ib:=1; 
while (ia <= N) and (ib <= N) do 
  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], ' ');
while ib <= N do write(B{ib], ' ');
end.

Rozwiązanie 2

program Suma(N,A,B);
var ia,ib: integer;
function mniejsze(ia, ib: integer):boolean;
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
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.

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

Rozwiązanie 1

program Podciag(N,A,M,B);
var ia,ib: integer;
    istnieje: boolean;
begin
if N > M then istnieje:=false
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);
  end;
end.

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.

Rozwiązanie 1

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

Można też odwracać jedynie część tablicy. Zapiszmy to w formie procedury

procedure Odwroc(var A: array[0..N-1] of integer, p,k:integer);
var pom: integer;
begin
while p < k do begin
  pom:=A[p];
  A[p]:=A[k];
  A[k]:=pom;
  p:=p+1;
  k:=k-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.

Możliwe rozwiązania zadania

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

Rozwiązanie 1

program Przesun1(N,A,k);
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.

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

Rozwiązanie 2

program Przesun2(N,A,k);
var w,d: integer;
begin
w:=nww(N,k);
d:=nwd(N,k);
for i:=0 to d-1 do begin
  akt:=A[i]; 
  nast:=(i+k)mod N;
  for j:=1 to w do begin
    pom:=A[nast];
    A[nast]:=akt;
    akt:=pom;
    nast:=(nast+k)mod N;
  end;
end;
end.

Można też zauważyć, że przesunięcie cykliczne o k w prawo realizuje się porzez trzy odwrócenia pewnych segmentów w tablicy. Procedura Odwroc pochodzi z zadania 8.

Rozwiązanie 3

program Przesun3(N,A,k);
begin
Odwroc(A,0,N-k-1);
Odwroc(A,N-k,N-1);
Odwroc(A,0,N-1);
end.

Zadanie 10 (Następna permutacja)

Tablica A typu array[1..N] of integer 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.

Rozwiązanie 1

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

program Nastepna_permutacja(N,A);
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;
  Odwroc(A,i,N);
end;

end.

Zadanie 11 (Segment o zadanej sumie)

Tablica A typu array[1..N] of integer 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ą p, k takie, że W = \Sum_i \in [p ..k-1] A[i])

Rozwiązanie 1

program Segment_o_danej_sumie(N,A,W);
var p,k,suma: integer;
    istnieje: boolean;
begin
if W < 0 then istnieje:=false 
else begin
  p:=1; k:=1;
  suma:=A[1];
  while (suma <> W) and (k <= N) do
    if suma < W then begin
      k:=k+1;
      suma:=suma+A[k];
    end
    else begin
      p:=p+1;
      suma:= suma-A[p];
    end;
    istnieje:=(suma=W);
end;
end.

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

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

Możliwe rozwiązania zadania

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 Glosowanie1(N,A);
var i,j,ile,zwyciezca: integer;
begin
i:=1;
zwyciezca:=0;
while (i <= (N div 2) + 1) and (zwyciezca=0)do begin
  ile:=0;
  for j:=1 to N do if A[i]=A[j] then ile:=ile+1;
  if (ile > (N+1) div 2) then zwyciezca:=A[i];
end;
end.

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

Rozwiązanie 2

program Glosowanie2(N,A);
var ile,i,a,kand,zwyciezca: integer;
begin
kand:=1; 
a:=A[1];
ile := 1;
i := 1;
while i < N do begin
  i:= i+1;
  if A[i]=a then ile:=ile+1
  else
    if ile > 0 then ile:=ile-1
    else begin
      a:=T[i];
      ile:=1;
    end;
end;
ile:=0;
for i:=1 to do 
  if A[i]=a then ile:=ile+1; 
if (ile > (N+1)div 2) then 
  zwyciezca:=a 
else zwyciezca:=0;
end.

Zadanie 13 (Arytmetyka liczb wielocyfrowych)

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

• 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.
• 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.
• 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..2N-1] of integer;

procedure Suma(A,B:liczba, var C:liczba, var:przepelnienie:boolean);
var p: integer;
begin
p:=0;
for i:=0 to N-1 do begin
  C[i]:=A[i]+B[i];
  if C[i] >= b then begin
    C[i]:=C[i]-b;
    p:=1;
  end
  else p:=0;
end;
przepelnienie:=(p=1);
end;

procedure Roznica(A,B:liczba, var C:liczba, var:ujemny:boolean);
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;

procedure Iloczyn(A,B:liczba, var C:dwa_liczba);
var p,i,j: integer;
begin
for i:=0 to 2N-1 do C[i]:=0;
for i:=0 to N-1 do begin
  p:=0;
  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
end;
end;

Zadanie INNE (Najdłuższy podciąg niemalejący)

Dana jest tablica A typu array[1..N] of integer, N > 1. Należy obliczyć długość najdłuższego podciągu niemalejącego w A.

Rozwiązanie 1

Kluczowe jest użycie dodatkowej tablicy B rozmiaru N, w której pod indeksem i przechowuje się minimalną wartość kończącą podciąg niemalejący o długości i w dotychczas przejrzanej części tablicy A, od 1 do k. Żeby uwzględnić A[k+1] należy w tablicy B odnależć miejsce na A[k+1] (najlepiej binarnie).

program Podciag_niemalejący(N,A);
var : integer;
    B: array[1..N] of integer;
begin
ib:=1;
B[ib]:=A[1];
ia:=2; 
while ia <= N do begin
  if A[ia] >= B[ib] then begin
    ib:=ib+1;     
    B[ib]:=A[ia]; 
  end
  else begin 
    z:=ZnajdzPierwszyWiekszy(B,1,ib);
    B[z]:=A[ia];
  end;
  ia:=ia+1;
end;
end.

Zadanie ()

Rozwiązanie 1

program (N,A);
var : integer;
begin
end.

Zadanie ()

Możliwe rozwiązania zadania

Rozwiązanie 1

program (N,A);
var : integer;
begin
end.