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
1
2
5
5
4
0 6
1 3
2 7
3
4
0
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 AP×2 i wczytaj z pliku ALOK.txt pozostaÅ‚e
dane. WyÅ›wietl na ekranie tablicÄ™ AP×2 .
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 znalez
ć 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]). Przeprowadz
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 i 0 d" 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 aar × ac przez macierz bac × bc . Iloczyn car × bc = aar × ac bac × bc 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