Tekst źródłowy strony Wstęp do programowania / Ćwiczenia 2

{{powrot|WDP_Wprowadzenie_do_programowania|do modułu Wprowadzenie do programowania}}

Ta strona zawiera podstawowe zadania na tablice.

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Oglądaj 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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 2</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 2</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 3</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 3</span>
<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; 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
</div>
</div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 4</span>
<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 większych lub równych c i miejszych od b są białe. </div>
</div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 4</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Ćwiczenie 1</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Ćwiczenie 2</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
<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

[[pimp:modul2_2_1.html|Wizualizacja]]

</div>
</div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 2</span>
<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] 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

[[pimp:modul2_2_2.html|Wizualizacja]]

</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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiąznie 1</span>
<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;
   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

[[pimp:modul2_3_1.html|Wizualizacja]]

</div>
</div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 2</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiąznie 2</span>
<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;
   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

[[pimp:modul2_3_2.html|Wizualizacja]]

</div>
</div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Ćwiczenie 1</span>
<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łoby gdyby tablica była posortowana ?

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 3</span>
<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, wystarczy porównywać wartości A[i] i A[i-maks].  
</div>
</div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiąznie 3</span>
<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

[[pimp:modul2_3_3.html|Wizualizacja]]

</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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
<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

[[pimp:modul2_4_1.html|Wizualizacja]]

</div>
</div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 2</span>
<div class="mw-collapsible-content" style="display:none">
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.
</div>
</div>
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 2</span>
<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

[[pimp:modul2_4_2.html|Wizualizacja]]

</div>
</div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 3</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 3</span>
<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

[[pimp:modul2_4_3.html|Wizualizacja]]

</div>
</div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 4</span>
<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 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.  
</div>
</div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 4</span>
<div class="mw-collapsible-content" style="display:none">
 '''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

[[pimp:modul2_4_4.html|Wizualizacja]]

</div>
</div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 5</span>
<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

[[pimp:modul2_4_5.html|Wizualizacja]]

</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 dwóch
zbiorów wypisać (operacją write) część wspólną tych zbiorów.
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiąznie 1</span>
<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

[[pimp:modul2_5_1.html|Wizualizacja]]

</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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
<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''';
   '''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

[[pimp:modul2_6_1.html|Wizualizacja]]

</div>
</div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Ćwiczenie 1</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 2</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 2</span>
<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

[[pimp:modul2_6_2.html|Wizualizacja]]

</div>
</div>

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

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
<div class="mw-collapsible-content" style="display:none">
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.   
</div>
</div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
<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

[[pimp:modul2_7_1.html|Wizualizacja]]

</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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
<div class="mw-collapsible-content" style="display:none">
Należy zamienić element 0 z N-1, 1 z N-2 itd.
</div>
</div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
<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[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

[[pimp:modul2_8_1.html|Wizualizacja]]

</div>
</div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 2</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 2</span>
<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

[[pimp:modul2_8_2.html|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'''. 
</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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
<div class="mw-collapsible-content" style="display:none">
 '''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

[[pimp:modul2_9_1.html|Wizualizacja]]

</div>
</div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 2</span>
<div class="mw-collapsible-content" style="display:none">
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. 
</div>
</div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 2</span>
<div class="mw-collapsible-content" style="display:none">
 '''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
</div>
</div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 3</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 3</span>
<div class="mw-collapsible-content" style="display:none">
 '''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

[[pimp:modul2_9_3.html|Wizualizacja]]

</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ą następują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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
<div class="mw-collapsible-content" style="display:none">
Zastanów się, która część tablicy pozostanie taka sama w następnej permutacji.
</div>
</div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiąznie 1</span>
<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''' 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

[[pimp:modul2_10_1.html|Wizualizacja]]

</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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
<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 się w l.
</div>
</div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
<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'''
     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

[[pimp:modul2_11_1.html|Wizualizacja]]

</div>
</div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 2</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 2</span>
<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 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

[[pimp:modul2_11_2.html|Wizualizacja]]

</div>
</div>

== 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.
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiąznie 1</span>
<div class="mw-collapsible-content" style="display:none">
 '''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

[[pimp:modul2_12_1.html|Wizualizacja]]

</div>
</div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 2</span>
<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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 2</span>
<div class="mw-collapsible-content" style="display:none">
 '''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

[[pimp:modul2_12_2.html|Wizualizacja]]

</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">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
<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:=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
</div>
</div>