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:
- Operacja Kol jest bardzo kosztowna, więc zależy nam na tym by kolor każdego żetonu był sprawdzany co najwyżej raz.
- Robot potrafi zapamiętać tylko kilka wartości z przedziału 0..N+1.
- 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 o k w prawo, 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)mad 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 ()
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.
