Podstawy programowania v2 (2008) - Laboratorium 1

LISTA 4. METODY ITERACYJNE i REKURENCYJNE

1. Obliczenia matematyczne

Program 1.1 Napisz program z użyciem funkcji, który zliczy n! metodą iteracyjną i rekurencyjną. Porównaj otrzymane wyniki z wynikami z kalkulatora.

Program 1.2 Napisz funkcję zwracającą NWD (największy wspólny dzielnik) dwóch liczb całkowitych dodatnich.

Napisz rekurencyjną wersję algorytmu Euklidesa wyznaczania NWD.

Program 1.3 Napisz funkcję wyświetlającą liczbę całkowitą w formacie binarnym. Uwaga, cyfry powinny być

wyświetlone we właściwej kolejności. Rozwiąż to zadanie rekurencyjnie i iteracyjnie.

Program 1.4 Proszę napisać funkcję zwracającą n-ty element ciągu Fibonacciego.

Program 1.5 Przerób program 1.5 - funkcję wyznaczającą elementy ciągu Fibonacciego na wersję rekurencyjną.

Sprawdź, ile razy ta funkcja zostanie uruchomiona dla wywołania fnFibo(5).

Wskazówka: można użyć zmiennej globalnej, której wartość zwiększana będzie o 1 po każdym wejściu do funkcji fnFibo().

2. Sortowanie tablic z użyciem wybranych algorytmów

Program 2.1 Napisz program sortujący tablicę liczb całkowitych metodami iteracyjnymi:

-

bąbelkową (bubble sort),

-

przez wstawianie (insertion sort),

-

przez wybieranie (selection sort).

Stwórz pętlę główną programu oraz funkcję z menu wyboru metody sortowania. Sortuj kopię tablicy wejściowej, aby można było wielokrotnie używać tych samych wartości do sortowania wielu elementów. Zliczaj operacje porównywania elementów i zamiany miejscami. Wynik sortowania oraz liczniki wyświetlaj na ekranie.

Program 2.2 Rozbuduj program 2.1 sortujący tablicę liczb całkowitych o metody rekurencyjne:

-

szybkie (quicksort),

-

stogowe (heapsort),

-

przez scalanie (mergesort).