Algorytm

Problem Wieże Dysków

Na ziemi narysowano niewielkie koło, na jego obwodzie umieszczono trzy drewniane paliki. Na jeden z nich nałożono płaskie drewniane klocki w kształcie dysków z dziurką w środku. Każdy dysk ma inną średnicę, dyski zostały nałożone w kolejności od największego (na spodzie) do najmniejszego (na wierzchu). Dyski można przekładać z palika na palik, ale tylko pojedynczo i nie wolno kłaść większego dysku na mniejszy. Przy tych ograniczeniach należy przełożyć wszystkie dyski na inny palik (którykolwiek).

Rozwiązanie opiszemy na tyle dokładnie, by mógł je wykonać np. przedszkolak nie rozumiejący samego problemu, ani dlaczego metoda działa.

Algorytm 1

usiądź wewnątrz koła,
przenieś najmniejszy dysk o jeden palik w prawo
dopóki wszystkie dyski nie znajdą się na jednym paliku
   przenieś dysk różny od najmniejszego na ten palik, na którym nie ma najmniejszego dysku
   przenieś najmniejszy dysk o jeden palik w prawo

Omówienie sformułowania problemu. Zadania algorytmiczne (informatyczne) często mają strukturę dane-wyniki. Dane to opis obiektów, które podlegają przetwarzania w sposób zadawany przez algorytm, natomiast wyniki to opis tego, co chcielibyśmy osiągnąć wykonawszy algorytm.

Po pierwsze, jest jasne od czego zaczynamy: trzy paliki na obwodzie koła, na jeden z nich nałożono dyski w kolejności od największego do najmniejszego.

Po drugie, wiadomo do czego zmierzamy: dyski w tej samej kolejności, na innym paliku.

By sformułować rozwiązanie musimy również mieć jasność, jakimi operacjami można się posługiwać. W tym przypadku ze sformułowania zadania wynika, że dostępne operacje to (1) porównywanie rozmiarów dysków oraz (2) przekładanie dysku na inny palik (pod warunkiem, że większego nie kładziemy na mniejszy).

Omówienie algorytmu. Posługując się podanym algorytmem rzeczywiście przełożymy dyski na inny palik, niezależnie od liczby dysków do przełożenia. Przykład ten pokazuje, że jeśli sposób postępowania opiszemy wystarczająco precyzyjnie, to osoba rozumiejąca opis wykona zadanie niezależnie od tego, czy wie dlaczego ten sposób jest dobry. Jednak twórca algorytmu powinien być przekonany o poprawności swojego rozwiązania. Powinien umieć odpowiedzieć na szereg pytań. Skąd pewność, że przekładanie dysków się zakończy, a może w pewnych przypadkach można przekładać je w nieskończoność? Skąd wiadomo, że w momencie zakończenia wykonywania algorytmu faktycznie wszystkie dyski będą nałożone na jeden palik? Czy może się zdarzyć, że po zakończeniu "wylądujemy" z dyskami z powrotem na paliku wyjściowym? (To byłby problem, bo dyski mamy umieścić na innym paliku, niż wyjściowy). Po ilu przełożeniach osiągniemy cel i od czego to zależy? Czy i kiedy mamy dowolność w przekładaniu największego wierzchniego dysku (np. na który palik go przełożyć)? Na takie pytania odpowiada algorytmika, dział informatyki zajmujący się analizą i projektowaniem algorytmów.

Opisany algorytm to "instrukcja dla przedszkolaka", by powtarzał ciąg czynności, aż do spełnienia pewnego warunku (znalezienia się wszystkich dysków na innym paliku). Od przedszkolaka wymagamy, by rozróżniał stronę prawą i lewą, potrafił porównać rozmiary dysków oraz przenosić je pojedynczo pomiędzy palikami. To niedużo. Do tego nie potrzeba nawet przedszkolaka, wystarczy maszyna wyposażona w manipulator.

Do przedszkolaka możemy mówić po polsku. Instrukcje dla maszyny trzeba formułować w prostszym, sztucznym języku. Takie instrukcje nazywamy programem. Zapisywanie algorytmów za pomocą ograniczonego zestawu operacji i konstrukcji językowych nazywamy programowaniem, a te operacje i konstrukcje składają się na sztuczny język, tzw. język programowania. Maszyny zdolne do wykonywania programów nazywamy komputerami.

Problem Najlżejszy Odważnik

Trzy odważniki A, B i C wyglądają tak samo, ale każdy ma inną masę (potocznie wagę). Za pomocą małej wagi szalkowej możemy sprawdzać, który z dwóch odważników jest lżejszy. Należy znaleźć najlżejszy odważnik spośród A, B i C.

Omówienie sformułowania problemu. Danymi wejściowymi w tym zadaniu są trzy odważniki, a w zasadzie ich wagi, ponieważ inne właściwości nie są istotne dla rozwiązania. Rozwiązanie algorytmiczne musi być skonstruowane w ten sposób, żeby wyznaczyć odważnik najlżejszy dla dowolnego układu mas odważników wejściowych. W tym zadaniu występuje tylko jedna dopuszczalna operacja: wyznaczenie lżejszego z dwóch odważników.

Algorytm 2

1. Wyznacz lżejszy z odważników A i B.
2. Porównaj wagę odważnika C z wagą lżejszego z odważników A i B; lżejszy odważnik jest najlżejszy spośród odważników A, B i C.

Omówienie Algorytmu 2. Opis algorytmu wydaje się czytelny, jednakże punkt 2. nie jest opisany bardzo precyzyjnie. W szczególności nie jest stuprocentowo jasne, w jaki sposób czynności opisane w punkcie 2. odnoszą się do dopuszczalnych operacji (w zadaniu występuje jedna operacja: wyznaczenie lżejszego z dwóch odważników).

Algorytm 3

   czy A jest lżejszy od B? 
   jeśli tak, to
       czy A jest lżejszy od C? 
       jeśli tak, to
           daj odpowiedź, że najlżejszy jest A
       jeśli nie, to
           daj odpowiedź, że najlżejszy jest C
   jeśli nie, to
       czy B jest lżejszy od C? 
       jeśli tak, to
           daj odpowiedź, że najlżejszy jest B
       jeśli nie, to
           daj odpowiedź, że najlżejszy jest C

Omówienie Algorytmu 3. W celu wyznaczenia najlżejszego odważnika wykonujemy dwa ważenia. Jedno ważenie nie wystarczy - po pierwszym ważeniu zawsze jeden z trzech odważników pozostaje nietknięty, a przecież to właśnie on może okazać się najlżejszy.

Opis rozwiązania opiera się na instrukcjach nakazujących wykonanie jednej lub drugiej czynności w zależności od spełnienia pewnego warunku. Są to tzw. instrukcje warunkowe. W opisie występują trzy instrukcje warunkowe, każda zaczynająca się pytaniem (warunkiem do sprawdzenia) postaci czy "X jest lżejszy od Y?". Podczas realizacji algorytmu zawsze wykonane zostaną tylko dwie z nich (nie możemy jednak z góry przewidzieć które, to zależy od danych wejściowych).

Instrukcja nakazująca wykonanie czynności w zależności od spełnienia warunku, tzw. instrukcja warunkowa, jest podstawową konstrukcją w wielu językach programowania.

Porządkowanie

Algorytm drugi wykonuje zawsze dwa ważenia w celu znalezienia najlżejszego odważnika. Wykonując jedno dodatkowe ważenie jesteśmy w stanie nie tylko wskazać najlżejszy odważnik, ale równie uszeregować wszystkie odważniki względem ich wag. W poniższym opisie skróciliśmy też zapis porównywania wag pisząc np. "czy A < B?", zamiast "czy A jest lżejszy od B?".

Algorytm 4

   czy A < B? 
   jeśli tak, to
       czy A < C?
       jeśli tak, to
           czy B < C?
           jeśli tak, to
               daj odpowiedź A,B,C
           jeśli nie, to
               daj odpowiedź A,C,B
       jeśli nie, to
           daj odpowiedź C,A,B
   jeśli nie, to
       czy B < C?
       jeśli tak, to
           czy A < C?
           jeśli tak, to
               daj odpowiedź B,A,C
           jeśli nie, to
               daj odpowiedź B,C,A
       jeśli nie, to
           daj odpowiedź C,B,A

Ten algorytm wykonuje czasem dwa, a czasem trzy ważenia, w zależności od danych wejściowych. Przy analizie algorytmów zazwyczaj patrzymy na przypadek najgorszy (pesymistyczny) - powyższy algorytm w przypadku pesymistycznym wymaga trzech ważeń.

Reprezentacja danych wejściowych

Czasami kłopoty ze sformułowaniem algorytmu wynikają z niedoprecyzowania postaci danych wejściowych. W powyższych zadaniach staraliśmy się unikać tego błędu.

Oto przykład sformułowania zadania, w którym pojawia się niejasność.

Problem Punkt i Prostokąt (wersja nieprecyzyjna)

Dany jest punkt oraz prostokąt o bokach równoległych do osi układu współrzędnych. Należy stwierdzić, jakie jest położenie punktu względem prostokąta (tzn. czy punkt znajduje się wewnątrz prostokąta, czy poza prostokątem).

Nie jest jasne, w jaki sposób punkt i prostokąt są zadane. Czy są np. narysowane na kartce? W jaki sposób wprowadzić zawartość kartki do maszyny? Zeskanować? Jak stwierdzić, że punkt leży wewnątrz prostokąta? Jeżeli zaczniemy się przyglądać punktowi narysowanemu bardzo blisko brzegu, za pomocą mikroskopu odkryjemy, że to nie żaden punkt, tylko olbrzymie nieregularne rozlewiska tuszu na górzystej przestrzeni papieru.

Francuski uczony René Descartes (znany jako Kartezjusz) zaproponował metodę opisu obiektów geometrycznych za pomocą ciągów liczb. Na przykład, wprowadzając prostokątny układ współrzędnych, punkt opisać można za pomocą dwóch liczb, a trójkąt za pomocą trzech punktów (czyli sześciu liczb). Dzisiaj wszyscy uczymy się tej metody w szkole.

Załóżmy, że autorowi zadania chodziło o to, że prostokąt i punkt są zadane właśnie za pomocą współrzędnych kartezjańskich. Na to wskazywałoby sformułowanie "osie układu współrzędnych" pojawiające się w treści zadania.

Wciąż jednak nie jest jasne, jaki wariant opisu danych autor zadania miał na myśli. Punkt zapewne miał być dany w postaci pary współrzędnych. Większe wątpliwości dotyczą opisu prostokąta. Dla przykładu, prostokąt może być zadany jako:

• cztery wierzchołki w dowolnej kolejności,
• dwa przeciwległe wierzchołki w dowolnej kolejności,
• dolny lewy wierzchołek, długość boku równoległego do osi X, długość boku równoległego do osi Y.

Przyjmijmy, że chodziło o tę ostatnią możliwość. Precyzyjne sformułowanie zadania wygląda wówczas tak.

Problem Punkt i Prostokąt (wersja precyzyjna)

Dane są punkt A = (Ax,Ay) oraz prostokąt o lewym dolnym rogu w punkcie P = (Px,Py), którego jeden bok o długości dx jest równoległy do osi X, a drugi bok ma długość dy. Liczby Ax,Ay,Px,Py,dx,dy są liczbami rzeczywistymi. Należy odpowiedzieć TAK, jeżeli punkt A znajduje się na prostokącie (tzn. w jego wnętrzu lub na brzegu) lub NIE, jeżeli punkt A znajduje się poza prostokątem.

Taki precyzyjny opis danych i wyników nazywamy specyfikacją zadania algorytmicznego.

Jeżeli algorytm dla każdych danych zgodnych ze specyfikacją zawsze podaje wynik zgodny z tą specyfikacją, to mówimy, że jest całkowicie poprawny względem specyfikacji.

Żeby móc zacząć myśleć o algorytmie musimy jeszcze wiedzieć jakimi operacjami możemy się posługiwać w jego opisie. W przypadku zadania o prostokącie operacjami dozwolonymi są operacje arytmetyczne na liczbach rzeczywistych i porównywanie liczb.

Oto algorytm zgodny z doprecyzowaną specyfikacją zadania Punkt i Prostokąt.

Algorytm 5

   czy Px <= Ax i Ax <= Px + dx i Py <= Ay i Ay <= Py + dy?
     jeśli tak, to odpowiedzią jest TAK
     jeśli nie, to odpowiedzią jest NIE

ZADANIA

Zadanie 1

Spróbuj skompletować rekwizyty do zadania o wieżach dysków. Wykonaj opisany algorytm dla 2, 3, 4 i 5 dysków. Policz, ile ruchów wykonasz w każdym z przypadków. Zaproponuj algorytm przemieszczania dysków przy dodatkowym żądaniu, że wszystkie dyski muszą się znaleźć na sąsiednim paliku z prawej strony.

Zadanie 2

Zapisz algorytm, który za pomocą wagi szalkowej porządkuje względem mas cztery odważniki za pomocą nie więcej niż pięciu ważeń. Sprawdź, czy Twój opis algorytmu jest na tyle precyzyjny, że koleżanki i koledzy są w stanie wykonać go bez zastanowienia.

Zadanie 3

Jeżeli poprosisz kogoś o wykonanie Twojego algorytmu z zadania 2, to samemu możesz zagrać rolę wagi. Możesz na początku zabawy ustalić potajemnie wagi odważników, a potem udzielać odpowiedzi na pytania partnera. Zauważ jednak, że o ile nie podasz sprzecznych odpowiedzi, możesz "oszukiwać", podając odpowiedzi wymuszające jak największą liczbę ważeń. Na przykład przy wykonaniu algorytmu 4, jeżeli na pytanie "czy A < B?" odpowiesz "TAK", to na pytanie "czy A < C" lepiej też odpowiedzieć "TAK", bo to zmusi partnera do zadania jeszcze jednego pytania (wykonania jeszcze jednego ważenia). Zastanów się, w jaki sposób udzielać takich złośliwych odpowiedzi podczas wykonania algorytmu z zadania 2. Czy zawsze da się wymusić pięć ważeń? Czy jeżeli na pierwsze kilka pytań odpowiemy zgodnie z autentycznymi ustalonymi na wstępie wagami odważników, to "oszustwo" w kilku ostatnich pytaniach wystarczy do wymuszenia pięciu ważeń? W ilu końcowych pytaniach trzeba "oszukać", by zawsze dało się wymusić pięć ważeń?

Zadanie 4*

Spróbuj znaleźć sposób uporządkowania pięciu odważników względem mas w maksymalnie siedmiu ważeniach. Uwaga! Nie chodzi tutaj o zapisanie algorytmu tak, jak w np. w 2 (autor spróbował, to zajęło 477 linii), tylko o opisanie mechanizmu wykonywania kolejnych ważeń, który pozwoli posortować 5 odważników.

Zadanie 5 (Fałszywa Moneta)

Mamy dziewięć monet, a jedna z nich jest fałszywa. Wszystkie monety wyglądają tak samo i tyle samo ważą, oprócz fałszywej, która jest lżejsza lub cięższa od pozostałych. Za pomocą małej wagi szalkowej możemy porównywać wagi monet. Na każdej szalce można położyć wiele monet; ważenie może dać jeden z trzech rezultatów: lewa szalka przeważa, szalki są w równowadze, prawa szalka przeważa. Zaproponuj algorytm znajdowania fałszywej monety wykonujący nie więcej niż trzy ważenia.

Zadanie 6*

Posłuż się rozwiązaniem zadania 5 do opracowania algorytmu znajdującego fałszywą monetę spośród dwunastu monet w trzech ważeniach.

Zadanie 7 (Kulki w Pudełkach)

Pewną liczbę pudełek (oznaczmy ją przez N) ustawiono w rzędzie i ponumerowano kolejnymi liczbami naturalnymi od 0 do N − 1. W każdym z pudełek o numerach od 0 do N − 2 umieszczono 1 kulkę, pudełko o numerze N − 1 jest puste. Na każdej kulce napisano jedną z liczb 0,1, ..., N-2 -- na każdej kulce inną liczbę. W jednym ruchu można przełożyć jedną kulkę do pudełka, które jest aktualnie puste. Należy poprzekładać kulki w ten sposób, by na koniec znalazły się w pierwszych N-1 pudełkach, ale tak, żeby liczby na kulkach w kolejnych pudełkach rosły. Opracuj algorytm przekładania kulek w celu ich rozmieszczenia w zadanej kolejności.

Zadanie 8

Czy w rozwiązaniu zadania 7 da się skonstruować algorytm, który nie przekłada żadnej kulki więcej niż dwa razy?

Zadanie 9

Z pełnej talii kart bez dżokerów wyjęto pewną liczbę kart i ułożono na stole. Karty leżą w jednym rzędzie, zakryte. Wiadomo, że wszystkie karty czerwone (kara i kiery) znajdują się przed kartami czarnymi (trefle i piki). Zaproponuj algorytm który policzy, ile czerwonych kart leży na stole, odkrywając możliwie mało kart.

Zadanie 10

W doprecyzowanym opisie zadania Punkt i Prostokąt przyjęto, że prostokąt jest zadany przez wierzchołek i długości boków (wariant trzeci). Sformułuj algorytm rozwiązujący to samo zadania dla innych wariantów reprezentacji prostokąta.

Zadanie 11

Podaj dokładną specyfikację następującego zadania i opisz algorytm zgodny z tą specyfikacją. W prostokątnym układzie współrzędnych dane są dwa prostokąty o bokach równoległych do osi układu. Wyznacz część wspólną tych prostokątów.