Wstęp do programowania

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.

Kodowanie

Zapisywanie algorytmu w języku programowania to ''kodowanie''. Istnieje prawdopodobnie kilka tysięcy języków programowania, a kilkadziesiąt z nich zdobyło większą popularność. Zawodowy programista zna zazwyczaj od kilkunastu do kilkudziesięciu języków, zaś w codziennej pracy posługuje się kilkoma. Większość języków jest uniwersalna, tzn. daje się w nich zapisać każdy algorytm, chociaż w niektórych językach pewne algorytmy zapisuje się wygodniej, niż w innych.

Instrukcja warunkowa

W poprzednim rozdziale skonstruowaliśmy algorytm wyznaczający najlżejszy z trzech odważników i opisaliśmy go w sposób sformalizowany w języku polskim

Zmienne

Algorytm B (Babiloński)

Dane są dodatnie liczby Q i e.

Niech p = 1.
Niech s oznacza średnią arytmetyczną liczb p i Q/p.
Jeżeli różnica pomiędzy s i p jest mniejsza od e, zakończ i daj odpowiedź s; w przeciwnym przypadku przyjmij za p wartość s i powtórz począwszy od kroku 2.

Na przykład, gdy weźmiemy Q=2 oraz e=0.001, otrzymamy wynik ~1.414214. Można się domyślać, do czego ten algorytm służy, ale zostawimy to jako przedmiot zadania 2, bo przede wszystkim interesuje nas teraz sam opis algorytmu.

Iteracja I

Zadanie spirala

W prostokątnym układzie współrzędnych dane są dwa punkty, na których rozpięto prostokąt o bokach równoległych do osi. Ze środka układu rysujemy łamaną o kształcie spirali: z wierzchołka (0,0) prowadzimy odcinek o długości 1 na północ (zgodnie z kierunkiem i zwrotem wektora [0,1]), następnie odcinek o długości 2 na wschód (zgodnie z kierunkiem i zwrotem wektora [1,0]), następnie o długości 4 na południe (kierunek i zwrot wektora [0,-1]), następnie o długości 8 na zachód (kierunek i zwrot wektora [-1,0]), potem o długości 16 znów na północ itd., za każdym razem podwajając długość odcinka i zmieniając kierunki zgodnie z ruchem wskazówek zegara. Należy znaleźć pierwszy wierzchołek spirali, który leży poza prostokątem (tzn. poza jego wnętrzem i poza brzegiem).

Iteracja II

Komputerowy skład czytelnych i estetycznych tabel to złożony problem, nad rozwiązaniem którego głowią się twórcy specjalizowanych programów (np. takiego jak LaTeX). Przykładem bardzo prostego zadania pojawiającego się przy okazji składu tabel jest wyznaczenie szerokości komórki tabeli na podstawie zawartej w niej wartości liczbowej. W maksymalnym uproszczeniu, chcielibyśmy dla danej liczby naturalnej obliczyć, ile cyfr zajmie jej reprezentacja dziesiętna.

Zadanie cyfry dzisiętne

Dane: liczba naturalna n.

Wynik: liczba cyfr liczby n w zapisie dziesiętnym.

Dozwolone operacje: porównania, operacje arytmetyczne.

Interesująca nas funkcja powinna dawać m.in. takie wyniki:

cyfryDziesiętne(2009) -> 4
cyfryDziesiętne(15) -> 2
cyfryDziesiętne(7) -> 1
cyfryDziesiętne(0) -> 1

Na pierwszy rzut oka wydaje się, że wystarczy policzyć ile razy daną liczbę da się podzielić przez dziesięć (każde całkowite dzielenie przez dziesięć "przesuwa" cyfry w prawo, gubiąc cyfrę "wypadającą" za przecinek dziesiętny).

Tablice

Pewien restaurator, przyjmując zamówienia na ekskluzywne bankiety, prosił klientów o przysłanie spisu gości z zaznaczeniem, kto ma koło kogo siedzieć. Oto jeden z takich spisów:

Bankiet klubu "Biały Mankiet"