72036 lista 6 (2)

ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopnia rok akad. 2007/2008 semestr zimowy

Ćwiczenie 6 Złożoność algorytmów

1. Oszacować złożoność czasową algorytmów normalizujących ciąg :

a)

1.    wyznacz w zmiennej max największą z wartości ciągu a(i);

2.    dla i od 1 do n wykonaj:

2.1.    a(i) = a(i) * 100 / max

b)

1.    wyznacz w zmiennej max największą z wartości ciągu a(i);

2.    iloraz= 100 / max ;

3.    dla i od 1 do n wykonaj:

3.1.    a(i) = a(i) * iloraz

2.    Podać algorytm wyszukiwania sekwencyjnego liczby S w nieuporządkowanym ciągu A[i] gdzie i=l,..., n oraz oszacować jego złożoność czasową:

a)    algorytm bez wartownika,

b)    algorytm z wartownikiem.

3.    Podać algorytm wyszukiwania binarnego liczby S w uporządkowanym ciągu A[i] gdzie i=l,..., n. Oszacować złożoność algorytmu.

a)    algorytm nierekurencyjny

b)    algorytm rekurencyjny

4.    Podać algorytm rekurencyjny dla problemu Wieże Hanoi. Oszacować jego złożoność czasową.

5.    Sprawdzić, czy w ciągu liczbowym A występuje podciąg B. Oszacować złożoność czasową algorytmu.

6.    Wypisać wszystkie permutacje danego ciągu n znaków. Np. dla ciągu ABC permutacjami są: ABC, ACB, BAC, BCA, CAB, CBA

7*. Podać algorytm rekurencyjny dla problemu skoczka szachowego: dana jest szachownica o nxn polach. Skoczek stoi na polu (0,0) i może poruszać się zgodnie z regułą gry w szachy. Znaleźć drogę dla skoczka aby przeszedł wszystkie pola szachownicy i każde odwiedził dokładnie jeden raz.

2007-11-06