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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 22: Linia 22:
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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>
+
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>
 
}}
 
}}
Linia 73: Linia 73:
 
     '''end''';
 
     '''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)).  
+
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 czasowy'': liniowy względem N
Linia 85: Linia 85:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<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>
+
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>
 
}}
 
}}
Linia 118: Linia 118:
 
       '''end;'''
 
       '''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.  
+
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 czasowy'': liniowy względem N
Linia 130: Linia 130:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<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>
+
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>
 
}}
 
}}
Linia 171: Linia 171:
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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.
+
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>}}
 
</div>}}
Linia 295: Linia 295:
  
 
{{cwiczenie| 1|pytanko 1|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{cwiczenie| 1|pytanko 1|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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 ?
+
Czy przedostatnia linia programu w Rozwiązaniu 2 jest potrzebna? Co by było, gdyby jej nie było?
 
</div>
 
</div>
 
</div>}}
 
</div>}}
  
 
===Inna wersja zadania===  
 
===Inna wersja zadania===  
A co było gdyby tablica była posortowana ?
+
A co byłoby gdyby tablica była posortowana ?
  
 
{{wskazowka| 3||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 3||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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].   
+
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>}}
 
</div>}}
Linia 354: Linia 354:
  
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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.
+
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>}}
 
</div>}}
Linia 406: Linia 406:
  
 
{{wskazowka| 4||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 4||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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.   
+
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>}}
 
</div>}}
Linia 465: Linia 465:
 
Dane są dwie tablice A i B typu array[1..N] of integer, N > 0. Obie są
 
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
 
posortowane rosnąco. Należy traktując A i B jako reprezentacje dwu
zbiorów wypisać (operacją write) cześć wspólną tych zbiorów.
+
zbiorów wypisać (operacją write) część wspólną tych zbiorów.
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Linia 502: Linia 502:
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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.
+
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>}}
 
</div>}}
Linia 544: Linia 544:
  
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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.
+
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>}}
 
</div>}}
Linia 590: Linia 590:
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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.   
+
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>}}
 
</div>}}
Linia 649: Linia 649:
  
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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.
+
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>}}
 
</div>}}
Linia 711: Linia 711:
  
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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.  
+
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>}}
 
</div>}}
Linia 728: Linia 728:
 
       pom:=A[nast];       //wstawiamy akt na A[nast]
 
       pom:=A[nast];       //wstawiamy akt na A[nast]
 
       A[nast]:=akt;
 
       A[nast]:=akt;
       akt:=pom;                       //to co tam było będzie nowym akt
+
       akt:=pom;                       //to co tam było, będzie nowym akt
 
       nast:=(nast+k) '''mod''' N;            //obliczamy nowe nast
 
       nast:=(nast+k) '''mod''' N;            //obliczamy nowe nast
 
     '''end''';
 
     '''end''';
Linia 752: Linia 752:
 
   OdwracanieTablicy(A,0,N-1);
 
   OdwracanieTablicy(A,0,N-1);
 
  '''end'''.
 
  '''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.
+
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(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-k)    ...        a(N-1)
Linia 767: Linia 767:
  
 
== Zadanie 10 (Następna permutacja) ==
 
== 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.
+
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:
 
'''Przykład''' Dla N=3 kolejne permutacje w [[porządku leksykograficznym]] wyglądają nastepująco:
Linia 778: Linia 778:
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Zastanów się która część talicy pozostanie taka sama w następnej permutacji.
+
Zastanów się, która część talicy pozostanie taka sama w następnej permutacji.
 
</div>
 
</div>
 
</div>}}
 
</div>}}
Linia 807: Linia 807:
 
Procedura OdwracanieTablicy pochodzi z Zadania 8.
 
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.
+
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 czasowy'': liniowy względem N
Linia 818: Linia 818:
  
 
== Zadanie 11 (Segment o danej sumie)  ==
 
== 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>).
+
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>).
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
Podobnie jak w zadaniu o segmencie o maksymalnej sumie można dla  
 
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.
+
danego początku l obliczać po kolei sumy coraz dłuższych segmentów zaczynających się w l.
 
</div>
 
</div>
 
</div>}}
 
</div>}}
Linia 858: Linia 858:
  
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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.
+
Podobnie jak w zadaniu o segmencie o maksymalnej sumie, możliwe też jest rozwiązanie o liniowym koszcie czasowym.
 
</div>
 
</div>
 
</div>}}
 
</div>}}
Linia 873: Linia 873:
 
     suma:=0;
 
     suma:=0;
 
     '''while''' (suma <> W) '''and''' (p <= N) '''do'''
 
     '''while''' (suma <> W) '''and''' (p <= N) '''do'''
       '''if''' suma < W '''then''' '''begin''' //jeśli suma jest za mała to przesuwamy prawy koniec segmentu
+
       '''if''' suma < W '''then''' '''begin''' //jeśli suma jest za mała, to przesuwamy prawy koniec segmentu
 
         suma:=suma+A[p];
 
         suma:=suma+A[p];
 
         p:=p+1;
 
         p:=p+1;
 
       '''end'''
 
       '''end'''
       '''else''' '''begin''' //jeśli za duża to przesuwamy lewy koniec segmentu
+
       '''else''' '''begin''' //jeśli za duża, to przesuwamy lewy koniec segmentu
 
         suma:= suma-A[l];
 
         suma:= suma-A[l];
 
         l:=l+1;
 
         l:=l+1;
 
       '''end''';
 
       '''end''';
     '''while''' (suma > W) '''do''' '''begin'''          //jeśli suma nadal za duża to próbujemy ją zmniejszyć
+
     '''while''' (suma > W) '''do''' '''begin'''          //jeśli suma nadal za duża, to próbujemy ją zmniejszyć
 
       suma:= suma-A[l];
 
       suma:= suma-A[l];
 
       l:=l-1;
 
       l:=l-1;
Linia 889: Linia 889:
 
   '''if''' znalezione '''then''' write('W tablicy A istnieje segment o sumie W');  
 
   '''if''' znalezione '''then''' write('W tablicy A istnieje segment o sumie W');  
 
  '''end'''.
 
  '''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
+
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.
+
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 czasowy'': liniowy względem N
Linia 901: Linia 901:
  
 
== Zadanie 12 (Głosowanie większościowe) ==
 
== 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.
+
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.
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Linia 938: Linia 938:
  
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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ł.
+
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>}}
 
</div>}}
Linia 957: Linia 957:
 
       '''end''';
 
       '''end''';
 
   '''end''';
 
   '''end''';
   ile:=0; //sprawdzamy czy kandydat jest liderem
+
   ile:=0; //sprawdzamy, czy kandydat jest liderem
 
   '''for''' i:=1 '''to''' N '''do'''  
 
   '''for''' i:=1 '''to''' N '''do'''  
 
     '''if''' A[i]=kand '''then''' ile:=ile+1;  
 
     '''if''' A[i]=kand '''then''' ile:=ile+1;  
Linia 978: Linia 978:
 
== Zadanie 13 (Arytmetyka liczb wielocyfrowych) ==
 
== 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:
 
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.
+
# 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.
+
# 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).  
 
# 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).  
  
Linia 991: Linia 991:
 
   
 
   
 
  '''procedure''' Suma(A,B:liczba, var C:liczba, var:przepełnienie:boolean);
 
  '''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.
+
  //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;
 
  '''var''' p: integer;
 
  '''begin'''
 
  '''begin'''

Wersja z 20:21, 15 lis 2006

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

Ta strona zawiera podstawowe zadania na tablice.

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__


Zadanie 1 (Flaga polska)

Tablica A typu array[1..N] of integer (N > 0) wypełniona zerami i jedynkami reprezentuje ciąg N urn w których znajdują się żetony białe (0) i czerwone (1). Podaj algorytm działania automatu przestawiającego żetony w urnach tak, by najpierw były żetony czerwone, potem białe. Robot może wykonywać dwa rodzaje operacji:

  • Kol(i) - podaje kolor żetonu w i-tej urnie (1 ≤ i ≤ n)
  • Z(i,j) - zamienia żetony z i-tej i j-tej urny (1 ≤ i,j ≤ n)

Uwagi:

  1. Operacja Kol jest bardzo kosztowna, więc zależy nam na tym by kolor każdego żetonu był sprawdzany co najwyżej raz.
  2. Robot potrafi zapamiętać tylko kilka wartości z przedziału 0..N+1.
  3. Nie można założyć, że występuje choć jeden żeton w każdym z kolorów.


Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}

Wskazówka 3

{{{3}}}

Rozwiązanie 3

{{{3}}}

Wskazówka 4

{{{3}}}

Rozwiązanie 4

{{{3}}}


Ćwiczenie 1

{{{3}}}

Ćwiczenie 2

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Rozwiązanie 2

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}

Ćwiczenie 1

{{{3}}}

Inna wersja zadania

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

Wskazówka 3

{{{3}}}

Rozwiązanie 3

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}

Wskazówka 3

{{{3}}}

Rozwiązanie 3

{{{3}}}

Wskazówka 4

{{{3}}}

Rozwiązanie 4

{{{3}}}

Rozwiązanie 5

{{{3}}}

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) część wspólną tych zbiorów.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}

Wskazówka 3

{{{3}}}

Rozwiązanie 3

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}

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

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

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}

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

{{{3}}}