Wstęp do programowania / Ćwiczenia 2: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
(Hetmany)
Linia 1: Linia 1:
To są ćwiczenia z rekurencji.
+
Ta strona zawiera podstawowe zadania na tablice.
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
Ogladaj wskazówki i rozwiązania __SHOWALL__<br>
 +
Ukryj wskazówki i rozwiązania __HIDEALL__
 +
</div>
 +
 
 +
 
 +
== 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 &le; i &le; n)
 +
*Z(i,j) - zamienia żetony z i-tej i j-tej urny (1 &le; i,j &le; 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.
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
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.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 2'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
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.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 2'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 3'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
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. 
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 3'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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; kc:=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
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 4'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
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 wiekszych równych od c i miejszych od b są białe.
 +
</div>
 +
</div>
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 4'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Pytanko 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
Dla jakich danych algorytm przedstawiony w Rozwiązaniu 4 dokona N-1 zamian?
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Pytanko 2'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
Jak trzeba by zmienić powyższe rozwiązania, gdyby zamiana Z(i,j) była dozwolona tylko dla i <> j ?
 +
</div>
 +
</div>
 +
 
 +
 
 +
== 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.
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
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.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 2'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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]
 +
        pom:=A[m]; A[m]:=A[w]; A[w]:=A[r]; A[r]:=pom;
 +
        m:=m+1;
 +
        r:=r+1;
 +
        w:=w+1;
 +
      '''end''';
 +
'''end'''.
 +
''Koszt czasowy'': liniowy względem N
 +
 
 +
''Koszt pamięciowy'': stały
 +
</div>
 +
</div>
 +
 
 +
== 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).
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
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).
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''program''' NajdłuższePlateau1(N:integer; A:array[1..N] of integer);
 +
'''var''' l,p,w,maks: integer;
 +
'''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
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 2'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
Dokładnie to samo rozwiązanie można zapisać używając jednej pętli.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 2'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''program''' NajdłuższePlateau2(N:integer; A:array[1..N] of integer);
 +
'''var''' w,p,dl,maks: integer;
 +
'''begin'''
 +
  w:=A[1]; dl:=1; p:=2; maks:=1;
 +
  '''for''' p:=2 '''to''' N '''do''' '''begin'''
 +
    '''if''' A[p]=w '''then''' dl:=dl+1
 +
    '''else''' '''begin'''
 +
      maks:=max(maks, dl);
 +
      dl:=1;
 +
    '''end''';
 +
  '''end''';
 +
  maks:=max(maks, dl);
 +
'''end'''.
 +
''Koszt czasowy'': liniowy względem N
 +
 
 +
''Koszt pamięciowy'': stały
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Pytanko 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
Czy przedostatnia linia programu w Rozwiązaniu 2 jest potrzebna? Co by było gdyby jej nie było ?
 +
</div>
 +
</div>
 +
===Inna wersja zadania===
 +
A co było gdyby tablica była posortowana ?
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 3'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
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 to wystarczy porównywać wartości A[i] i A[i-maks]. 
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 3'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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
 +
</div>
 +
</div>
 +
 
 +
== 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.
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
Najprostsze rozwiązanie to dla wszystkich możliwych segmentów policzyć ich sumę.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 2''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
W powyższym rozwiązaniu sumę pewnych segmantó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.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 2'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 3'''  <div class="mw-collapsible-content" style="display:none">
 +
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].
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 3'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 4'''  <div class="mw-collapsible-content" style="display:none">
 +
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 segmantu 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 segmantu o maksymalnej sumie. Jedyną sensowną możliwością jest rozpatrywanie segmentów które zaczynają się od p+1. 
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 4'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''program'''  SegmentOMaksymalnejSumie4(N:integer; A:array[1..N] of integer);
 +
'''var''' l,p,i,biez,maks: integer;
 +
'''begin'''
 +
  l:=1;
 +
  p:=2;
 +
  suma:=A[l]; 
 +
  maks:=max(0,suma);
 +
  while p <= N '''do'''
 +
    '''if''' suma+A[p] <= 0 '''then''' '''begin'''
 +
      l:=p+1;
 +
      suma:=A[l];
 +
      p:=l+1;
 +
      maks:=max(0,suma);
 +
    '''else''' '''begin'''
 +
      suma:=suma+A[p];
 +
      maks:max(0,suma);
 +
      p:=p+1;
 +
    '''end''';
 +
'''end'''.
 +
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 a 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
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 5'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
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
 +
</div>
 +
</div>
 +
 
 +
== 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 dwu
 +
zbiorów wypisać (operacją write) cześć wspólną tych zbiorów.
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1'''  <div class="mw-collapsible-content" style="display:none">
 +
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. 
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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
 +
</div>
 +
</div>
 +
 
 +
== 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.
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1'''  <div class="mw-collapsible-content" style="display:none">
 +
Dopóki istnieją elementy w obu tablicach przesuwamy się tak jak przy obliczaniu części wspólnej, potem obługujemy końcówki tablic.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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''';
 +
  '''while''' ia <= N '''do''' write(A{ia], ' '); //obsługa końcówki A
 +
  '''while''' ib <= N '''do''' write(B{ib], ' '); //obsługa końcówki B
 +
'''end'''.
 +
''Koszt czasowy'': liniowy względem N
 +
 
 +
''Koszt pamięciowy'': stały
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Pytanko 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
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 ?
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 2'''  <div class="mw-collapsible-content" style="display:none">
 +
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.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 2'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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
 +
</div>
 +
</div>
 +
 
 +
== Zadanie 7 (Podciąg) ==
 +
Dane 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)]).
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1'''  <div class="mw-collapsible-content" style="display:none">
 +
Każdy element tablcy 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. 
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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
 +
</div>
 +
</div>
 +
 
 +
== 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.
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1'''  <div class="mw-collapsible-content" style="display:none">
 +
Należy zamienić element 0 z N-1, 2 z N-2 itd.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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[p]:=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
 +
</div>
 +
</div>
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 2'''  <div class="mw-collapsible-content" style="display:none">
 +
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.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 2'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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
 +
 
 +
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'''.
 +
</div>
 +
</div>
 +
 
 +
== 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.
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
Najprościej rozwiązać to zadanie używając dodatkowej pamięci rozmiaru N.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''program''' Przesuń1(N,k:integer; A:array[1..N] 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
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 2''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
Można też skorzystać z rozkladu 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.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 2'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''program''' Przesuń2(N,k:integer; A:array[1..N] 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
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 3''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
Można też zauważyć, że przesunięcie cykliczne o k w prawo można zrealizować poprzez trzy odwrócenia pewnych segmentów tablicy.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 3'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''program''' Przesun3(N,k:integer; A:array[1..N] 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 aryginalna tablica, a w kolejnych tablica po kolejnych wywolaniach 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
 +
</div>
 +
</div>
 +
 
 +
== 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ą nastepująco:
 +
1 2 3
 +
1 3 2
 +
2 1 3
 +
2 3 1
 +
3 1 2
 +
3 2 1
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
Zastanów się która część talicy pozostanie taka sama w następnej permutacji.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 1''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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''' 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;
 +
    OdwracanieTablicy(A,i,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
 +
</div>
 +
</div>
 +
 
 +
== 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<math>=A[l]+...+A[p-1]</math>).
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
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 sie w l.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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'''
 +
    maks:=0;
 +
    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
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 2''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
Podobnie jak w zadaniu o segmencie o maksymalnej sumie możliwe też jest rozwiązanie o liniowym koszcie czasowym.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 2'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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 a 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
 +
</div>
 +
</div>
 +
 
 +
== Zadanie 12 (Głosowanie większościowe) ==
 +
Dana jest tablica A typu array[1..N] of integer, N > 0. Sprawdzić czy jest w niej element wystepujący więcej niż N/2 razy i jeśli tak wskaż go.
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
Najprościej jest dla każdego elementu policzyć liczbę wystąpień w tablicy. Jest to oczywiście rozwiązanie o kwadratowym koszcie czasowym.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 1'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''program''' Głosowanie1(N:integer; A:array[1..N] of integer);
 +
'''var''' i,j,ile,indeks_lidera: integer;
 +
'''begin'''
 +
  i:=1;
 +
  indeks_lidera:=0;
 +
  '''while''' (i < (N+1) div 2) '''and''' (indeks_lidera=0) '''do''' '''begin'''
 +
    ile:=0;
 +
    '''for j:=1 '''to''' N '''do''' if A[i]=A[j] '''then''' ile:=ile+1;
 +
    '''if''' (ile >= N div 2 + 1) '''then''' indeks_lidera:=i;
 +
  '''end''';
 +
  '''if''' indeks_lidera <> 0 '''then''' write('Liderem jest: ', A[indeks_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
 +
</div>
 +
</div>
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 2''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
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ł.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 2'''
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''program''' Głosowanie2(N,W: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''' '''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
 +
</div>
 +
</div>
 +
 
 +
== 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:
 +
# 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).
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie 1''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
'''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:=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;
 +
    p:=0;
 +
  '''end''';
 +
'''end''';
 +
''Koszt czasowy'': kwadratowy względem N
 +
 
 +
''Koszt pamięciowy'': stały
 +
</div>
 +
</div>
 +
 
  
 
==Zadanie 1 (Labirynt)==
 
==Zadanie 1 (Labirynt)==

Wersja z 10:11, 24 lip 2006

Ta strona zawiera podstawowe zadania na tablice.

Ogladaj 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

Rozwiązanie 1

Wskazówka 2

Rozwiązanie 2

Wskazówka 3

Rozwiązanie 3

Wskazówka 4

Rozwiązanie 4

Pytanko 1

Pytanko 2


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 1

Rozwiązanie 2

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

Rozwiązanie 1

Wskazówka 2

Rozwiązanie 2

Pytanko 1

Inna wersja zadania

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

Wskazówka 3

Rozwiązanie 3

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

Rozwiązanie 1

Wskazówka 2

Rozwiązanie 2

Wskazówka 3

Rozwiązanie 3

Wskazówka 4

Rozwiązanie 4

Rozwiązanie 5

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 dwu zbiorów wypisać (operacją write) cześć wspólną tych zbiorów.

Wskazówka 1

Rozwiązanie 1

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

Rozwiązanie 1

Pytanko 1

Wskazówka 2

Rozwiązanie 2

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

Rozwiązanie 1

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

Rozwiązanie 1

Wskazówka 2

Rozwiązanie 2

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

Rozwiązanie 1

Wskazówka 2

Rozwiązanie 2

Wskazówka 3

Rozwiązanie 3

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ą nastepująco:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Wskazówka 1

Rozwiązanie 1

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

Wskazówka 1

Rozwiązanie 1

Wskazówka 2

Rozwiązanie 2

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

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

Wskazówka 1

Rozwiązanie 1

Wskazówka 2

Rozwiązanie 2

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


Zadanie 1 (Labirynt)

Czy istnieje ścieżka miedzy wskazanymi punktami (i1,j1) i (i2,j2) w labiryncie reprezentowanym przez prostokątną tablicę liczb całkowitych o rozmiarze M×N, zawierającą zera (ściana) i jedynki (droga)? Zakładamy, że nie można przechodzić z pola na pole po skosie (np. z (2,5) na (3,6)), a tylko w czterech podstawowych kierunkach (np. z (2,5) na (3,5), (2,4) itd.)

Wskazówka 1

Rozwiązanie 1

Pytanko 1:

Pytanko 2:

Pytanko 3: (trudniejsze)

Odpowiedź:

Dla ciekawskich:

Zadanie 2 (Z górki na pazurki)

W tablicy liczb całkowitych o rozmiarze M×N zapisana jest mapa gór (każdy punkt ma podaną dodatnią wysokość). Sprawdzić, czy da się przejść z punktu startowego (i1,j1) do docelowego (i2,j2) idąc:

  • tylko w dół lub po płaskim
  • tylko w dół

Tak jak w poprzednim zadaniu poruszać się można tylko w czterech kierunkach podstawowych, nie po przekątnej.

Wskazówka 1

Rozwiązanie 1

Rozwiązanie 2

Zadanie 3 (Wieże Hanoi z ograniczeniami)

Na wykładzie były wieże Hanoi. Ciekawa modyfikacja tego zadania polega na zabronieniu ruchów pomiędzy niektórymi pałeczkami, np. z pierwszej na drugą. Zapisać procedurę realizującą to zadanie przy zabronionych niektórych ruchach.

Wskazówka 1

Rozwiązanie 1

Pytanko 1

Odpowiedź

Zadanie 4 (Ustawianie hetmanów)

Napisz procedurę znajdująca wszystkie takie rozstawienia 8 hetmanów na szachownicy, by żadne dwa hetmany się nie atakowały.

Wskazówka 1

Rozwiązanie 1

Zadanie 5 (Mnożenie wielomianów)

Dane są dwie tablice (array[0..N-1] of real) reprezentujące dwa wielomiany stopnia N-1. Należy obliczyć iloczyn tych wielomianów metodą dziel-i-zwyciężaj. Zakładamy, że N jest potęgą dwójki.

Wskazówka 1

Zadanie 6 (Suma składników)

Napisz procedurę, która wypisze dla zadanej liczby n jej wszystkie rozkłady na sumy nieujemnych liczb naturalnych większych od 1 ustawionych w kolejności nierosnącej. Np. dla n = 3:
3 = 3
3 = 2+1
3 = 1+1+1

Wskazówka 1

Wskazówka 2

Rozwiązanie 1