lista 6 (2)

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


Wyszukiwarka

Podobne podstrony:
20855 lista 7 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopn
lista ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopnia 
lista 6 (2) ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopnia
lista 9 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopni
72036 lista 6 (2) ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarn
lista ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopnia 
lista 8 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopni
lista2 (2) ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I sto
lista10a ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopn
lista5 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopnia
19272 lista2 (2) ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne
lista11iq6 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I sto
lista10b ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopn
lista11iq6 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I sto
lista 2 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia INFORMATYKA II rok, studia stacjonarne I stopnia ro
Lista 7 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia INFORMATYKA II rok, studia stacjonarne I stopnia ro
lista 9 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia INFORMATYKA II rok, studia stacjonarne I stopnia ro

więcej podobnych podstron