Algorytmy i struktury danych (2 semestr – 1 rok – inny program – stare zadania)

1) Napisz   funkcję   w   Turbo   Pascalu   o   nazwie   PLP,   która   dla   zadanego   parametru 

całkowitego n znajduje najmniejszą liczbę pierwszą nie mniejszą niż n.

2) Napisz   funkcję   w   Turbo   Pascalu   o   nazwie   PLP,   która   dla   zadanego   parametru 

naturalnego k znajduje największą liczbę pierwszą nie większą niż k.

3) Niech (x

i

,y

i

)  i=1, 2, …, k  oznaczają kolejne wierzchołki wielokąta na płaszczyźnie. 

Napisz program w TP, który wczytuje k, oraz współrzędne wierzchołków wielokąta, a 

następnie   sprawdza   czy   wielokąt   jest   właściwy,   tzn.,   że   żadne   dwa   boki   tego 

wielokąta nie przecinają się.

4) Niech (x

i

,y

i

)  i=1, 2, …, n  oznaczają kolejne wierzchołki wielokąta na płaszczyźnie. 

Napisz program w TP, który wczytuje n, oraz współrzędne wierzchołków wielokąta, 

a następnie sprawdza czy wielokąt jest wypukły.

P(x

1

,y

1

)    Q(x

2

,y

2

)    R(x

3

,y

3

)

det



P , Q , R



=det

[

x

1

y

1

1

x

2

y

2

1

x

3

y

3

1

]

=



x

2

− x

1



y

3

− y

1



−



x

3

− x

1



y

2

− y

1



det



P , Q , R



=0  - R leży na prostej

det



P , Q , R



0  - R leży po lewej stronie prostej (jak na rysunku)

det



P , Q , R



0  - R leży po prawej stronie prostej

 

5) Niech  A oznacza macierz kwadratową o wymiarach  n × n. Napisz procedurę, która 

dla zadanej liczby  r<n  oblicza ciąg  S

k

, k=1, 2, …, n-r,  gdzie  S

k 

jest równe sumie 

wszystkich elementów macierzy A

k+i,n-k+1+j

 i=0, 1, …, r, j=0, 1, …, r.

6) Niech  A oznacza macierz kwadratową o wymiarach  n × n. Napisz procedurę, która 

dla zadanej liczby  r<n  oblicza ciąg  S

k

, k=1, 2, …, n-r,  gdzie  S

k 

jest równe sumie 

wszystkich elementów macierzy A

k+i,k+j

 i=0, 1, …, r, j=0, 1, …, r.

7) Niech A oznacza miacierz kwadratową n × n. Należy opracować algorytm obliczania 

maksymalnej sumy według następujących reguł: zaczynamy sumawanie od elementu 

A

11

, jeśli do sumy wchodzi element  A

ij

  to jako następny mamy prawo dosumować 

element A

i+1,j

 lub A

i+1,j+1

 (z każdego wiersza znajdzie się sumie tylko jeden element).

8) Kopalnia złota. Dane są na płaszczyźnie współrzędne n punktów (x

i

,y

i

) (położenie 

samorodków złota). Masz jako pierwszy prawo wyboru działki o wymiarach a × b, o 

bokach   równoległych   od   osi   układu.   Opracuj   algorytm,   który   ustali   współrzędne 

lewego dolnego wierzchołka twojej działki tak by działka zawierała jak najwięcej 

samorodków. Zakładamy, że zarówno współrzędne punktów jak i wymiary działki są 

liczbami całkowitymi. Samorodki leżące na brzegu działki należą do Ciebie.

9)   Napisz w TP procedurę SORT_STUD(k:INTEGER;VAR a:spis), która sortuje malejąco 

listę studentów względem lat studiów. Oto definicja typów:

Student= RECORD
           nazwisko: STRING[30];

       rok: 1..5;
     END;

spis=ARRAY[1..200] OF student;

P .

Q .

R .

Uwaga! Czy możliwe jest zrealizowanie tego zadania przy dwukrotnym przeglądaniu 

spisu?

10)  Napisz   w   TP   procedurę   SORT_OCENA(n:INTEGER;VAR   a:lista),   która   sortuje 

malejąco listę studentów względem ocen. Oto definicja typów:

Student= RECORD
           nazwisko: STRING[30];

       ocena: STRING[4];
     END;

Lista=ARRAY[1..200] OF student;

Uwaga!   Dopuszczalne   oceny:  ndst,   dost,   dst+,   db,   db+,   bdb.   Czy   możliwe   jest 

zrealizowanie tego zadania przy dwukrotnym przeglądaniu listy?

11) Definicja. Ciąg {a

i

} i=1, 2, …, m liczb rzeczywistych nazywamy jednopikowym, jeśli 

istnieje   liczba   naturalna  p  taka,   że   ciąg   {a

i

}   jest   malejący   dla  i=1,   2,   …,   p  oraz 

rosnący  dla i=p, p+1, …, m. Napisz funkcję w Pascalu, która dla danego  m  oraz 

jednopikowego ciągu {a

i

} znajduje najmniejszy element.

12)  Definicja.   Ciąg   {x

i

}  i=1,   2,   …,   n  nazywamy   jednopikowym,   jeśli   istnieje   liczba 

naturalna k taka, że ciąg {x

i

} jest rosnący dla i=1, 2, …, k oraz malejący dla i=k, k+1, 

…, n. Napisz funkcję typu Integer w Pascalu, która dla danego n oraz jednopikowego 

ciągu {x

i

} znajduje numer jego największego elementu.

13)  Głosowanie   przez  INTERNET.   Program  w  TP.  Wyniki  głosowania  znajdują   się  w 

pliku   tekstowym   d:\ankieta\PLUS.TXT.   W   pliku   tym   znajduje   się   nieznana   liczba 

wierszy.   Każdy   wiersz   zawiera  2  liczby,   z   których   pierwsza   jest  6-cio  cyfrowym 

numerem telefonu, a druga oznacza numer k kandydata, na którego oddano z tego 

telefonu głos, 1≤k≤10.

1. Napisz   program   w   TP,   który   zlicza   ile   głosów   oddano   na   poszczególnych 

kandydatów. Wyniki wyświetl na ekranie.

2. Napisz   program   w   TP,   który   zlicza   ile   głosów   oddano   na     poszczególnych 

kandydatów przy założeniu, że z każdego numeru telefonu można zaliczyć do 

wyników głosowania tylko jeden głos.

14)  Głosowanie   przez  INTERNET.   Program  w  TP.  Wyniki  głosowania  znajdują   się  w 

pliku   tekstowym   c:\glosowanie\ERASMS.TXT.   W   pliku   tym   znajduje   się   nieznana 

liczba   wierszy.   Każdy   wiersz   zawiera  2  liczby,   z   których   pierwsza   jest  6-cio 

cyfrowym   numerem   telefonu,   a   druga   oznacza   numer  k  kandydata,   na   którego 

oddano z tego telefonu głos, 1≤k≤12.

1. Napisz   program   w   TP,   który   zlicza   ile   głosów   oddano   na   poszczególnych 

kandydatów. Wyniki wyświetl na ekranie.

2. Napisz   program   w   TP,   który   zlicza   ile   głosów   oddano   na     poszczególnych 

kandydatów przy założeniu, że z każdego numeru telefonu można zaliczyć do 

wyników głosowania tylko jeden głos.

Semestr II – teoria (2 semestr – 1 rok – inny program – stare zadania)

1) Jaka   jest   przeciętna   złożoność   algorytmu   wyszukiwania   elementu   w   tablicy 

posortowanej metodą bisekcji a jaka metodą interpolacyjną?

2) Ile   razy   (przeciętnie)   jest   szybszy   algorytm  QUICKSORT  w   porównaniu   z 

INSERTSORT dla n=21

12

?

3) Definicja drzewa: RST.

4) Drzewo AVL. Co to jest atrybut wierzchołka? Na czym polega rotacja pojedyncza?

5) Podaj   oszacowanie   od   dołu   dla   problemu   sortowania   zbioru  n-elementowego   z 

implementacją tablicową.

6) Podstawowe własności programowania obiektowego.

7) Przykład funkcji mieszającej.

8) Jakie znasz metody usuwania kolizji przy zastosowaniu funkcji mieszającej?

9) Zastosowanie oraz idea KM (Karpa-Millera).

10)Definicja kopca zupełnego (złożoność pesymistyczna wyszukiwania informacji).

Algorytmy i struktury danych (2 rok)

1) Dany jest n-elementowy ciąg par liczb naturalnych:

(p

i

,q

i

)

1<p

i

≤q

i

<k i=1,2,..., n.

Definicja wagi liczby naturalnej: liczba  1  ma wagę  1. Każda liczba występująca w 

parze z 1 ma wagę 2, każda liczba występująca w parze z liczbą o wadze 2 ma wagę 3, o 

ile wcześniej nie miała ustalonej wagi 1 lub  2. W podobny sposób definiujemy liczby o 

wadze 4, 5 itd. Liczby dla których nie uda się zdefiniować w ten sposób wagi mają wagę 0. 

Napisz program, który wyświetli tabelę wynikową liczb kolejno o wagach 2, 3, 4 i 5.

Wagi przykład (pary nie muszą być posortowane wg. pierwszego elementu)

p 1 1 2 2 3 3 5 7 7 7

q 3 5 5 8 4 5 7 8 9 1

0

(chyba zły przykład)

liczba 1 2 3 4 5 6 7 8 9 10

waga 1 3 2 3 2 0 3 4 4

4

Wagi przykład 2 (pary nie muszą być posortowane wg. pierwszego elementu)

p 1 1 2

q 3 5 5

liczba

1 2 3 4 5 6 7 8

waga

1 0 4 2 0 0 0 3

2) Dany jest n-elementowy ciąg par liczb naturalnych:

(p

i

,q

i

)

1<p

i

≤q

i

<k i=1,2,..., n.

Definicja wagi liczby naturalnej: liczba  1  ma wagę  1. Każda liczba występująca w 

parze z 1 ma wagę 2, każda liczba występująca w parze z liczbą o wadze 2 ma wagę 3, o 

ile wcześniej nie miała ustalonej wagi 1 lub 2. W podobny sposób definiujemy liczby o 

wadze 4, 5 itd. Liczby dla których nie uda się zdefiniować w ten sposób wagi mają wagę 

0.   Napisz   program,   który   wyświetli   tabelę   wynikową   liczb   według   rosnących   wag 

pomijając liczby o wadze 0.

3) Ciąg liczb całkowitych (n-elementowy) nazywamy nieparzystym wesołym skoczkiem, 

jeśli   wartości   bezwzględne   różnic   pomiędzy   kolejnymi   elementami   przyjmują 

wszystkie   możliwe   nieparzyste   wartości   pomiędzy  1  i  2n-3.   Napisz   funkcję   typu 

Boolean, która sprawdza czy dany ciąg {a

i

} jest nieparzystym wesołym skoczkiem.

4) Ciąg liczb całkowitych (n-elementowy) nazywamy parzystym wesołym skoczkiem, jeśli 

wartości   bezwzględne   różnic   pomiędzy   kolejnymi   elementami   przyjmują   wszystkie 

możliwe   parzyste   wartości   pomiędzy  2  i  2n-2.   Napisz   funkcję   typu   Boolean,   która 

sprawdza czy dany ciąg {a

i

} jest parzystym wesołym skoczkiem.

5) Zakład stolarski zebrał  n  zamówień na usługi w  2005  r. Każde zamówienie zawiera 

cztery informacje: nazwisko klienta, liczbę dni potrzebnych na wykonanie usługi (w

i

), 

termin  wykonania usługi (t

i

), 1≤t

i

≤250,  kara za każdy dzień zwłoki po terminie (k

i

). 

Napisz   procedurę,   która   ustali   kolejność   wykonywania   usług   tak   by   kara     za 

niedotrzymanie   terminów   była   możliwie   mała.   Zakładamy,   że   w   ciągu   roku   usług 

planujemy na następny rok, numerując te dni od 251 do 500. Sprawdzenie wszystkich 

n!  możliwości   jest   oczywiście   niemożliwe,   dlatego   jeśli   nie   masz   lepszego   pomysłu 

zastosuj metodę typy INSERTSORT, zaczynając do usług, które mają najwcześniejszy 

termin wykonania.

6) Zaproponuj strukturę danych dla grafu i napisz program sprawdzający, czy dany graf 

jest dwukolorowalny, tzn. czy jego wierzchołki mogą być pomalowane na kolory biały i 

czarny w taki sposób, aby sąsiadujące ze sobą wierzchołki nigdy nie były tego samego 

koloru. Założenie: graf jest spójny i nieskierowany.

Dane: n – liczba wierzchołków, 1<n<200, m – liczba krawędzi grafu, oraz ciąg krawędzi 

i

k

, j

k

, gdzie 1≤i

k

<j

k

≤n, k=1, 2, ..., m.

Jaką własność mają cykle w grafach dwukolorowalnych?

7) Zakład usługowy ma do wykonania n zleceń. Podane są: 

• czas potrzebny na wykonanie zlecenia g[i] godzin oraz m[i] minut, i=1,2, ..., n 

• wartość zlecenia z[i] złotych. 

Ustal kolejność zleceń tak by zlecenia najbardziej opłacalne (stawka na godz) były na 

początku. W przypadku identycznej stawki godzinowej w pierwszej kolejności powiimy 

wystąpić   zlecenia   wymagające   mniej   czasu   na   jego   wykonanie.   Napisz   schemat   NS 

programu, który zrealizuje powyższe zadanie dla danych: 

n 

nr zlecenia[l], g[l], m[l], [1] 

nr zlecenia[2], g[2], m2], z[2] 

nr zlecenia[n], g[n], m[n], z[n] 

8) Pracujesz w PLL LOT. Masz napisać program, który dla wybranej pary miast na świecie 

będzie   znajdował   najkrótsze   połączenia.   Zanim   zrealizujesz   to   zadanie   w   całości 

musisz rozwiązać kilka 

pomocniczych zadań. Ustawienie danych: 

n {liczba miast}

nazwa_miasta[1], dlugosc_geograficzna[l], szerokosc_geograficzna[1] 

nazwa_miasta 121, dlugosc_geograficzna 121, szerokosc_geograficzna [2]

...

nazwa_miastami, dlugosc_geograficzna[n], szerokosc_geograficzna[n]

m {liczba połączeń lotniczych}

p[l], q[l] {numery miast tworzących pierwszą linię lotniczą}

p[2], q[2] 

p[m], q[m]

Zakładamy,   że   promień   kuli   ziemskiej  R=6738km,   szerokość   geograficzna   może 

przyjmować wartości od  -90  (biegun południowy) do  +90  (biegun północny), długość 

geograficzna   może   przyjmować   wartości   od  -180  do  180  (ujemne   na   zachód   od 

Greenwich, dodatnie na wschód). Dla ułatwienia przyjmijmy, że zarówno długość jak i 

szerokość   geograficzna   są   podane   przy   pomocy   dwóch   liczb   całkowitych   (stopnie   i 

minuty). 

      Napisz   program,   który   wczytuje   powyższe   dane   z   klawiatury,   uzupełnia   każdą 

miejscowość jej odległością od Warszawy (dla uproszczenia przyjmijmy, że Warszawa 

jest   na   pierwszym   miejscu   na   liście   miejscowości)   oraz   do   każdej   krawędzi   grafu 

dodaje   również   długość   (koszt)   krawędzi   (odległość   między   miejscowościami).   Tu 

należy wykonać sortowanie listy miast rosnąco względem odległości od Warszawy. Tak 

zmodyfikowane   dane   zapisujemy   na   dysku  D:  w   pliku   tekstowym  MIASTA.   Na   tym 

etapie najważniejszym zadaniem jest napisanie funkcji typu INTEGER, która dla dwóch 

wybranych miast oblicza odległość między nimi w kilometrach.

      Drugie   zadanie   polega   na   opisaniu   słownym   algorytmu,   który   dla   danego   pliku 

MIASTA  wyznaczy drzewo minimalnych połączeń Warszawy z pozostałymi miastami. 

Zaproponuj strukturę danych. 

9) Dana jest lista studentów II roku informatyki. Każdy wiersz listy zawiera nazwisko oraz 

wykaz ocen z 4 przedmiotów egzaminacyjnych (1 ocena jeśli zdane za 1-szym razem, 2 

oceny za 2-gim,  itd.) Dopuszczalne oceny: 2, 3, 3+, 4, 4+, 5. Lista zakończona jest 

wierszem, w którym występuje nazwisko złożone co najwyżej z 1-go znaku.

Posortuj listę na 3 podgrupy studentów:

1. studentów, którzy zdali wszystkie egzaminy w 1-szym terminie,

2. studentów, którzy zdali wszystkie egzaminy ale nie wszystkie w 1-szym terminie,

3. studentów, którzy z 1 przedmiotu otryzmali 3 oceny niedostateczne.

Napisz program,  który wczytuje powyższe dane oraz realizuje dodatkowe zadanie – 

wyprowadzi na urządzenie zewnętrzne 3 listy studentów.

10)Zdjęcia lotnicze. Dana jest powierzchnia P w kształcie prostokąta o wymiarach: A na B. 

Załoga   samolotu   wykonała   serię   zdjęć   lotniczych.   Każde   zdjęcie   obejmuje   fragment 

analizowanego prostokąta i jest również prostokątem o bokach równoległych do boków 

prostokąta P. Zdjęcie takie opisane jest przy pomocy 4 liczb: x

i

, y

i

, a

i

, b

i

, gdzie para (x

i

, y

i

) 

oznacza   współrzędne   lewego   dolnego   rogu   prostokąta,   natomiast   (a

i

,   b

i

)   oznaczają 

wymiary prostokąta. Liczby te spełniają nierówności:

0≤x

i

≤x

i

+a

i

≤A       0≤y

i

≤y

i

+b

i

≤B       i=1, 2, ..., n

Napisz program, który wczyta liczbę n, a następnie informacje o każdym z tych n zdjęć 

oraz obliczy pole obszaru, który został sfotografowany co najmniej raz. Niektóre z tych 

zdjęć przynajmniej częściowo mogą obejmować ten sam obszar, a część prostokąta  P 

nie została sfotografowana.

11)Problem   pasażera   MPK.  Dany   jest   graf   opisujący   sieć   komunikacji   miejskiej. 

Wierzchołki grafu o numerach 1, 2, ..., n, reprezentują przystanki. Krawędzie grafu (p

i

, 

p

j

)   oznaczają   bezpośrednie   przejazdy   z   przystanku  p

i

  do  p

j

.   Sieć   składa   się   z  r 

przystanków komunikacyjnych. Linia komunikacyjna o numerze i opisana jest jako ciąg 

przystanków p

i,j

, i=1, 2, ..., s

i

, przez które przejeżdżają pojazdy danej linii. Oczywiście, 

przyjmujemy,   że   autobus   (trolejbus)   w   drodze   powrotnej   wraca   tą   samą   trasą. 

Pomijamy   tutaj   sprawę   rozkładu   jazdy.   Interesuje   nas,   czy   dla   danych   dwóch 

przystanków  k  oraz  m  istnieje bezpośrednie lub tylko z jedną przesiadką połączenie 

między tymi przystankami.

Zadanie dla Ciebie:

●

Zaprojektuj strukturę danych,

●

Napisz   program,   który   wczyta   opisane   informacje   z   pliku   tekstowego 
c:\mpk\danempk,

●

Napisz   procedurę,   która   dla   danych   dwóch   numerów   przystanków  k  oraz  m 
znajdzie, o ile istnieje, numer linii łączącej te przystanki,

●

Napisz procedurę, która w przypadku braku połączenia bezpośredniego, znajdzie, o 
ile istnieje, połączenie z jedną przesiadką łączące przystanki k i m.

12)Mediana.  Dla   pewnego   zestawu   danych   (rekordów)   brak   definicji   relacji   <   lub  ≤, 

natomiast istnieje metoda, która dla danych 3 elementów stwierdza, który z nich jest 

elementem   środkowym.   Metoda   ta   opisana   jest   w   postaci   funkcji  MED3(a,b,c). 

Wynikiem funkcji jest liczba 1, jeśli elementem środkowym jest a, 2 jeśli b, oraz 3 jeśli 

c.   Korzystając   z   funkcji   MED3   opracuj   algorytm   znajdowania   mediany   (elementu 

środkowego)   w   tablicy  T[1..n],  n  –   nieparzyste,   której   elementami   są   rekordy 

omawianego typu. Oszacuj jeśli to możliwe, złożoność zaproponowanego przez Ciebie 

algorytmu. Jako operację dominującą przyjmij wywołanie funkcji MED3.

13)Zagęszczenie punktów. (Zadanie obowiązkowe). Ustawienie danych: n, x

1

, x

2

, ..., x

n

, a. 

Napisz schemat NS programu, który wczyta powyższe dane i znajdzie przedział na osi 

liczbowej o długości a, który zawiera możliwie najwięcej elementów ciągu {x

i

}.

14)Ciąg   wklęsły.  Ciąg   monotoniczny   {x

i

}  i=1,   2,   ...,   m  nazywamy   wklęsłym,   jeśli   dla 

dowolnych liczb naturalnych i, j, k takich, że 1≤i<j<k≤m spełniony jest warunek

(k-j)x

i

+(j-j)x

k

≤(k-i)x

j

Ustawienie danych: m, x

1

, x

2

, ..., x

m

.

Napisz schemat NS programu, który wczyta powyższe dane i w przypadku, gdy ciąg 

okaże się monotoniczny sprawdzi czy jest to ciąg wklęsły.

15)Liczby   szczęśliwe.  Po   wielomiesięcznych   badaniach   grupa   entuzjastów   internetu 

stwierdziła, że liczby szczęśliwe mają następujące własności:

●

Liczba 0 jest szczęśliwa

●

Jeśli liczba n jest szczęśliwa, to również liczba 2n jest szczęśliwa, a liczba 2n+1 
jest nieszczęśliwa

●

Jeśli liczba n jest nieszczęśliwa, to również liczba 2n jest nieszczęśliwa, a liczba 
2n+1 jest szczęśliwa.

Napisz schemat NS funkcji, której wartością jest liczba 1, jeśli argument funkcji n jest 

liczbą szczęśliwą, a 0 gdy n jest liczbą nieszczęśliwą.

16)  Ustawienie   danych:  n   w[1]   q[1]   w[2]   q[2]   ...   w[n]   q[n],   gdzie  w[i]  oznacza   wagę, 

natomiast q[i] oznacza iloraz inteligencji i-tego studenta. Masz uzasadnić hipotezę: im 

mniejsza   waga   tym   większy   iloraz   inteligencji.   W   tym   celu   napisz   program,   który 

wczyta   powyższe   dane,   a   następnie   znajdzie   najdłuższy   cię   liczb   naturalnych  k[j], 

1≤k[j]≤n, taki, że  w[k[j]]  jest ciągiem ostro rosnącym, a ciąg  q[k[j]]  jest ciągiem ostro 

malejącym. Ustal jaka jest złożoność pesymistyczna zaproponowanego przez Ciebie 

algorytmu.

17)  Ustawienie   danych:  m   w[1]   q[1]   w[2]   q[2]   ...   w[m]   q[m],   gdzie  w[i]  oznacza   wagę, 

natomiast q[i] oznacza iloraz inteligencji i-tego studenta. Masz uzasadnić hipotezę: im 

większa waga tym większy iloraz inteligencji. W tym celu napisz program, który wczyta 

powyższe dane, a następnie znajdzie najdłuższy cię liczb naturalnych  k[j],  1≤k[j]≤m, 

taki, że ciągi  w[k[j]]  oraz  q[k[j]]  są ciągami ostro rosnącymi. Ustal jaka jest złożoność 

pesymistyczna zaproponowanego przez Ciebie algorytmu.

18)  Definicja   typu:   TYPE   wielokat=ARRAY[1..1000,1..2]   OF   REAL;   Napisz   funkcję 

PW(n:INTEGER;   VAR   v:wielokat):REAL;   której   wartością   jest   pole   wielokąta   o   n-

wierzchołkach, podanych w tablicy v.

19)  Definicja   typu:   TYPE   nkat=ARRAY[1..1000,1..2]   OF   REAL;   Napisz   funkcję 

wW(n:INTEGER; VAR v:nkat):BOOLEAN; której wartością jest TRUE, jeśli jest to wielokąt 

wpukły, FALSE w przeciwnym razie. Kolejne wierzchołki wielokąta podane są w tablicy 

v.

20) Dany jest graf nieskierowany, podany jako dolny trójkąt macierzy sąsiedztwa. Napisz 

program  sprawdzający czy jest to graf spójny. Ustawienie danych:  n, G[2,1],  G[3,1], 

G[3,2], G[4,1, ..., G[n,n-1], gdzie G[i,j]=0 lub 1.

21) Dany jest graf nieskierowany, podany jako górny trójkąt macierzy sąsiedztwa. Napisz 

program, który skonstruuje dla tego grafu drzewo rozpinające. Ustawienie danych:  n, 

G[1,2], G[1,3], ..., G[1,n], G[2,3], ..., G[n-1,n], gdzie G[i,j]=0 lub 1.

22) Ustawienie danych: n, a[1], a[2], ... , a[n], k, b[1], b[2], ... , b[k]. Przystanki autobusowe 

zostały ponumerowane liczbami naturalnymi. Linia nr 16 zaczyna kurs od przystanku 

a[1],   a   kończy   na   przystanku   a[n].   Linia   nr   21   zaczyna   kurs   od   przystanku   b[1],   a 

kończy na przystanku b[k]. Napisz program, który wczyta powyższe dane (jak zwykle 

ważna jest kolejność), a następnie ustali ile wspólnych przystanków mają te dwie linie. 

Oszacuj złożoność zaproponowanego algorytmu.

23)  Definicja   typu:   TYPE   tabl=ARRAY[1..1000,1..2]   OF   REAL;   Napisz   funkcję 

PUNKTY(n:INTEGER,VAR   v:tabl):INTEGER:   która   dla   danego   w   tablicy   v   wielokąta 

wypukłego   o   n   wierzchołkach   jako   wynik   daje   liczbę   punktów   o   współrzędnych 

całkowitych znajdujących się w tym wielokącie.

24)  Ustawienie danych: k, p[1], p[2], ... , p[k], m, b[1], b[2], ... , b[m].  Przystanki metra 

zostały   ponumerowane   liczbami   naturalnymi.   Trasa   A   zaczyna   kurs   od   przystanku 

p[1], a kończy na przystanku p[k]. Trasa B zaczyna kurs od przystanku q[1], a kończy 

na przystanku q[m]. Napisz program, który wczyta powyższe dane (jak zwykle ważna 

jest   kolejność),   a   następnie   ustali   ile   wspólnych   przystanków   mają   te   dwie   linie. 

Oszacuj złożoność zaproponowanego algorytmu.

25) 

Definicja   typu:   TYPE   wielokat=ARRAY[1..100,1..2]   OF   REAL; 

punkty=ARRAY[1..5000,1..2]   OF   REAL;   Napisz   funkcję   ZLICZANIE(n:INTEGER;   VAR 

v:wielokat;   VAR   pkt:punkty):INTEGER:   która   dla   danego   w   tablicy   v   wielokąta 

wypukłego o n wierzchołkach jako wynik daje liczbę punktów tablicy pkt, znajdujących 

się wewnątrz wielokąta v.