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.