ASD Ćwiczenia 1

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 0

Udowodnij, że algorytm 6174 ma własność stopu.

Podobnie udowodnij to dla wersji tego algorytmu z trzema cyframi z liczbą 495 zamiast 6174.

Rozwiązanie

Zadanie 1

Udowodnij, że algorytm Najdłuższy-Malejący jest poprawny.

Rozwiązanie



Zadanie 2

Udowodnij, że algorytm 2-Pakowanie jest poprawny.

Rozwiązanie

Zadanie 3

Udowodnij poprawność algorytmu na cykliczną równoważność słów.

Rozwiązanie

Zadanie 4

Operacja dominującą w algorytmie na cykliczną równoważność jest porównanie dwóch elementów tablic u,v (czy są równe, jeśli nie to który jest mniejszy). Liczba porównań jest liniowa. Dla jakich ciągów zadanej dlugości długości algorytm na cykliczną równoważność wykonuje maksymalną liczbę porównan symboli?

Rozwiązanie