Sysło M. - Piramidy szyszki i inne konstrukcje algorytmiczne (1).pdf

Spis treści Wstęp ............................................................................................................................... 5 Oznaczenia i wyróżnienia w tekście ............................................................................ 8 1. Dodaj do smaku szczyptę soli — czy przepisy kulinarne są algorytmami? . . . 9 2. Jak budowano piramidy ........................................................................................... 15 3. Zabawy towarzyskie.................................................................................................... 21 3.1. Kto jest idolem? ................................................................................................. 21 3.2. Wybory lid e r a ....................................................................................................... 24 4. Sprawność rosyjskich chłopów w mnożeniu — jak można upraszczać sobie życie ...................................................................... 30 5. Rekurencja — jak korzystać z tego, cojuż znamy lub jak „zrzucić robotę’'na kom puter...................................................................... 34 6. Liczby Fibonacciego— jak być doskonałym .......................................................... 41 6.1. Wprowadzenie liczb Fibonacciego ................................................................... 41 6.2. Występowanie liczb Fibonacciego w naturze ................................................. 42 6.3. Doskonałe wymiary — złoty podział i próby wyjaśnienia fenomenu liczb Fibonacciego ............................................................................ 46 6.4. Znajdowanie liczb Fibonacciego ...................................................................... 52 7. Napełnianie naczyń za pomocą algorytmu E uklidesa........................................... 57 7.1. Największy wspólny dzielnik i algorytm n aiw n y.............................................. 58 7.2. Algorytm Euklidesa ........................................................................................... 60 7.3. Przelewanie w o d y ................................................................................................. 63 8. Liczby pierwsze i liczby złożone ............................................................................... 67 8.1. Badanie, czy liczba jest pierwsza ...................................................................... 69 8.2. Generowanie liczb pierwszych ......................................................................... 71 8.3. Wzory na liczby pierwsze .................................................................................. 74 8.4. W pogoni za największą liczbą pierwszą .......................................................... 78 9. Arytmetyka zegarowa — o pożytkach z r e s z t.......................................................... 80 9.1. Arytmetyka modularna — szybkie działania na dużych liczbach ............... 80 9.2. Jak Chińczycy radzili sobie ze sprawdzaniem frekwencji w oddziałach wojskowych .................................................................................. 84 3

10. Przeszukiwanie zbiorów uporządkowanych i nieuporządkowanych — o korzyściach z dbania o porządek ................................................................... 92 10.1. Gra w odgadywanie liczb y ............................................................................... 93 10.2. Poszukiwania w książce telefonicznej .......................................................... 95 10.3. W poszukiwaniu książek.................................................................................. 96 10.4. Programy wspomagające ............................................................................... 98 10.5. Zadania i pytania ogólne — podsumowanie................................................. 99 11. Znajdowanie trwałych związków — par tanecznych, małżeństw ..................... 101 11.1. Gra dla całej klasy ........................................................................................... 102 11.2. Określenie trwałości p a r .................................................................................. 103 11.3. Algorytm znajdowania układu trwałych p a r ................................................. 105 11.4. Uogólnienia i modyfikacje ............................................................................ 107 11.5. Realizacja algorytmu znajdowania trwałego doboru w p a r y ..................... 109 12. Czy zawsze zyskujemy na zachłanności? ............................................................ 111 12.1. Najmniej drobnych w kieszeniach ............................................................... 113 12.2. Powrót do labiryntu — i opuszczenie go metodą rozszerzania ............... 116 13. Niewysokie drzewa — szybkie automaty i krótkie kody .................................... 121 13.1. Szybko działające automaty na monety ....................................................... 122 13.2. Skompresowane kody liter ............................................................................ 129 13.3. Najszybsze scalanie wielu ciągów ................................................................... 132 14. Poszukiwanie z nawrotami ..................................................................................... 134 14.1. Rozmieszczanie królowych na szachownicy ................................................ 135 14.2. Powrót do labiryntu — i wyjście z niego metodą zgłębiania ..................... 142 15. Programowanie dynamiczne .................................................................................. 146 Lista problemów, algorytmów oraz ich realizacji wjęzyku Pascal ........................ 155 Dodatek. Wybrane programy wjęzyku Pascal .......................................................... 158 Skorowidz pojęć ............................................................................................................. 165

Wstęp Wykształcenie jest tym, co pozostaje, gdy zapomni się to, czego uczyliśmy się. [Burrhus F. Skinner — psycholog amerykański} Książka ta ma swoje korzenie we wcześniejszej książce Algorytmy*. Zaczęła ona powstawać, gdy autor przejął się znaczeniem słów B. F. Skinnera z motta za­ mieszczonego powyżej i zastanawiał się, jaki wkład może wnieść do wykształce­ nia zajmowanie się tworzeniem algorytmów. Jak każdemu nauczycielowi, auto­ rowi zależy na tym, aby był to istotny wkład, opierający się działaniu czasu i przynoszący korzyści w życiu. Z tych względów, rozważane w niniejszej książce sytuacje problemowe są wzięte z bliskiego otoczenia, a proponowane postępo­ wanie, prowadzące do ich rozwiązania, ma wiele cech naturalnych działań człowieka. Obydwie książki — Algorytmy oraz Piramidy, szyszki i inne konstrukcje algoryt­ miczne — są w dużym stopniu niezależne od siebie i mogą być wykorzystywane osobno. Jednak każda z nich zyska na wartości, gdy towarzyszyć jej będzie dru­ ga. Pierwsza zawiera wyprowadzenie i opis podstawowych algorytmów i technik algorytmicznych, z wykorzystaniem przykładowych sytuacji problemowych. W drugiej zaś, główny nacisk jest położony na analizę rzeczywistych sytuacji problemowych, której wynikiem jest opis postępowania algorytmicznego, pro­ wadzącego do otrzymania rozwiązania oraz ścisłego opisu algorytmu. Mówi się często, że człowiek dotąd nie zrozumie czegoś, zanim nie nauczy tego — kogoś innego. W rzeczywistości, człowiek nie zrozumie czegoś naprawdę, zanim nie zdoła nauczyć tego — komputera. [Donald E. Knuth — informatyk amerykański] *M. M. Sysło Algorytmy WSiP, Warszawa 1997 zob. również stronę http://www.wsip.com.pl 5

Powyższe słowa, wypowiedziane przez jednego z najwybitniejszych informa­ tyków naszych czasów, dobrze ujmują rolę algorytmów w dobie komputerów. Algorytm bowiem jest rozumiany dzisiaj najczęściej jako opis czynności, które mają być wykonane przez komputer. W książce tej pokazujemy także, jak pro­ gramować rozwiązania, czyli zapisywać je w postaci zrozumiałej dla kompu­ terów. Przez programowanie rozumiemy tutaj uczenie komputera, jak ma roz­ wiązać konkretną sytuację problemową. Rola, jaką ono odgrywa, została traf­ nie ujęta w słowach D. E. Knutha — programowanie może być sposobem sprawdzenia, czy właściwie rozumiemy problem i jego rozwiązanie oraz czy po­ trafimy zastosować to rozwiązanie w konkretnej sytuacji i przekazać je innym osobom oraz maszynom. Układ książki i sposoby korzystania z niej Książka składa się z 15 rozdziałów, stanowiących niezależne jednostki tema­ tyczne, które można studiować w dowolnej kolejności. Kluczem do wyboru po­ szczególnych partii materiału mogą być pojęcia, będące przedmiotem rozważań w poszczególnych rozdziałach. Dla ułatwienia, pojęcia te są wymienione w ram­ ce na początku każdego rozdziału i zebrane w skorowidzu na końcu książki. Prezentacja sytuacji problemowych, dyskusja rozwiązań i sposoby wyprowadze­ nia algorytmów są silnie związane z naturą rozważanych problemów, przez co książka nie ma jednorodnej struktury. Autor starał się przy tym dobrać możliwie najbardziej elementarny, a jednocześnie wystarczająco przekonujący sposób przedstawienia, który z jednej strony — umożliwia dostrzeżenie charak­ terystycznych cech rozważanych sytuacji, a z drugiej — kieruje ku najbardziej właściwym sposobom ich rozwiązywania. Książka ma za zadanie włączyć uczącego się w proces tworzenia metod rozwią­ zywania sytuacji problemowych i powstawania algorytmów, jako współtwórcę ostatecznego rozwiązania. Książka jest przeznaczona również dla tych, którzy w rozwiązywaniu pro­ blemów chcą posłużyć się komputerem. Dla nich, opisy prawie wszystkich algo­ rytmów są rozwinięte do postaci umożliwiającej napisanie odpowiedniego pro­ gramu w języku Pascal. Do trudniejszych algorytmów zostały napisane progra­ my w języku Pascal — ich teksty znajdują się na końcu książki w Dodatku. Można również skorzystać z programu ELI, który znajduje się na dyskietce załączonej do książki Algorytmy, by przedstawić rozwiązanie w postaci projektu zbudowanego z gotowych klocków, odpowiadających podstawowym kon­ strukcjom algorytmicznym. 6

Podziękowania Dziękuję tym wszystkim uczniom, studentom i nauczycielom w szkołach i uczelniach, którzy życzliwie przyjęli książkę Algorytmy i podzielili się ze mną swoimi uwagami i radami. Szczególnie jestem wdzięczny dr Helenie Krupickiej za uwagi, które nasunęły się Jej w trakcie wykorzystywania książki Algorytmy na zajęciach z przedmiotu „Wstęp do informatyki”, prowadzonych ze studen­ tami I. roku informatyki Uniwersytetu Wrocławskiego oraz za szczegółową lekturę niniejszej książki i wiele sugestii, które pomogły mi udoskonalić pre­ zentację. Składam podziękowania recenzentom, Iwonie Krajewskiej-Kranas i Witoldowi Kranasowi, za ich propozycje ulepszeń książki oraz dyskusje nad jej zawar­ tością. Pani Redaktor Annie Łaskiej-Gmaj jestem głęboko wdzięczny za pełną pieczę nad powstawaniem tej książki. Maciej M. Sysło syslo@ii.uni.wroc.pl Wrocław, luty 1998 r.

Oznaczenia i wyróżnienia w tekście Taka ramka na początku rozdziału zawiera wykaz pojęć, którym są po­ święcone rozważania w danym roz­ dziale. Co tkwi w nazwie? Czy róża pachniałaby słodziej, gdyby nazywała się inaczej? [William Shakespeare — poeta angielski, dramatopisarz i aktor] Zalecamy zapoznanie się z treścią tekstu umieszczonego na szarej apli, jeszcze przed lekturą tekstu znajdującego się obok — jest to często lakoniczne ujęcie tła dla prowadzonych rozważań. Wszystkie wyróżnienia w tekście, takie jak: rodzaje pisma, ramki oraz ikony mają na celu zwrócenie uwagi na charakter prezen­ towanych treści oraz powinny ułatwić ko­ rzystanie z książki. Pojęcia definiowane w tekście są pisane pogrubioną czcionką. Czcionkipochyłej użyto do zapisania symboli i wzorów matematycznych. Fragmenty programów w języku Pascal są pisane czcionką nieproporcjonalną. Wiele fragmentów tekstu poprzedzają ikony. O . Ta ikona oznacza początek rozważań, na ogół są to zadania do wykona- nia przez Czytelnika, które dotyczą realizacji opisanych algorytmów w postaci programów w języku Pascal i wykonania obliczeń za pomocą kom­ putera. Tym znakiem poprzedzamy informacje, stanowiące rozszerzenie i uogól­ nienie rozważanych zagadnień, w których często odsyłamy do innych opracowań. W szczególności, pod tym znakiem są często zgrupowane odwo­ łania do książki Algorytmy. Każdy wyróżniony ikoną fragment tekstu, jak również fragment stanowiący zamknięty blok, np. treść zadania lub opis algorytmu, jest zakończony znakiem ■

1. Dodaj do smaku szczyptę soli — czy przepisy kulinarne są algorytmami? A le ... nie napisano trucizna, więc Alicja odważyła się spróbować i odkrywszy, że zawartośćjest bardzo smaczna (w rzeczywistości smakowała jak ciastko z wiśniami, zmieszane ze śmietanką, ananasem, pieczonym indykiem, ciągutką i gorącą grzanką posmarowaną masłem), szybko wypiła wszystko do dna. [Lewis Carroll Przygody Alicji w kramie czarów] Pojęcia: • przepis kulinarny = algorytm? • składniki spożywcze = dane? • potrawa = wynik? • kucharz + sprzęt = komputer? Co mogło być napisane na naczyniu, które zawierało coś, co tak smakuje? A z czego i w jaki sposób przygotować taką potrawę czy też napój? Rozpoczynamy tę książkę podobnie, jak zaczyna się wiele książek poświęconych al­ gorytmom i algorytm ice — od przytocze­ nia przepisu kulinarnego. W naszym przy­ padku jednak, w przeciwieństwie do więk­ szości innych książek, jest to w pewnym sensie negatywny przykład — postaramy się przekonać Cię, że gruncie rzeczy książ­ ka kucharska, jako zbiór przepisów, nie jest zbiorem algorytmów w znaczeniu, któ­ re przyjmujemy za właściwe. W tym rozdziale wykorzystamy przepis na staropolską potrawę. Zaczerpnęliśmy go z książki Marii Lemnis i Henryka Vitry W staropolskiej kuchni i przy polskim stole (Wyd. Interpress, Warszawa 1983), w której poza przepisami tradycyjnej kuchni można zapoznać się z obyczajami panującymi przy stole oraz relacjami z wielu sławnych, historycznych biesiad Polaków. Przytoczymy tu w całości, znajdujący się w tej książce przepis na chłodnik litewski. Do zapoznania się z rozważaniami za­ wartymi w tym rozdziale jest wymagana niewielka znajomość algorytmiki. Posta­ nowiliśmy jednak zamieścić je na począt­ ku książki, by wywołać u Czytelnika ape­ tyt... na algorytmy. Proponujemy również wykonać eksperymenty opisane pod koniec rozdziału, wtedy będzie można zaspokoić również apetyty kulinarne. Zachęcamy do powrotu do lektury tego rozdziału po zapoznaniu się z innymi fragmentami książki, gdy znane już będą właściwe znaczenia podstawowych pojęć algorytmiki. 9

Chłodnik litewski Chłodnik, zwany także „chołodźcem”, jest zimną, nie gotowaną zupą, bogatą w witaminy, przyjemnie kwaskowatą i orzeźwiającą. Istnieje kilka odmian chłodnika, można bowiem z dużą swobodą stosować i dozo­ wać dodatki. Podajemy wypróbowany i powszechnie znany przepis, bardzo prosty do przyrządzenia. 1/4 I kwasu buraczanego lub kwasu ze świeżo ukiszonych ogórków łączymy, lek­ ko ubijając, z 1/4 I gęstej młodej śmietany oraz 1/2 I niezbieranego kwaśnego mle­ ka (ew. maślanki albo jogurtu). Jeśli użyliśmy jedynie kwasu ogórkowego, chłod­ nik zabarwiamy na różowy kolor sokiem wyciśniętym (przez gazę) z utartego na miazgę surowego buraka ćwikłowego. Można też użyć 1/8 I kwasu buraczanego i 1/8 I kwasu ogórkowego i w razie konieczności chłodnik dobarwić. W dawniej­ szych przepisach zalecano dodawanie do chłodnika zimnego rosołu, jest to jed­ nak zupełnie zbyteczne. Chłodnik solimy do smaku, nie zapominając o odrobinie cukru pudru; powinien być łagodny, lecz zdecydowanie kwaskowaty. Teraz doda­ jemy spory pęczek drobniutko posiekanego kopru i mały pęczek drobno posieka­ nego szczypiorku. Można też dodać łyżeczkę utartej na miazgę cebuli. Koniecz­ nym natomiast dodatkiem jest pokrajany na drobną kostkę świeży, obrany ogórek, wskazanym zaś — pęczek pokrajanej na cieniutkie plasterki rzodkiewki. Jeżeli natomiast chłodnik zakwasiliśmy wyłącznie kwasem ogórkowym, szczypiorku można nie dodawać, natomiast zwiększyć ilość kopru. Chłodnik musi „dojrzewać" w chłodnym miejscu przez 2 godziny. Na godzinę przed podaniem wstawić go na „parter” lodówki. W głębokie talerze kładziemy po 4 ćwiartki jaj ugotowanych na twardo i zalewamy je bardzo zimnym chłodnikiem. Do chłodnika można dodać pokrajaną w drobną kostkę zimną pieczeń cielęcą. Najwykwintniejszym, ale też i najtrudniej osiągalnym, a przy tym bardzo drogim dodatkiem są ugotowane i obrane szyjki rakowe. Próbowano je zastąpić, bez powodzenia, krewetkami, lecz chłodnik litewski i krewetki to dwa różne i nie do pogodzenia (w jednym garnku) światy. O ostatecznym szlifie smakowym chłodnika decyduje (jak w większości „zło­ żonych” potraw) indywidualny smak. Jedni wolą chłodniki bardziej kwaśne, inni łagodniejsze. Jedno tylko obowiązuje bezwzględnie: chłodnik musi być naprawdę zimny. ■ Czy ten przepis na sporządzenie chłodnika litewskiego jest algorytmem? W potocznym, encyklopedycznym znaczeniu, algorytm jest opisem krok po kroku rozwiązania postawionego problemu lub sposobu osiągnięcia jakiegoś celu. Ponieważ naszym celem jest przyrządzenie chłodnika litewskiego, po­ wyższy przepis umożliwia osiągnięcie tego celu. Aby jednak mógł on być uzna­ ny za algorytm, powinien spełniać kilka warunków. Przedyskutujemy je tutaj krótko. 10

Jeśli algorytm jest opisem sposobu osiągnięcia jakiegoś celu, to ten cel powi­ nien być dokładnie określony, a jeśli rozwiązuje problem — to również należy precyzyjnie opisać ten problem. W każdym postępowaniu, w którym będziemy stosować algorytm, można wyróżnić: dane, które służą do osiągnięcia celu, oraz sam cel, czyli wynik działania. W algorytmice, czyli w dziedzinie zajmującej się algorytmami, ten układ danych i wyników nazywa się specyfikacją problemu, który mamy rozwiązać lub celu, który mamy osiągnąć. Specyfikację problemu tworzą więc: dane i wynik (lub cel). Dodatkowo, należy podać wszystkie cechy danych i wyniku oraz określić, jaki ma być związek danych z wynikami — czyli, jak rodzaj i ilość oraz jakość danych ma wpływać na wynik. Spróbujmy sformułować specyfikację problemu, polegającego na przyrządze­ niu chłodnika litewskiego. W najogólniejszej postaci można napisać krótko: Specyfikacja czynności przygotowania chłodnika litewskiego Dane: składniki spożywcze, opisane w powyższym przepisie na chłodnik. Wynik: chłodnik litewski otrzymany zgodnie z powyższym przepisem. ■ Spróbuj teraz bardziej sprecyzować tę specyfikację. Zadanie 1.1. Z przepisu na chłodnik, wypisz wszystkie składniki spożywcze, które mają być użyte do jego sporządzenia. Przy każdym składniku wymień jego ilość i cechy. Wyróżnij te składniki, które są opcjonalne, tzn. mogą, ale nie muszą być użyte. ■ Rozwiązanie tego zadania będzie stanowić dokładny opis danych. Wypiszmy je tutaj również, by móc skomentować ich charakter. Dane: składniki spożywcze, niezbędne do przyrządzenia chłodnika litewskiego według powyższego przepisu: • kwas buraczany lub kwas ze świeżo ukiszonych ogórków — 1/4 1, albo kwas buraczany i kwas ogórkowy — po 1/8 I, • gęsta młoda śmietana — 1/41, • niezbierane kwaśne mleko (ew. maślanka albo jogurt) — 1/21, • sok z surowego buraka ćwikłowego (w razie konieczności), • sól — do smaku, • cukier puder — odrobina, • koper — spory pęczek, • szczypiorek — mały pęczek, • cebula — łyżeczka, • świeży ogórek, • rzodkiewka — pęczek, • jaja — 1 sztuka na osobę, • pieczeń cielęca lub szyjki rakowe. Sporządzenie tego spisu składników nie zajęło nam zbyt wiele czasu. Natomiast precyzyjne określenie wyniku, to już inne zadanie. Jest jednak wątpliwe, czy 11

jest to możliwe, bowiem poza stwierdzeniem, że ma to być zupa, znana jako chłodnik litewski, w jej przepisie nie znajdujemy innego określenia. Jest tam tylko jeden, zdecydowany warunek: chłodnik musi być naprawdę zimny. A za­ tem, chłodnikiem jest to coś, co otrzymamy, wykorzystosując podane składniki i wykonując czynności zgodnie z przepisem. Można więc powiedzieć, że wynik w przepisie kulinarnym jest dokładnie określony dopiero na podstawie opisu sposobu jego otrzymania. Wróćmy jeszcze do danych — od nich bowiem zależy wynik, w tym przypadku — postać i smak potrawy. Po pierwsze, znajdujemy wśród nich wiele mało pre­ cyzyjnych określeń, np.: wiemy co to jest śmietana, ale jak się przekonać, że jest ona gęsta i młoda? Jeszcze gorzej jest z precyzją określenia ilości niektórych składników: do smaku, odrobina, spory, mały, a nawet — łyżeczka. A zatem, dane te nie mają cechy dobrej określoności, gdyż ich określenia oraz ilości nie są precyzyjne i nie dla każdej osoby przyrządzającej chłodnik tyle samo znaczą. Zwróćmy jeszcze uwagę na jedną kwestię. Czy z podanego przepisu wynika, dla ilu osób będzie ta potrawa? Na podstawie objętości składników można obli­ czyć, że samych płynów zostanie użyty 1 litr. Składniki stałe zwiększą tę obję­ tość może o 1/4 litra. A my chcielibyśmy, aby taki przepis nadawał się do sporządzenia chłodnika dla dowolnej liczby osób. A zatem te dane nie mają także cechy uniwersalności, ale to można próbować jakoś naprawić. Zadanie 1.2. Przyjmij, że na podstawie podanego wyżej przepisu na chłodnik litewski zostanie sporządzona zupa dla czterech osób. Zmodyfikuj dane w taki sposób, aby wśród nich znalazła się również liczba n, określająca dla ilu osób ma to być potrawa — wtedy ilości wszystkich składników podaj w zależności od n. m Jak sobie poradziłaś z określeniem ilości — szczypta, do smaku, odrobina, spory? Jak nadmieniliśmy, wynik posłużenia się powyższym przepisem nazywa się chłod­ nikiem litewskim, ale dokładne określe­ nie, co to jest chłodnik litewski musimy zastąpić opisem, jak się go otrzymuje. Spróbujmy sformułować podany przepis w postaci listy kroków. Krok 1. {Przygotowanie składników} Przygotuj wszystkie składniki wymienio­ ne wśród danych, w odpowiedniej postaci i ilości. Krok 2. 1/4 I kwasu buraczanego lub kwasu ze świeżo ukiszonych ogórków połącz, lekko ubijając, z 1/4 I gęstej młodej śmietany oraz 1/2 I niezbie- ranego kwaśnego mleka (ew. maślanki albo jogurtu). Możesz też użyć 1/8 I kwasu buraczanego i 1/8 I kwasu ogórkowego. W tym rozdziale wyjątkowo w pierwszej kolejności zwracamy się bezpośrednio do dziewcząt, kierując się tradycyjnym spoj­ rzeniem na kuchnię, jako domenę dzia­ łania pań. 12

Krok 3. Jeśli użyłaś jedynie kwasu ogórkowego, to chłodnik zabarw na różowo sokiem wyciśniętym (przez gazę) z utartego na miazgę surowego bu­ raka ćwikłowego. Krok 4. Posól do smaku i nie zapomnij o odrobinie cukru pudru — chłodnik powinien być łagodny, lecz zdecydowanie kwaskowaty. Krok 5. Dodaj spory pęczek drobniutko posiekanego kopru i mały pęczek drobno posiekanego szczypiorku. Możesz też dodać łyżeczkę utartej na miazgę cebuli. Krok 6. Dodaj pokrajany na drobną kostkę świeży, obrany ogórek; wskazane jest dodanie również pęczka pokrajanej na cieniutkie plasterki rzod­ kiewki. Krok 7. Jeżeli chłodnik zakwasiłaś wyłącznie kwasem ogórkowym, to szczy­ piorku możesz nie dodawać, natomiast zwiększ ilość kopru Krok 8. Możesz dodać pokrajaną w drobną kostkę zimną pieczeń cielęcą, a najlepiej — ugotowane i obrane szyjki rakowe. Krok 9. Ugotuj jajka na twardo — po jednym dla każdej osoby. Krok 10. Odstaw chłodnik w chłodne miejsce na 2 godziny, a na godzinę przed podaniem wstaw go na „parter” lodówki. Krok 11. Połóż w głębokim talerzu 4 ćwiartki jajka i zalej je bardzo zimnym chłodnikiem. ■ W tym opisie nie uwzględniliśmy kilku sformułowań z oryginalnego przepisu, które mogą mieć duży wpływ na ostateczny wynik, wśród nich: można bowiem z dużą swobodą stosować i dozować dodatki, o ostatecznym szlifie smakowym chłodnika decyduje indywidualny smak. Czy ten opis sposobu przyrządzenia chłodnika można nazwać algorytmem? Niewątpliwie, jako wynik wykonania wszystkich 11 kroków na składnikach wy­ specyfikowanych w danych, otrzymamy chłodnik litewski. I będzie to zupa o in­ dywidualnym smaku. Właśnie m.in. ta ostatnia cecha wyniku powstrzymuje nas przed nazwaniem tego przepisu algorytmem. Od algorytmu bowiem będziemy wymagać, by jego kroki były dobrze określone, czego niestety nie można powie­ dzieć o większości poleceń, w których operuje się m.in. nieprecyzyjnie określo­ nymi ilościami składników. Kolejną kwestią jest sprzęt (ang. hardware), czyli urządzenia używane do sporządzania potrawy. Wiele z nich zapewne nie gwarantuje np. precyzyjnego odmierzania ilości składników. Do „urządzeń” wykonujących chłodnik musimy też zaliczyć kucharza. Niestety jest to kolejne ogniwo algorytmu, o którym nie można powiedzieć, że jest „dobrze określone”. Wszystkie bowiem decyzje, do­ tyczące postaci i ilości składników, w tym zwłaszcza takie, jak: do smaku, odro­ 13

bina, spory i mały pęczek, zależą tylko od niego. A zatem, nie możemy być pew­ ni, że ten „komputer” kulinarny, czyli kucharz wraz ze swoimi sprzętem będzie „działał” zawsze tak samo. Dyskusja ta wiedzie nas do konkluzji, że przepisu kulinarnego nie można uznać za algorytm służący do otrzymania potrawy, w tym przypadku — chłodnika litewskiego, gdyż nie są w nim dobrze określone: • dane, czyli składniki spożywcze, zarówno co do postaci, jak i ilości; • poszczególne polecenia przepisu; • kucharz wraz ze sprzętem kuchennym. Przepis kulinarny nie jest więc na ogół algorytmem w takim sensie, w jakim przyjmuje się w algorytmice, gdyż nie gwarantuje on, że na jego podstawie, dla jednakowych danych otrzymamy zawsze ten sam wynik. Tak się dzieje, gdyż nie­ mal żaden element przepisu kulinarnego nie jest dobrze określony. O tych cechach przepisu kulinarnego możesz przekonać się, wykonując ekspe­ ryment na lekcji techniki, przeznaczonej na przygotowanie chłodnika litewskie­ go. Proponujemy, by był to eksperyment wykonywany przez całą klasę. Zadanie 1.3. Najpierw uzgodnijcie w całej klasie zmodyfikowaną postać spe­ cyfikacji problemu, precyzując dokładnie wszystkie składniki wśród danych, a następnie — poszczególne kroki algorytmu. Uwzględnijcie te produkty, które są dla wszystkich dostępne i nie są zbyt drogie. ■ Sporządzenie chłodnika nie wymaga gotowania (z wyjątkiem jajek, które można przynieść z domu już ugotowane), należy jedynie odpowiednio przygo­ tować i wymieszać wszystkie składniki, zatem może to być łatwo wykonane w klasie. Zadanie 1.4. Ponieważ oryginalny przepis jest przewidziany do przyrządzenia zupy dla czterech osób, podzielcie się w klasie na zespoły czteroosobowe. Posługując się opisami sporządzonymi jako rozwiązanie zad. 1.3 oraz zawczasu przygotowanymi składnikami, sporządźcie w każdej grupie swój chłodnik litewski. Nieprecyzyjne określenia w poleceniach przepisu rozstrzygajcie kole­ gialnie. ■ A teraz wreszcie nadszedł dla Was czas na degustację wyników ... naszych roz­ ważań. Zadanie 1.5. Przetestujcie otrzymane w klasie wyniki użycia swojego przepisu na chłodnik. Porównajcie najważniejsze cechy tej potrawy, które decydują o jej smaku, a więc, czy jest: przyjemnie kwaskowata, orzeźwiająca, naprawdę zimna, słona do smaku, dość słodka. Na końcu wybierzcie głosami większości najlep­ szy z chłodników. ■

2. Jak budowano piramidy Człowiek boi się czasu, lecz czas lęka się piramid. [Powiedzenie arabskie] Pojęcia: • piram idy— jak je budowano? • wynik— jak go osiągnąć? • strategie dziel-i-rządź oraz dziel-i-zwyciężaj. Jeśli algorytm jest opisem krok po kroku sposobu osiągnięcia jakiegoś celu, to za cel możemy przyjąć stojące do dzisiaj piramidy i zapytać, jak je zbudowano. Frapuje więc nas problem odwrotny do najczęściej rozważanego w algorytmice — znamy wyniki działania pewnego algorytmu, chcielibyśmy poznać sam algorytm. Masz więc tutaj okazję włączyć się do poszukiwania metod powstania tych budowli. Pochodzenie piramid Wśród wszystkich cudów świata jedynie piramidy znajdują się na każdej ich liście. Jedną z najbardziej znanych jest lista siedmiu cudów świata sporządzona przez Filona z Bizancjum (ok. 225 r. p.n.e.), na której obok piramid wymie­ nione są: Kolos Rodyjski, posąg Zeusa Olimpijskiego dłuta Fidiasza, latarnia morska na wyspie Faros naprzeciw Ale­ ksandrii, Mauzoleum w Halikarnasie, Wi­ szące Ogrody Semiramidy w Babilonie i świątynia Artemidy w Efezie. Większość piramid wzniesiono w okresie Starego Państwa, w latach 2686-2181 p.n.e., w czasie panowania III—VI dynastii faraonów. Mają więc one ponad 4500 lat. Piramidy są naziemnymi częściami grobowców i służyły jako miejsce wiecznego spoczynku władców Egiptu i ich małżonek. Zlokalizowano około 100 piramid. Egipcjanie Epoki Piramid wie­ rzyli, że po fizycznej śmierci ciała jest możliwy dalszy żywot ducha, gdy tylko Podane tutaj informacje dotyczące histo­ rii oraz budowy piramid pochodzą ze źródeł wymienionych na końcu tego roz­ działu. Musimy uprzedzić, że nawet te publikacje zawierają wiele sprzecznych danych. 15

ciało nie zostanie zniszczone i będzie zaopatrywane w zapasy żywności. Do gro­ bowców wkładano więc przedmioty przeznaczone do użytku zmarłego, w tym również łodzie umożliwiające pośmiertne wędrowanie. Wielkość i rozmiary piramid Dalej piszemy głównie o Wielkiej Piramidzie i jej otoczeniu — zob. rys. 2.1. Została ona zbudowana dla faraona Cheopsa (jest to greckie imię, w oryginale egipskim brzmi ono Khufu) na zachodnim brzegu Nilu w Gizie, który obecnie stanowi przedmieścia Kairu. Obok stoją również: piramida faraona Khafre — syna Cheopsa, wzniesiona razem ze Sfinksem, oraz najmniejsza wśród tych trzech piramida Menkaure — syna Khafre. Wszystkie te budowle zostały wzniesione w ciągu około 75 lat! Rysunek 2.1. Wielka Piramida (piramida Cheopsa) w otoczeniu innych budowli w Gizie Wielka Piramida jest największym osiągnięciem Epoki Piramid zarówno pod względem rozmiarów, jak i doskonałości wykonania. Wszystkie boki podstawy mają około 230 m długości, a różnica między nimi nie przekracza 20 cm. Boki są niemal dokładnie zorientowane według stron świata — odchylenia nie przekraczają 5 minut, a zatem krawędzie podstawy tworzą w narożnikach niemal idealne kąty proste. Wysokość piramidy wynosiła blisko 147 m, a obec­ nie jest mniejsza o 945 cm. 16

Zadanie 2.1. Porównaj rozmiary innych, znanych Ci budowli z rozmiarami pira­ midy Cheopsa. W tym celu wykonaj szkic tych budowli w tej samej skali. Wy­ bierz budowle, które widziałeś i wydały Ci się monumentalne. Spróbuj również umieścić na powierzchni zajmowanej przez tę piramidę jak największą liczbę znanych Ci budowli. ■ Na rysunku 2.2 przykładowo zestawiono z Wielką Piramidą dwie znane bu­ dowle. Rysunek 2.2. Wielkie budowle w cieniu Wielkiej Piramidy Jeśli Wielka Piramida jest tak duża, to ile zużyto na nią budulca? Oszacowano, że składa się ona z około 2 300 000 kamiennych bloków, z których każdy waży średnio 2.5 tony, a największy blok — leżący na stropie Królewskiej Komnaty — waży blisko 20 ton. Zadanie 2.2. Przyjmij, że Wielka Piramida składa się z 2300000 kamiennych bloków. Załóż również, że budowano ją przez 20 lat (faraon Cheops panował niewiele dłużej niż 20 lat), pracując każdego dnia od świtu do nocy, czyli przez 14 godzin na dobę. Przyjmując, że bloki trafiały na swoje miejsce w równych odstępach czasu, oblicz, jak często (czyli, co ile minut) musiano je ustawiać na swoim miejscu. ■ To wręcz niewiarygodne, by w takim tempie mogła powstawać Wielka Pirami­ da! A jednak. Wykonaj jeszcze jedne obliczenia, które uzmysłowią Ci ogromne rozmiary tej budowli. 0 ilości kamienia, zużytego do postawie­ nia trzech piramid w Gizie, mogą świad­ czyć wyniki obliczeń, które rzekomo wykonał Napoleon w czasie kampanii egipskiej: wystarczyłoby go na zbudowa­ nie wokół Francji muru o wysokości 3 m 1grubości 1 m! 17

Zadanie 23. Przyjmij dla ułatwienia, że piramidę Cheopsa zbudowano z jedna­ kowych bloków o wysokości 2 m i wymiarach podstawy 3 m na 3 m. Z ilu takich bloków musiałaby się ona składać? Co ile minut musiałby trafiać taki blok na swoje miejsce, gdyby wznoszono ją po 14 godzin dziennie przez 20 lat? Wskazówka. Podziel całą piramidę na warstwy o wysokości równej 2 m i oblicz, ile bloków o rozmiarach 3 m na 3 m znajdzie się w każdej warstwie. Następnie zsumuj te liczby. ■ Wspomnieliśmy już, że piramidy cechuje również duża dokładność ich wykona­ nia. Dotyczy to zarówno wymiarów, jak i dopasowania bloków. Jedno z drugim jest zresztą ściśle związane, trudno bowiem byłoby utrzymać zamierzone wymiary, gdyby pojedyncze bloki nie były dobrze wykończone i dopasowane. Podaje się, że bloki zostały spasowane z dokładnością do 1/50 cala, co powodu­ je, że dzisiaj nie można między nie wcisnąć nawet żyletki! Kto budował piramidy Kamień na budowę Wielkiej Piramidy pochodził z wyrobisk znajdujących się blisko miejsca jej ustawienia, a część dowożono Nilem, który w okresie wylewu przepływał w odległości 400 m od placu budowy. Zatem przy budowie byli po­ trzebni robotnicy zajmujący się: wycinaniem, obróbką i dopasowaniem kamien­ nych bloków oraz transportem olbrzymich bloków na znaczną odległość i wyso­ kość. Przy tym stosowano jedynie narzędzia wykonane z miedzi (m.in. dłuta i piły) — do wycinania i szlifowania kamienia, drewniane kliny — do powodo­ wania pęknięcia skały, drewniane płozy i belki oraz liny — do przemieszczania bloków. Z braku krążka, którego Egipcjanie nie znali, najpoważniejszą ope­ racją było wynoszenie bloków na wymaganą wysokość. W tym celu posługiwano się pochylniami, budowanymi wokół piramidy. Według greckiego historyka Herodota, który w V w. p.n.e. podróżował po Egipcie, Wielką Piramidę budowało 100 tys. robotników. Współcześni badacze piramid twierdzą, że wystarczyło 30-40 tys. robotników. Te ostatnie liczby są szacowane również na podstawie możliwości wyżywienia i „zakwaterowania” robotników wokół budowy. Wszyscy są zgodni, że piramidy nie są dziełem olbrzymich rzesz niewolników, ani zwykłych wolnych ludzi, a brały w tym udział zespoły wykwalifikowanych robotników. Przy tym przedsięwzięciu pracowano z takim poświęceniem i wysiłkiem, jakiego trudno się doszukać w jakiejkolwiek innej kulturze. Zadanie 2.4. Rozwiązując zad. 2.3 obliczyłeś, ile równej wielkości kamiennych bloków należało postawić jedne na drugich, aby utworzyć z nich Wielką Pira­ midę. Teraz, przydziel robotników do tej pracy. Dla ułatwienia przyjmij, że każdy blok był wycinany, szlifowany, transportowany i ustawiany przez taką 18

samą liczbę robotników. Określ według swojego uznania, ile te czynności zabie­ rały im czasu. Pamiętaj jednak, że ze względu na ograniczony dostęp, nad jed­ nym blokiem nie mogło pracować jednocześnie zbyt wiele osób. Na podstawie tych rachunków oblicz, ilu robotników musiałoby brać udział w tej hipotetycz­ nej budowie Wielkiej Piramidy. ■ Pomijamy tutaj przypuszczenia, że piramidy budowali przybysze z innych pla­ net i cywilizacji, na co niektórzy znajdują potwierdzenie w samych piramidach. Techniki pracy Nawet na podstawie tak krótkiego opisu, jak powyższy, można określić w za­ rysie coś, co dzisiaj nazwalibyśmy „kolejnymi krokami algorytmu”, według którego budowano piramidy. Ewentualny taki „algorytm” jest jednak powodem największych rozbieżności między badaczami piramid, gdyż jest mało prawdo­ podobne, że stosując go, można by dzisiaj powtórzyć wyczyn sprzed 4500 lat. Jak napisaliśmy, przy budowie piramid pracowano bez sprzeciwu, a wręcz — z poczuciem zaszczytu wykonywania przy­ sługi swojemu władcy, chociaż niewątpli­ wie, nie wszyscy musieli być z tego zado­ woleni. Zarządzający budową posługiwali się zapewne zasadami, które nazwano i sformalizowano znacznie później: rzym­ ską zasadą dziel i rządź (łac. divida et im­ pera) — odpowiedni podział siły roboczej zapewniał posłuszeństwo — oraz zasadą algorytmiki dziel i zwyciężaj (ang. divide and conquere) — podział pracy z dobrze zaplanowaną komunikacją i współdziała­ niem między grupami był niewątpliwie jedną z podstawowych zasad postępowania w przedsięwzięciu na taką skalę, które w ostateczności przyniosło zwycięstwo w postaci ukończonych budowli (zastosowanie tej drugiej zasady ilustrujemy w rozdz. 10). Konkluzja Nie znamy dzisiaj algorytmu, według którego organizowano budowę piramid. Budowle te jednak stoją do dzisiaj, jest ich około 100, a więc ich twórcom mu­ siał być znany algorytm ich budowania, którego nie potrafimy dzisiaj odtwo­ rzyć. Sytuacja jest więc taka, że wynik zastosowania algorytmu jest znany — bo piramidy stoją — natomiast nie znamy samego algorytmu. Jeden z badaczy piramid zlecił firmie bu­ dowlanej, wykonującej konstrukcje na rzecz rządu amerykańskiego, by oceniła wykonalność zadania zbudowania pira­ midy o wielkości odpowiadającej Wiel­ kiej Piramidzie, narzędziami stosowa­ nymi przez ówczesnych budowniczych. Stosując tzw. metodę ścieżki krytycznej do planowania przedsięwzięć, specjaliści tej firmy obliczyli, że 4000 do 5000 robot­ ników zbudowałoby ją dzisiaj w ciągu 20-40 lat. 19

Osobom zainteresowanym tematem piramid polecamy bardziej szcze­ gółowe opracowania na ten temat, są to książki: I. E. S. Edwards Piramidy Egiptu PIW, Warszawa 1995, J. Romer, E. Romer Siedem cudów świata PIW, Warszawa 1997 oraz strony WWW pod adresem: http://www.pbs.org/wgbh/nova/pyramid/ ■ Zadanie 2.5. Jeśli jesteś bardziej zainteresowany, jak budowano piramidy, to zajrzyj na strony WWW pod podanym wyżej adresem i przejrzyj relacje z ostat­ nich wykopalisk prowadzonych w Gizie. Na tej podstawie przygotuj krótkie wystąpienie dla swoich rówieśników na temat: „Koncepcje budowy piramid w świetle najnowszych odkryć archeologicznych”. ■

3. Zabawy towarzyskie Tracisz 100% szans, których nie podejmujesz. [Wayne Gretzky — hokeista kanadyjski] Ten rozdział jest poświęcony znajdowaniu w zbiorze elementu, który ma szczególne własności względem innych elementów. Przedstawiamy rozwiązania dwóch tego typu problemów w postaci gry między grupą osób, którą może sta­ nowić cała klasa. W obu przypadkach jest łatwo opisać poszukiwany element i można go łatwo znaleźć, korzystając jedynie z jego definicji. Naszym celem tutaj jest jednak naprowadzić Cię na metody, które nie są tak oczywiste, ale za to bardzo szybkie w działaniu. Pierwszy problem dotyczy znajdowania idola, a drugi — lidera. O pierwszym jedynie wspomnieliśmy w książce Algorytmy i pozostawiliśmy go do samodzielnego rozwiązania (zob. problem 13.22), a dla drugiego — podaliśmy rozwiązanie (zob. p. 5.6.1). Jeśli nawet zapoznałeś się z tymi problemami w książce Algorytmy, to i tak nie powinieneś się tutaj nudzić, gdyż piszemy o nich całkiem inaczej, angażując stopniowo Ciebie i całą klasę w otrzymanie rozwiązań. 3.1. Kto jest idolem? Na dużym oficjalnym przyjęciu na ogół nie wszyscy się znają. Wśród gości może się zjawić wiele powszechnie znanych osób. Często ambicją gospodarzy, którymi może być fundacja lub stowarzyszenie, jest zaproszenie osoby niezmiernie popularnej wśród wszystkich gości, na przykład aktora filmowego, piosenkarza lub prezentera telewizyjnego. W takich przypadkach dochodzi czasem do absurdalnej sytuacji, gdy zaprasza się osobę, której osobiście nie znają nawet gospodarze imprezy! Idolem, dla uczestników takiego przyjęcia, możemy nazwać osobę, która jest znana (przynajmniej z wyglądu) wszystkim gościom, ale sama nie zna nikogo. Twoim zadaniem jest wykryć, czy w towarzystwie złożonym z n osób znajduje się idol. Pojęcia: • relacja, • warunek, • wartość logiczna (Boolowska), • tablica, • iteracja, • pracochłonność algorytmu. 21

Uwaga. Musimy podać tutaj dwa, dość istotne ograniczenia „znajomości”, czyli znaczenia powiedzenia „ja znam tę osobę” lub „osoba A zna osobę fi”. Po pierwsze, nie jest to relacja zwrotna, to znaczy, jeśli „osoba A zna osobę fi”, to jeszcze nie wynika stąd, że „osoba B zna osobę A ”. Jest to dość naturalne ograniczenie, zwłaszcza wtedy, gdy B jest rzeczywiście idolem — wszyscy go znają, ale on zna niewiele osób. Po drugie, fakt, że „osoba A zna osobę B” nie oznacza, że osoba B o tym wie. Stąd wynika, że aby się dowiedzieć, czy „osoba A zna osobę B”, musimy zapytać o to osobę zł, gdyż B może o tym nie wiedzieć — tak jest najczęściej, gdy osoba B jest idolem. ■ Uściślijmy teraz postać podstawowej „operacji”, jaką można wykonywać w poszukiwaniu idola w grupie osób. Polega ona na wybraniu dwóch osób z tej grupy, powiedzmy zł i B, oraz zadaniu jednej z nich, powiedzmy zł, pytania, czy zna tę drugą osobę. Odpowiedź może mieć jedną z dwóch postaci: „tak” lub „nie”. Zadanie 3.1. Zaproponuj, bez specjalnego namyślania się, jakąś metodę wykry­ wania, czy w danej grupie osób znajduje się idol. Ile razy musiałeś wykonać podstawową operację, czyli sprawdzić, czy jedna osoba zna drugą? ■ A teraz dochodzimy do najważniejszego fragmentu naszych rozważań — rozwiąż koniecznie następne zadanie. Zadanie 3.2. Przypuśćmy, że osobie (Panu) zł zadałeś pytanie: „czy zna Pan Panią B” i otrzymałeś odpowiedź „tak”. Która z tych dwóch osób ma szansę być idolem, a która nim nie jest? A jaki jest wniosek, gdy otrzymałeś odpowiedź „nie”? ■ Rozwiązanie ostatniego zadania ma przełomowe znaczenie dla dalszych roz­ ważań i w gruncie rzeczy jest kluczem do metody, o którą nam tutaj chodzi. Jeśli na pytanie, „czy Pan zł zna Panią B”, zadane Panu zł, otrzymałeś odpo­ wiedź „tak”, czyli zł zna B, to A nie może być idolem, bo idol nie zna nikogo w towarzystwie. Jeśli otrzymałeś odpowiedź „nie”, czyli zł nie zna fi, to z kolei B nie może być idolem, bo idol jest wszystkim znany. Zatem zadanie jednego py­ tania dotyczącego dwóch osób eliminuje z towarzystwa jedną z nich spośród kandydatów na idola. Rozwiązanie zad. 3.2 możemy więc sformułować w posta­ ci następującego wniosku: bez względu na odpowiedź, „tak” lub „nie”, udzieloną na pytanie „czy osoba A zna osobę fi”, jedna z tych dwóch osób nie może być idolem w towarzystwie. Na podstawie tego wniosku łatwo jest rozwiązać następujące zadanie: Zadanie 3.3. Zaproponuj, w jaki sposób za pomocą ciągu n - 1 pytań w postaci „czy osoba A zna osobę fi”, można wśród n osób wskazać kandydata na idola, czyli wyeliminować n -1 osób jako ewentualnych kandydatów na idola. ■ 22

Po tym postępowaniu, w którym za pomocą n -1 pytań eliminujemy kandy­ datów i redukujemy ich liczbę do jednego, musimy sprawdzić jedynie, czy nie wyeliminowana osoba jest rzeczywiście idolem. Jak to zrobić, jest treścią na­ stępnego zadania. Zadanie 3.4. Przypuśćmy, że po wykonaniu zad. 3.3, osoba X pozostała jako kandydat na idola. Ile pytań w postaci „czy osobami zna osobę 5 ” należy zadać i którym osobom, aby się przekonać, że X jest rzeczywiście idolem? ■ Wyprowadziliśmy już w ten sposób pełną metodę służącą do wykrywania, czy w towarzystwie znajduje się idol. Podaj teraz szczegółowy opis tej metody. Zadanie 3.5. Opisz w postaci listy kroków algorytm otrzymany w dwóch po­ przednich zadaniach. Poprzedź go specyfikacją problemu, który ten algorytm rozwiązuje. Podaj ten opis w takiej postaci, jakby to rzeczywiście miało być wy­ krywaniem idola w jakimś towarzystwie. ■ Zadanie 3.6. Ile razy w algorytmie, podanym przez Ciebie w rozwiązaniu zad. 3.5, jest zadawane pytanie „czy osoba A zna osobę B ”, gdy w towarzystwie jest n osób? ■ Jako odpowiedź w ostatnim zadaniu powinieneś otrzymać liczbę 3 (n -l). Dokładnie tyle pytań należy zadać, by przekonać się, że w towarzystwie istnieje idol. Jeśli zadałeś więcej pytań, to albo dokładniej sprawdź swoje obliczenia, albo jeszcze raz sformułuj algorytm na podstawie rozwiązań zadań 3.3 i 3.4. Jeśli kandydat na idola nie jest nim rzeczywiście, to w wyprowa­ dzonym algorytmie często okazuje się to prędzej niż po zadaniu wszystkich pytań. A teraz porównamy otrzymany algorytm z metodą, w której należałoby spraw­ dzić znajomość każdej osoby z każdą. Zadanie 3.7. Ile jest różnych możliwych pytań w postaci „czy osoba A zna osobę B”, które można zadać w towarzystwie złożonym z n osób? Wskazówka. Uwzględnij uwagę podaną na początku tego punktu, że relacja znajomości nie jest relacją zwrotną. ■ W pytaniu „czy osoba A zna osobę B ” obie osoby mogą być dowolnymi osobami z towarzystwa, czyli osoba A może wystąpić w pytaniu z każdą inną osobą B. Zatem, osoba A występuje na pierwszej pozycji w «-1 pytaniach, a ponieważ wszystkich osób jest n, więc całkowita liczba wszystkich możliwych pytań wynosi n(n - 1). Zwróć tutaj uwagę, że pracochłonność algorytmu, otrzymanego w zad. 3.5, wynosi co najwyżej 3 (« -l) pytań, by wykryć, czy w towarzystwie jest idol, chociaż liczba wszystkich możliwych do zadania pytań jest znacznie, znacznie większa i wynosi n(n - 1). 23

^£*5 Zadanie 3.8. Algorytm, który w zad. 3.5 podałeś w postaci listy kroków, ^ przedstaw teraz w języku Pascal, w postaci funkcji logicznej (Boolow- skiej) Idol, która przyjmuje wartość true, gdy w badanym towarzystwie znajduje się idol, i false — gdy go nie ma. Przyjmij, że relacja znajomości jest dana w tablicy (macierzy) Zna o wymiarach n na n,w której element o indek­ sach i oraz j ma wartość true, gdy osoba i zna osobę j, oraz false, gdy osoba i nie zna osoby j. (Wartości elementów na przekątnej w tej tablicy nie mają znaczenia dla naszych rozważań.) Zatem w programie głównym powinna się znaleźć definicja typu danych, na przykład: type TablicaB=array[1..n;1..n] of Boolean; Proponujemy następujący nagłówek funkcji Idol: function Idol(n:integer; Zna:TablicaB; var k :integer):Boolean; w którym parametry mają następujące znaczenie: n — liczba osób w towarzy­ stwie, Zna — tablica logiczna zawierająca relację znajomości, k — numer osoby na przyjęciu, która została zidentyfikowana jako idol. O tym, czy w towa­ rzystwie znajduje się idol, świadczy wartość funkcji Idol — wynosi ona true, gdy jest idol, i false, w przeciwnym razie. Jeśli w towarzystwie nie ma idola, to wartość parametru k nie ma znaczenia. ■ r p j Zadanie 3.9. Pytaniu „czy osoba A zna osobę B” odpowiada w proce- durzę Idol sprawdzenie, czy element tablicy Zna o indeksach odpo­ wiadających osobom A i B ma wartość true. Oblicz, ile razy w Twojej proce­ durze jest sprawdzany ten warunek — powinno to być co najwyżej 3(n -1 ) razy. Jeśli jest inaczej, to sprawdź swoją implementację algorytmu, który w zad. 3.5 działał zgodnie z naszymi oczekiwaniami, czyli miał wykonywać co najwyżej 3(n -1 ) takich porównań. ■ fJ ^ l Zadanie 3.10. Napisz odpowiedni program z procedurą Idol. Wykonaj obliczenia testowe na danych o towarzystwie, w którym jest idol i w którym nie ma idola. Sprawdź, czy Twój program daje poprawne wyniki. ■ 3.2. Wybory lidera Pojęcia: • iteracja, • porządkowanie kubełkowe, • pracochłonność algorytmu. Zajmiemy się teraz wyznaczaniem w to­ warzystwie lidera. To zadanie, w ogólnej postaci, jest szczegółowo omówione w książ­ ce Algorytmy (p. 5.6.1), wracamy tutaj jed­ nak do niego, by na początku rozważyć w formie gry-zabawy jego szczególną po- 24

stać i na podstawie wspólnego działania wyprowadzić rozwiązanie, wyłaniające lidera w grupie osób (gdy tylko istnieje). Przypomnijmy, w zbiorze, w którym elementy mogą występować wielokrotnie (taki zbiór nazywa się czasem multizbiorem), liderem jest taki element, którego liczebność w tym zbiorze jest większa od połowy liczby wszystkich elementów. A więc, jeśli zbiór ma np. 10 lub 11 elementów, to element będący w nim liderem musi się powtarzać co najmniej 6 razy, a jeśli ma 12 elementów — to 7 razy. Zbiór w tym zadaniu może być złożony z osób, liczb, przedmiotów itp. Wybór najbardziej popularnej osoby Na początku zajmiemy się znajdowaniem lidera w dosłownym sensie. Załóżmy więc, że naszą uwagę w klasie ograniczamy do jakiejś wybranej sfery działal­ ności lub zainteresowań i chcemy się przekonać, czy w naszej opinii klasowej istnieje w tej dziedzinie osoba, którą można by uznać za lidera — musi to być osoba, która jest obierana przez więcej niż połowę wszystkich uczniów. Przypuśćmy na przykład, że chcemy się przekonać, czy w naszej klasowej opinii istnieje autor współczesnej polskiej poezji śpiewanej, którego moglibyśmy uznać za lidera — najbardziej popularnego autora. Starając się wyłonić taką osobę, usłyszymy zapewne wiele różnych nazwisk, a wśród nich: Długosz, Kaczmarski, Młynarski, Osiecka, Stachura i inne. Aby ograniczyć „rozrzut” kandydatów na lidera, wyłońmy najpierw listę kilku, najpoważniejszych kandydatów na lidera. W tym celu niech każdy z uczniów wypisze na kartce nie więcej niż trzy nazwiska osób, które według niego są najlepszymi kandydatami na lidera poezji śpiewanej. Następnie, niech jedna osoba zbierze kartki i sporządzi ranking osób, które znalazły się na kartkach. Do dalszego postępowania kwalifikujemy trzy osoby, które znalazły się na trzech najwyższych miejscach w tym rankingu. Następnym etapem są wybory: na tablicy wypisujemy tych trzech kandydatów i każdy ma prawo wpi­ sać na swojej kartce do głosowania tylko jedno nazwisko spośród wypisanych na tablicy. Dalszy etap, to obliczenie wyników wyborów i stwierdzenie, czy któregoś z kan­ dydatów można rzeczywiście uznać w opinii całej klasy za lidera współczesnej polskiej poezji śpiewanej — musi on uzyskać więcej niż połowę oddanych głosów. Postępowanie opisane obok jest stosowa­ ne w wielu sytuacjach. Najlepszym przy­ kładem są wybory liderów politycznych w partiach lub w instytucjach ustawo­ dawczych lub rządowych. Na ogół, różne partie i ugrupowania mają najpierw pra­ wo zgłosić kandydatów, a następnie od­ bywają się wybory. W niektórych gre­ miach obowiązuje zasada, że kandydat na dane stanowisko musi uzyskać więcej niż połowę głosów, a zatem w naszym sensie można uznać go za lidera. Opisa­ ne obok algorytmy mogą więc mieć prak­ tyczne zastosowanie. 25

Zadanie 3.11. Jaki przychodzi Ci do głowy najprostszy sposób przekonania się, czy przeprowadzone głosowanie wyłoniło lidera? ■ Zapewne postąpisz tak, jak najczęściej robi się w takich sytuacjach. Na po­ czątku oznaczysz miejsca na stosy kartek nazwiskami kandydatów, a następnie przeglądając kolejne kartki z głosowania, będziesz je odkładał na odpowiednie stosy. Na końcu, by sprawdzić, czy został wyłoniony lider, weźmiesz najliczniejszy ze stosów i sprawdzisz, czy zawiera on więcej niż połowę kartek. Jeśli tak, to oso­ bę w ten sposób wyłonioną można uznać za lidera w opinii klasowej. Tak na ogół przebiega liczenie głosów w wyborach, w których wyborcy składają swoje głosy, wypisując nazwisko jednego kandydata na kartce. Nawet nie zdajesz sobie sprawy, że po­ służyłeś się obok metodą porządkowania, która nazywa się porządkowaniem ku­ bełkowym (lub koszykowym) — jej na­ zwa bierze się stąd, że zamiast na stosy, kartki są wrzucane do kubełków. Ścisły opis algorytmu porządkowania kubełko­ wego znajduje się w książce Algorytmy (p. 6.3.1). Zadanie 3.12. Sporządź w postaci listy ścisły opis kroków naszkicowanego algorytmu znajdowania lidera. ■ U Zadanie 3.13. Sporządź opis algorytmu podanego w zad. 3.12 w postaci procedury w języku Pascal. Zanim napiszesz procedurę zastanów się nad doborem struktur danych, najwłaściwszych dla operacji wykonywanych w algorytmie. Przede wszystkim zadecyduj, w jaki sposób mają być pamiętane informacje zapisane na kartkach — czy konieczne jest pamiętanie wszystkich poszczególnych kartek, a może wystarczy pamiętać tylko ich liczbę? ■ Znajdowanie lidera w zbiorze Teraz zajmiemy się podaniem algorytmu, służącego do znajdowania lidera w ogólnej sytuacji. Znajdowanie lidera Dane: Zbiór A'złożony z n elementów {xl,x2,—,xn}. Wynik: Lider / w zbiorze X lub informacja, że X nie zawiera lidera. Załóżmy, że elementami zbioru X są liczby — nie umniejsza to ogólności naszych rozważań, gdyż zawsze można elementom zbioru X przyporządkować liczby: różnym elementom — różne liczby. Na przykład, zbiór {1, 2, 1, 3,1, 4} nie zawiera lidera, bo liczebność najliczniej występującej w nim liczby 1 wynosi 26

tylko nl2 = 6/2 = 3, ale zbiory {1, 2,1, 3,1, 1} i {1, 2,1, 3,1, 4,1} mają lidera — jest nim liczba 1. W ostatnim zbiorze, częstość lidera wynosi 4, a nl2 = 7/2 = = 3.5. Zadanie 3.14. Jaka jest różnica między rozważanym wcześniej zadaniem znale­ zienia lidera wśród autorów poezji śpiewanej, a zadaniem o powyższej specyfi­ kacji? ■ Powinieneś tę różnicę natychmiast zauważyć: we wcześniejszym zadaniu, na kartkach z głosowania mogły się znaleźć nazwiska osób ustalone przed przystąpieniem do głosowania, a więc przed tworzeniem zbioru, w którym szukaliśmy lidera. Tutaj natomiast, o zbiorze X wiemy jedynie, że zawiera n liczb, ale nie wiemy, jakie to mogą być liczby i ile jest w nim różnych liczb. Algorytm, który jest odpowiedni do takiej sytuacji, jest oparty na następującej własności zbioru z liderem: Jeśli zbiór X zawiera lidera, a * iy są jego różnymi elementami, to zbiór T = JT-{jr,y}, powstały przez usunięcie tych elementów ze zbioru X, również zawiera lidera. Uzasadnimy poprawność takiego wnioskowania. Uzasadnienie. Przyjmijmy, że zbiór X, złożony z n elementów, zawiera lidera i oznaczmy go przez /. Zatem / występuje w zbiorze X więcej niż nl2 razy. Oznaczmy przez c liczebność l w X, czyli mamy c > nl2. Jeśli żaden z elementów * i y nie jest liderem /, to element / pozostaje liderem zbioru 7, gdyż ze zbioru X nie ubył żaden element równy l, a liczba elementów w zbiorze Y zmniejszyła się o dwa w porównaniu ze zbiorem X. A więc, jeśli było c > nl2, to tym bardziej jest c > (n-2)12. Jeśli natomiast jeden z elementów* iy jest równy / (tylko jeden z nich może być równy /, gdyż są to różne elementy), powiedzmy* = /, to liczebność / w zbiorze Y wynosi teraz c-1. Odejmijmy 1 od obu stron nierówności c > n l2. Wtedy otrzymamy c-1 > nl2-1 i po sprowadzeniu prawej strony do wspólnego mia­ nownika dostajemy c-1 > («—2)/2. Oznacza to, że liczebność elementu l w zbiorze Y jest większa od połowy liczby elementów w zbiorze Y, czyli l jest również liderem zbioru Y. To kończy uzasadnienie słuszności własności zbioru z liderem. ■ Zadanie 3.15. Opisana własność zbioru X z liderem nie przenosi się w drugą stronę, to znaczy usunięcie dwóch różnych elementów * i y ze zbioru X, który nie zawiera lidera, może dać zbiór Y, który zawiera lidera. Postaraj się podać przykład, potwierdzający to stwierdzenie. Wskazówka. Jeśli masz kłopot z podaniem odpowiedniego przykładu, to zajrzyj na str. 82 w książce Algorytmy. m 27