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