Lab_08_problem.pdf

(70 KB) Pobierz

Metodyka i Techniki Programowania II

Problem -> Algorytm -> Program

dr inż. Jerzy Domżał, dr inż. Janusz Gozdecki

na podstawie instr. dr inż. Krzysztofa Juszkiewicza

2011-04-12

08

UWAGI DO ZADAŃ



Proszę pamiętać o odpowiednim formatowaniu kodu i stosowaniu komentarzy

Wszystkie programy proszę zapisywać w katalogu lab8



Ćwiczenie 1 – usuwanie skoku bezwarunkowego

Przepisz program c2_6p.c tak, by nie było w nim skoku bezwarunkowego goto . W tym celu użyj

pętli. Wszystkie następne programy nie mogą używać instrukcji goto .

Ćwiczenie 2 – największy wspólny dzielnik

Przepisz plik c2_3p.c tak, by procedura obliczania rozkładu na czynniki pierwsze znalazła się w

osobnej funkcji. Następnie:

1. Napisz kod do znajdowania NWD (największego wspólnego dzielnika) metodą szkolną, t.j.:

a. Dla dwóch podanych liczb, znajdź ich czynniki pierwsze

b. Ze zbioru czynników, wybierz powtarzające się w obu rozkładach

c. Ich iloczyn to NWD

2. Zastosuj iteracyjny algorytm Euklidesa z dzieleniem modulo:

a. Wczytaj dwie liczby

b. Oblicz resztę z dzielenia liczby większej przez mniejszą

c. Otrzymaną resztę potraktuj jako liczbę mniejszą, a dotychczasową liczbę mniejszą –

jako większą

d. Powtarzaj kroki 2 i 3 do czasu uzyskania reszty równej zero.

e. Końcowa liczba mniejsza to NWD

3. Zastosuj iteracyjny algorytm Euklidesa bez dzielenia modulo wg poniższego schematu:

4. Napisz rekurencyjny algorytm Euklidesa. Napisz funkcję o nazwie GCD (Greatest Common

Divisor), dwuargumentową, która zwraca pierwszą liczbę, jeśli druga jest zero. W

przeciwnym przypadku zwraca wynik wywołania funkcji GCD, biorąc drugi argument jako

pierwszy, a jako drugi – resztę z dzielenia modulo pierwszego przez drugi.

803583947.051.png

803583947.062.png

803583947.072.png

803583947.078.png

803583947.001.png

803583947.002.png

803583947.003.png

803583947.004.png

803583947.005.png

803583947.006.png

803583947.007.png

803583947.008.png

803583947.009.png

803583947.010.png

803583947.011.png

803583947.012.png

803583947.013.png

803583947.014.png

803583947.015.png

803583947.016.png

803583947.017.png

803583947.018.png

803583947.019.png

803583947.020.png

803583947.021.png

803583947.022.png

803583947.023.png

803583947.024.png

803583947.025.png

803583947.026.png

803583947.027.png

803583947.028.png

803583947.029.png

803583947.030.png

803583947.031.png

803583947.032.png

803583947.033.png

803583947.034.png

803583947.035.png

803583947.036.png

803583947.037.png

803583947.038.png

803583947.039.png

803583947.040.png

803583947.041.png

803583947.042.png

803583947.043.png

803583947.044.png

803583947.045.png

803583947.046.png

803583947.047.png

803583947.048.png

803583947.049.png

803583947.050.png

803583947.052.png

803583947.053.png

803583947.054.png

803583947.055.png

803583947.056.png

803583947.057.png

803583947.058.png

803583947.059.png

803583947.060.png

803583947.061.png

803583947.063.png

803583947.064.png

803583947.065.png

803583947.066.png

803583947.067.png

803583947.068.png

Ćwiczenie 3 – podnoszenie do potęgi

1. Napisz program, który dla podanych dwóch liczb naturalnych, podstawy i wykładnika,

obliczy w pętli wynik potęgowania.

2. Zwróć uwagę, że do obliczenia czwartej potęgi wystarczą dwa mnożenia – dwukrotne

podniesienie do kwadratu. Przepisz tak funkcję z poprzedniego punktu, aby wykonywała

znacząco mniej mnożeń. Spróbuj wykorzystać funkcję log z biblioteki math.h . Utwórz

trzecią funkcję, wykorzystującą wywołanie funkcji pow z biblioteki math.h .

3. Porównaj szybkość działania trzech funkcji potęgujących, uruchamiając je po kolei wiele

razy i analizując czas ich wykonania za pomocą programu gprof .

Ćwiczenie 4 – ciąg Fibonacciego

Ciąg Fibonacciego zbudowany jest w następujący sposób:

a. Pierwszy i drugi element ciągu jest równy 1

b. Każdy kolejny element jest sumą dwóch poprzednich wyrazów

1. Zastosuj algorytm iteracyjny (znajdowanie elementów po kolei) do znalezienia elementu

ciągu o zadanych numerze.

2. Napisz funkcję, która uruchamia siebie rekurencyjnie dla znalezienia elementu ciągu o

zadanym numerze.

3. Wiedząc, że prawdziwe jest twierdzenie o potęgowaniu macierzy:

n

1

1

F

F









n



1

n











1

0

F

F

n

n



1

Napisz funkcję, która znajduje dany element ciągu Fibonacciego z użyciem metody

szybkiego potęgowania (ćw. 3.2)

Program gprof

Program gprof (alternatywnie prof) służy do porównywania szybkości wykonywania

poszczególnych części programu ujętych w funkcje. Programista, chcący efektywnie korzystać z

tego programu powinien zatem stworzyć kod o odpowiedniej strukturze. W szczególności

porównywane funkcje powinny dostać przygotowane dane, a zadaniem tych funkcji powinno być

jedynie odpowiednie ich przetworzenie, bez wyświetlania. Warunkiem korzystania z programu

gprof jest odpowiednie skompilowanie testowanego programu wynikowego. Po uruchomieniu tego

ostatniego i zakończeniu działania na dysku utworzony zostanie binarny plik o nazwie gmon.out ,

zawierający informacje dla programu profilującego.

Przykład użycia gprof

1. Upewnij się, że program c2_6p został skompilowany z następującymi opcjami:

cc –pg –g3 c2_6p.c -o c2_6p

2. Uruchom program:

./c2_6p

3. Uruchom program profilujący dla analizowanego programu:

gprof c2_6p

4. Uruchom program prezentując wersję skróconą:

gprof –b c2_6p

803583947.069.png

803583947.070.png

803583947.071.png

803583947.073.png

803583947.074.png

803583947.075.png

803583947.076.png

803583947.077.png

Plik z chomika:

Inne pliki z tego folderu:

c2_3p.c (1 KB)
c2_6p2.exe (16 KB)
c2_6p3.exe (15 KB)
cw1.c (2 KB)
cw2_1.c (2 KB)

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin