Wstęp do programowania / Ćwiczenia 2

<<< Powrót do modułu Wprowadzenie do programowania

Ta strona zawiera podstawowe zadania na tablice.

Oglądaj 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; kb:=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 większych lub równych 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

Ćwiczenie 1

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

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

Wizualizacja

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] jeśli m<>r; wpp zamieniamy A[m] i A[w]
        pom:=A[m]; 
        A[m]:=A[w]; 
        if (m<>r) then begin
          A[w]:=A[r]; 
          A[r]:=pom;
        end
        else A[w]:=pom; 
        m:=m+1;
        r:=r+1;
        w:=w+1; 
      end;
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Wizualizacja

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ąznie 1

program NajdłuższePlateau1(N:integer; A:array[1..N] of integer);
var l,p,w,maks: integer;
  koniec:boolean;
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

Wizualizacja

Wskazówka 2

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

Rozwiąznie 2

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

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Wizualizacja

Ćwiczenie 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łoby 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, wystarczy porównywać wartości A[i] i A[i-maks].

Rozwiąznie 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

Wizualizacja

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

Wizualizacja

Wskazówka 2

W powyższym rozwiązaniu sumę pewnych segmentó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

Wizualizacja

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

Wizualizacja

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 segmentu 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 segmentu 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,maks,suma: integer;
begin
  l:=1;
  p:=1;
  suma:=0;   
  maks:=0;
  while p <= N do
    if suma+A[p] <= 0 then begin
      l:=p+1;
      suma:=0;
      p:=l;
    end
    else begin
      suma:=suma+A[p];
      maks:=max(maks,suma);
      p:=p+1;
    end;
end.

W powyższym programie suma=A[l]+...+A[p-1] i jest to największa suma kończąca się na p-1 (przyjmując, że suma pustego ciągu też kończy się na p-1).

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 o 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

Wizualizacja

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

Wizualizacja

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 dwóch zbiorów wypisać (operacją write) część 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ąznie 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

Wizualizacja

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;
  for ia:=ia to N do write(A[ia], ' ');	//obsługa końcówki A
  for ib:=ib to N do write(B[ib], ' ');	//obsługa końcówki B
end.

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Wizualizacja

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

Wizualizacja

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 tablicy 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

Wizualizacja

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, 1 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[l]:=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

Wizualizacja

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

Wizualizacja

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[0..N-1] 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

Wizualizacja

Wskazówka 2

Można też skorzystać z rozkładu 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[0..N-1] 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[0..N-1] 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 oryginalna tablica, a w kolejnych tablica po kolejnych wywołaniach 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

Wizualizacja

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ą następują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ęść tablicy pozostanie taka sama w następnej permutacji.

Rozwiąznie 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 A[i] > A[i+1] do i:=i-1;
  k:=N;
  while A[k] < A[i] do k:=k-1;
  pom:=A[i];
  A[i]:=A[k];
  A[k]:=pom;
  OdwracanieTablicy(A,i+1,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

Wizualizacja

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 się 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
    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

Wizualizacja

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 o 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

Wizualizacja

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

Dana jest tablica A typu array[1..N] of integer, N > 0. Sprawdź, 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ąznie 1

program Głosowanie1(N:integer; A:array[1..N] of integer);
{Program wypisuje wartość tego elementu, który występuje ponad połowę 
razy, o ile taki istnieje, lub komunikat, że takiego elementu nie ma}
var i,j,ile,indeks_lidera: integer;
begin
  i:=1;
  indeks_lidera:=0; {Zero oznacza, że lidera jeszcze nie znaleźliśmy}
  while (i < (N+1) div 2) and (indeks_lidera=0) do begin
    ile:=0;
    for j:=i to N do if A[i]=A[j] then ile:=ile+1;
    {Tutaj zaczynamy od i, bo nie ma sensu zaczynać wcześniej. I tak, jeśli istnieje lider, 
     to będzie wykryty przy pierwszym jego wystąpieniu}
    if (ile >= N div 2 + 1) then indeks_lidera:=i
    else i:=i+1
  end;
  if indeks_lidera <> 0 then write('Liderem jest: ', A[indeks_lidera])
  else write('Nie ma 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

Wizualizacja

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: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 N 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

Wizualizacja

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:=0 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