Informatyka - Podstawy Programowania w Języku C++ 

prow. Sławomir Czarnecki 

 

Zadania na laboratorium nr. 7 

 
1.  Utwórz  plik  tekstowy  ALOK.txt  i  na  podstawie  zaproponowanej  na  poniŜszym  rysunku 
numeracji węzłów oraz prętów kratownicy, zapisz do niego kolejno: liczbę prętów (równą 8) 
a następnie wszystkie składowe macierzy alokacji (patrz z4 na Lab 6): 
 

8 
4 5 
0 5 

  

 

 

 

 

 

 ... 
0 3 

 

0

1

2

3

4

5

0

1

2

3

4

7

5

6

 

 

Rys.1.  Numeracja węzłów i prętów statycznie wyznaczalnej kratownicy płaskiej. 

 
Zdefiniuj  strumień  odczytu  danych  z  pliku  ALOK.txt  i  wczytaj  z  niego  liczbę  prętów  P,  a 
następnie zdefiniuj dynamicznie macierz alokacji 

2

P×

A

 i wczytaj z pliku ALOK.txt pozostałe 

dane. Wyświetl na ekranie tablicę 

2

P×

A

. 

 
2.  Sortowanie  tablicy  a[dim]  przez  wstawianie  (por.  np.  [1]).  Algorytm  jest  analogiczny  do 
czynności porządkowania talii kart. Zaczynamy od „pustej” lewej ręki, po czym bierzemy ze 
stołu kolejne karty i wstawiamy je we właściwe miejsca w posortowanej juŜ części talii kart 
trzymanej  w  lewej  ręce.  Aby  znaleźć  właściwe  miejsce  dla  danej  karty  trzymanej  w  prawej 
ręce, porównujemy ją (od strony prawej do lewej) z posortowanymi juŜ kartami, które mamy 
w lewej ręce. Przykład: 
lewa ręka 

stół z nieposortowanymi kartami 

 

5 2 4 6 1 3 

 talia na stole do posortowania 

 

5

 

 

2 4 6 1 3 

 bierzemy pierwszą kartę 

5

 ze stołu do lewej ręki 

 
5 

2

 

 

4 6 1 3  

 bierzemy drugą kartę 

2

 ze stołu do lewej ręki 

2 

5 

 

4 6 1 3  

 szukamy dla karty 

2

 właściwego miejsca w lewej ręce 

 
2 5 

4

   

6 1 3   

 bierzemy trzecią kartę 

4

 ze stołu do lewej ręki  

2 

4 

5   

6 1 3   

 szukamy dla karty 

4

 właściwego miejsca w lewej ręce 

2 4 5 

6

  

1 3 

 

 bierzemy czwartą kartę 

6

 ze stołu do lewej ręki 

 
2 4 5 6 

1

 

3 

 

 bierzemy piątą kartę 

1

 ze stołu do lewej ręki 

2 4 5 

1 

6 

3 

 

 szukamy dla karty 

1

 właściwego miejsca w lewej ręce 

2 4 

1 

5 6 

3 

 

 szukamy dla karty 

1

 właściwego miejsca w lewej ręce 

2 

1 

4 5 6 

3 

 

 szukamy dla karty 

1

 właściwego miejsca w lewej ręce 

1 

2 4 5 6 

3 

 

 szukamy dla karty 

1

 właściwego miejsca w lewej ręce  

 
1 2 4 5 6 

3

 

 

 

 bierzemy szóstą kartę 

3

 ze stołu do lewej ręki 

1 2 4 5 

3 

6 

 

 

 szukamy dla karty 

3

 właściwego miejsca w lewej ręce 

1 2 4 

3 

5 6 

 

 

 szukamy dla karty 

3

 właściwego miejsca w lewej ręce 

1 2 

3 

4 5 6 

 

 

 szukamy dla karty 

3

 właściwego miejsca w lewej ręce 

 

Uwaga  !  Elementy  tablicy  mogą  być  sortowane  w  miejscu,  tzn.  nie  jest  konieczne 
definiowanie  Ŝadnej  innej  dodatkowej  tablicy  pomocniczej  i  wszystkie  operacje  moŜna 
przeprowadzać na elementach sortowanej tablicy.

  

 
3. Porównanie dwóch algorytmów sortowania: insert_sort(...) oraz quick_sort(...). Zgodnie ze 
wskazówkami  prowadzącego  zajęcia,  dołącz  do  projektu  plik  nagłówkowy  sorting.h  z 
deklaracjami  kilku  funkcji  (m.in.  sortowania  tablic)  oraz  plik  sorting.cpp  z  definicjami  tych 
funkcji  (na  zajęciach  omówiony  będzie  sposób  dołaczania  do  projektu  własnych  bibliotek 
funkcji). Utwórz dość duŜą tablicę v typu 

double

 (np. v[100000]) inicjalizując ją dowolnymi 

liczbami  losowymi  (na  przykład  z  przedziału  [–1000.0,1000.0]).  Przeprowadź  dla  tablicy  v 
test  szybkości  działania  algorytmu  sortowania  insert_sort(...)  z  zadania  2  i  algorytmu 
sortowania quick_sort(...) zaimplementowanego w pliku sorting.cpp. 
 
Zaimplementuj algorytm poszukiwania binarnego w posortowanej tablicy a[dim] jako funkcję 

int

  binary_search(

double

*  a, 

double

  x, 

int

  dim).  Funkcja  binary_search(...)  ma  zwracać 

najmniejszy  indeks 

(

)

0

i

i

dim

≤ <

,  dla  którego 

[ ]

x

a i

=

  lub  –1,  jeśli  nie  istnieje  składowa 

wektora  a  równa  x.  Idea  (dobrze  znanego  i  bardzo  prostego)  algorytmu  poszukiwania 
binarnego przedstawiona będzie w czasie zajęć. 
 
4. Zdefiniuj funkcję  
 

void

 product(

double

** a, 

double

** b, 

double

** c, 

int

 ar, 

int

 ac, 

int

 bc) 

 
mnoŜenia  macierzy 

ar

ac

×

a

  przez  macierz 

ac bc

×

b

.  Iloczyn 

ar

bc

ar

ac

ac bc

×

×

×

=

c

a

b

  tych  macierzy 

„zwracany”  ma  być  jako  trzeci  parametr  funkcji  product(...).  Przetestuj  działanie  funkcji 
product(...). 
 
  
 
Literatura 
 
[1] Cormen T., Leiserson C., Rivest R., Wprowadzenie do algorytmów, Wyd. Naukowo-
Techniczne, Warszawa 1997