Algorytmy i złożoność
Zadanie 0. UTM - patrz instrukcja.
Zadanie 1.
a. Zrealizuj procedurę będącą implementacją algorytmu Euklidesa w sposób nie wykorzystujący rekurencji.
b. Zrealizuj procedurę podnoszenia liczby całkowitej x do potęgi n (całkowitej, nieujemnej). Rekurencyjnie.
Zadanie 2.
a. Zaimplementować rekurencyjną procedurę fib, która wywołana z
argumentem n typu int zwróci n-ty wyraz ciągu Fibonacciego, w-g
definicji ze slajdu 62 w PDF-ie wykładowym.
b. Doprowadzić rekurencyjną procedurę fib do postaci z rekurencją
krańcową i policzyć fib(50).
c. Przedstawić wersję procedury fib z wykorzystaniem pętli.
d. Wyznaczyć wzór matematyczny lub napisać program komputerowy
określający ilość wywołań procedury fib (n) przy założeniu, że mamy
do czynienia z definicją fib, jak w punkcie a.
Zadanie 3.
a. https://projecteuler.net/problem=1
b. https://projecteuler.net/problem=4
c. https://projecteuler.net/problem=9
Zadanie 4. Wykonaj zadanie ze slajdu 73 w PDF-ie wykładowym, punkty a, b i c.
Zadanie 5. Wykonaj zadanie ze slajdu 84 w PDF-ie wykładowym, punkty a i b.
Zadanie 6. W oparciu o implementację listy jednokierunkowej:
a. Dodaj pole tail oznaczające ostatni element listy i uwzględnij je w algorytmach wstawiających.
b. Dodaj metodę pozwalającą na wstawienie elementu za węzeł wskazany indeksem całkowitym. Metoda powinna zwrócić flagę boolean informującą o tym, czy wstawienie się powiodło, czy nie.