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:
lista 6 (2) ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I st20855 lista 7 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopnlista 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 stopni72036 lista 6 (2) ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarnlista 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 stopnilista2 (2) ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stolista10a ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopnlista5 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopnia19272 lista2 (2) ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarnelista11iq6 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stolista10b ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopnlista11iq6 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stolista 2 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia INFORMATYKA II rok, studia stacjonarne I stopnia roLista 7 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia INFORMATYKA II rok, studia stacjonarne I stopnia rolista 9 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia INFORMATYKA II rok, studia stacjonarne I stopnia rowięcej podobnych podstron