Czarna robota, czyli po co nam te zabawy

W tym rozdziale przedstawiamy wykaz zagadnień algorytmicznych, którymi będziemy zajmować się w ramach projektów. Opisujemy specyfikacje poszczególnych problemów, podajemy też słowny opis wybranych metod ich rozwiązania, ale nie pokazujemy gotowych działających programów. Ich samodzielne napisanie pozostawiamy jako ćwiczenie.

Biometryczny Indeks Masy Ciała (BMI)

Mając dany wzrost i masę ciała osoby, obliczamy jej biometryczny indeks masy. Porównując go z wartościami progowymi podejmujemy decyzję, czy wskaźnik mieści się w granicach normy, czy też jest wyższy lub niższy niż norma. Program powiadamia użytkownika o wyniku tego porównania.

Program, mając do dyspozycji imię użytkownika, formułuje komunikat uwzględniając rodzaj gramatyczny odpowiadający (prawdopodobnej) płci respondenta.

Trójkąty

Mając dane trzy liczby dodatnie badamy, czy mogą one być długościami boków trójkąta. Jeżeli tak, to obliczamy pole tego trójkąta oraz miary jego kątów; komunikat końcowy klasyfikuje trójkąt jako ostro- prosto- lub rozwartokątny.

Podobne obliczenia przeprowadzamy dla trójkąta określonego na płaszczyźnie z układem współrzędnych przez podanie współrzędnych wierzchołków. Do rozważenia jest także wariant w przestrzeni trójwymiarowej.

Prostokąty kanonicznie zorientowane

Na płaszczyźnie z układem współrzędnych rozpatrujemy prostokąty, których krawędzie są równoległe do osi. Takie prostokąty są w pełni określone albo przez zadanie współrzędnych naprzeciwległych wierzchołków, albo przez zadanie jednego określonego wierzchołka oraz wymiarów: szerokości i wysokości.

Przysłanianie prostokątów

Sprawdzić, czy dwa prostokąty mają część wspólną. Odpowiedź jest wartością typu logicznego.

Wyznaczanie części wspólnej dwóch prostokątów

Wyznaczyć część wspólną dwóch danych prostokątów. Dana wynikowa ma opisywać prostokąt w taki sam sposób, jak każda z danych wejściowych.

Sumowanie i zliczanie elementów ciągu wejściowego

Czytamy ciąg elementów (np. liczb) o nieznanej długości. Dla każdego elementu z osobna sprawdzamy spełnienie ustalonego warunku. Pod koniec czytania mamy odpowiedzieć na pytania: z ilu elementów składał się ten ciąg? ile elementów spełniało sprawdzany warunek?

W przypadku dotyczącym danych liczbowych może też paść pytanie o sumę elementów spełniających warunek.

Wielokąty

Uogólniamy nasze poprzednie struktury danych tak, by były w stanie reprezentować nie tylko trójkąt, ale dowolny wielokąt na płaszczyźnie. W strukturach danych niezbędne będzie użycie list numerowanych, a w algorytmach — iteracji.

Szczegóły niezbędne do dopracowania pomysłu i wskazówki dotyczące implementacji zostaną podane podczas zajęć.

Obwód figury

Opracuj schemat obliczania obwodu wielokąta. Zapisz go w postaci funkcji.

Pole powierzchni

Opracuj schemat obliczania pola powierzchni wielokąta (istnieje wiele metod). Zapisz go w postaci funkcji.

Wypukłość

Opracuj schemat rozstrzygania o wypukłości wielokąta. Zapisz go w postaci funkcji.

Pomysł: sprawdź, czy idąc po brzegu figury we wszystkich wierzchołkach skręcasz w tę samą stronę. Do wyznaczenia kierunku skrętu użyj funkcji trygonometrycznych (ściślej: nie potrzebujesz wartości sinusa, tylko znaku sinusa; jest on taki sam, jak znak wyznacznika definiującego iloczyn wektorowy na płaszczyźnie).

Średnica

Jak znaleźć średnicę wielokąta, czyli największą odległość między jego wierzchołkami?

Położenie środka masy

Wyznacz położenie środka masy wielokąta.

Położenie punktu względem obszaru

Mając dany punkt i wielokąt rozstrzygnij, czy punkt leży w jego obrębie. Istnieje kilka metod.

Wyszukiwanie danych

Filtrowanie wierszy pliku

Na postawie ciągu obiektów zapisanych w pliku (jeden obiekt w jednym wierszu) zbuduj plik wynikowy składający się z tych obiektów, które spełniają zadany warunek.

Przykład: lista mieszkańców danej miejscowości.

Filtrowanie listy

To samo zadanie można sformułować dla listy numerowanej: mając daną listę obiektów zbudować listę złożoną z tych elementów, które spełniają zadany warunek.

Wariant: zbudować listę numerów, pod jakimi w danej liście przechowywane są elementy spełniające dany warunek.

Wyszukiwanie w liście metodą liniową

Znaleźć numer pierwszego w kolejności elementu listy spełniającego dany warunek. Podać wartość tego elementu korzystając ze znalezionego numeru.

Przykład: poszukiwanie danych adresowych na podstawie numeru telefonu. Ile pracy potrzeba, by otrzymać wynik przeszukania n-elementowego spisu? Co się stanie, kiedy dana nie występuje na liście?

Znaleźć numer następnego elementu spełniającego ten sam warunek (tj. pierwszego w nieprzeszukanym odcinku listy).

Transformacje ciągów danych

Mając dany ciąg jednakowo zbudowanych obiektów ułożonych w listę oraz funkcję działającą na pojedynczym obiekcie tego typu, zbudować ciąg wartości funkcji odpowiadających elementom listy wejściowej.

Wariant: lista wynikowa składa się z par postaci [obiekt, f(obiekt)].

Przykłady: obliczanie wieku na podstawie daty urodzenia; zamiana jednostek w ciągu danych pomiarowych, transformacja współrzędnych ciągu punktów na płaszczyźnie; generator korespondencji seryjnej.

Tablicowanie funkcji

Mając dane: algorytm obliczania funkcji jednej zmiennej oraz przedział zawarty w dziedzinie tej funkcji skonstruować listę współrzędnych punktów wykresu tej funkcji „dobrze” pokrywających ten przedział.

Funkcja jako podprogram

1. mając instrukcję obliczania f i wartość argumentu x umiemy obliczyć f(x)
2. co z tego wynika? otrzymanie tylko skończenie wielu wartości w skończonym czasie; niezdolność do analizy właściwości funkcji, …
3. co to znaczy „dobrze” pokryć przedział? (kontrola błędu? wizualne dopasowanie linii łamanej do wykresu? …)

Stały krok

Zakładamy, że odcięte punktów wykresu będą tworzyć ciąg arytmetyczny. Pierwszy punkt będzie odpowiadał początkowi przedziału, ostatni — końcowi przedziału, zaś liczba kroków będzie parametrem wejściowym.

Problem: kiedy stały krok jest niedobry? (patrz zestaw ćwiczeń).

Pętla for

Pułapka związana z dokładnością arytmetyki zmiennopozycyjnej: w wyniku sukcesywnego dodawania ostatni punkt może mieć współrzędną nie należącą do zadanego przedziału, co powoduje kłopoty w przypadku, kiedy skraj przedziału jest skrajem dziedziny funkcji. Możliwa jest też sytuacja, kiedy ostatni punkt leży w pobliżu krańca przedziału, ale w jego wnętrzu — co wtedy?

Pętla while

Pułapka związana z dokładnością arytmetyki zmiennopozycyjnej: w wyniku sukcesywnego dodawania błędy kumulują się. Współrzędna x-owa ostatniego punktu może nieco różnić się od końca przedziału. Jeżeli będzie za duża, to nie uwzględnimy ostatniego węzła. Trzeba więc mądrze określić kryterium zakończenia iteracji; naiwny warunek x < b nie wystarcza.

Tablicowanie jako podprogram

Co jest dane?

przedział na osi liczbowej (czyli dwie liczby), liczba kroków, tablicowana funkcja

Jaki wobec tego winien być nagłówek podprogramu?

Co jest wynikiem?

tablica współrzędnych

Czy w związku z tym lepiej, żeby podprogram tablicujący był funkcją, czy procedurą?

… czy istnieje jedna odpowiedź? niekoniecznie, ale każda odpowiedź powinna mieć argumentację.

Jeżeli podprogram tablicujący ma być funkcją, to jak zorganizować instrukcję return? (co jest wynikiem procesu tablicowania)

Jeżeli podprogram tablicujący ma być procedurą, to w jakim sensie generuje on wyniki? (jak je wykorzystać w tym samym programie)

Numeryczne rozwiązywanie równań

Funkcja jako podprogram — a gdyby tak odwrócić?

• gdybyśmy umieli przekształcać instrukcje postępowania…
  • y = a⋅x + b ⇒ x = (y−b)/a dla a ≥ 0
  • y = a⋅x² + b ⇒ x = ((y−b)/a)^1/2 dla a ≠ 0 i y ≥ b
  • y = ln(a⋅x + b) ⇒ x = (e^y−b)/a
• …czyli w każdym przypadku inaczej…
• czasami się nie da:
  • y = x + ln(x)/x ⇒ x = ???
• ogólnie tym bardziej się nie da:
  • y = f(x) ⇒ x = ???
• Wniosek: mając instrukcję obliczania f i wartość y nie umiemy znaleźć x : f(x)=y

Co to znaczy „rozwiązywać równanie w sposób przybliżony”?

• Nie ma szans na uzyskania dokładnego rozwiązania
• Akceptowalną wartość błędu trzeba sobie założyć
• Iteracje sterowane uzyskanym poziomem błędu
• W każdym kroku nowe przybliżenie…
• …miejmy nadzieję, że lepsze niż poprzednie

Analiza wyników tablicowania funkcji ciągłej

• Po czym poznać, że wykres funkcji przecina oś OX?
  • jeżeli funkcja jest ciągła, to następuje zmiana znaku wartości funkcji
• Jak dokładnie możemy oszacować położenie punktu przecięcia?
  • nie znamy położenia miejsca zerowego
  • znamy węzły po jego obu stronach
  • najlepszy „kandydat”: środek przedziału między węzłami
  • jaki jest błąd takiego przybliżenia?
    • nie większy niż połowa długości przedziału… czyli znamy górne oszacowanie błędu!
• Co się da zrobić, żeby poznać je dokładniej?
  • interpolować?
    • …
  • tablicować w tym podprzedziale
  • na ile nowe przybliżenie jest lepsze od poprzedniego?
• Na ile części dzielić przedział, żeby nie marnować swoich zasobów?
  • na jak najmniejszą liczbę (czyli 2) —
    rysunek
  • po czym zrobić to samo z nieodrzuconym podprzedziałem
• Kiedy skończyć?
  • kiedy błąd stanie się na tyle mały, że jesteśmy w stanie go zaakceptować
  • czyli po ilu cyklach iteracji?

Metoda bisekcji

• Tablicowanie „w głąb” tylko w tym podprzedziale, w którym na pewno istnieje pierwiastek
  • warunek przyjmowania przez funkcję wartości o przeciwnych znakach
  • w każdym kroku wybieramy podprzedział, na którego końcach wartości różnią się znakiem
• Minimalna liczba kroków, tzn. dwa
• Dwukrotne zmniejszenie górnego oszacowania błędu w jednym kroku: gwarantowana zbieżność do prawdziwego rozwiązania!
• Algorytm metody bisekcji
  • Kod źródłowy programu…
• W arkuszu kalkulacyjnym…
  • Tylko raz obliczamy wartość funkcji w każdym kroku
  • Dane wejściowe w ustalonym miejscu; dana wynikowa w ustalonym miejscu
  • Pobieranie danej ze wskazanego wiersza: funkcja index
  • Praktycznie…
    • 

Metoda bisekcji jako podprogram

Przekazywanie funkcji jako argumentu

Program sterowany decyzjami użytkownika

Dopracowanie programu tak, by dało się go używać bez zastanawiania, jaka jest jego wewnętrzna budowa. Z ostatnich przykładów widać potrzebę dokonania takiej unifikacji. Szerzej temat ten zostanie poruszony w podrozdziale 11.1.

Wprowadzanie danych

Jak przekazać z wejścia tekst?

• input()
• czytanie z pliku
• formularz ekranowy (np. easygui)

Jak przekazać z wejścia liczbę? najlepiej dwuetapowo

• tekst = input(komunikat)
• wynik = int(tekst)
• wynik = float(tekst)

choć oba etapy można połączyć w jednej instrukcji złożonej

• wynik = int(input(komunikat))
• wynik = float(input(komunikat))

Konstrukcje int(tekst) oraz float(tekst) dokonują konwersji (zamiany) typu wyrażenia tekst podanego jako argument na odpowiedni typ liczbowy.

Funkcja eval(tekst) oblicza i zwraca wartość dowolnego wyrażenia będącego jej argumentem.

Konstrukcja input(tekst) jest tym samym, co eval(input(tekst)).

Wyprowadzanie wyników

pokazać wyniki (gdzie)? zapisać wyniki (gdzie)? pokazać wykres? zapisać wykres: w jakim formacie? gdzie?

W stronę aplikacji użytkowej

Głównym elementem programu użytkowego jest pętla sterowana decyzjami użytkownika. Odpowiednia funkcja wywoływana wewnątrz tej pętli pozwala na podejmowanie decyzji (np. za pomocą menu). Jedna z dostępnych opcji związana jest z zakończeniem pracy. Poszczególne decyzje obsługiwane są za pomocą osobno zdefiniowanych podprogramów.

Użycie bibliotek zawierających gotowe elementy sterujące interfejsem użytkownika (okna dialogowe, menu, inne).