Nauka algorytmu

Aby zająć się pisaniem programów, należy nabyć pewnych umiejętności, do których na pewno trzeba zaliczyć:

• zdolność logicznego myślenia,
• jasnego formułowania problemów do rozwiązania,
• podawanie czytelnych i jednoznacznych odpowiedzi.

Chęć nabycia tych umiejętności zmusza do tego, aby starannie wykonywać swoją pracę. Widać z tego, że pewne nawyki są przydatne nie tylko w informatyce, ale również w naszym codziennym życiu. Jeżeli potrafimy rozwiązywać problemy za pomocą komputera, wykorzystując języki programowania, to znaczy, że programujemy.
Zanim jednak poznamy konkretny język programowania i zaczniemy pisać jakikolwiek program, należy nauczyć się posługiwania się algorytmami. Komputer jest tylko maszyną, którą wykorzystujemy do własnych celów, bo komputer nie myśli, lecz tylko wykonuje polecenia. Dlatego krok po kroku trzeba mu podać czynności, jakie ma wykonać.

Co to jest algorytm? Wydaje się, że najbardziej przystępną definicją będzie określenie algorytmu jako przepisu prowadzącego do rozwiązania zadania, problemu. W przepisie tym podaje się opis czynności, które trzeba wykonać, oraz dane, dla których algorytm będzie określony.

Co w takim przepisie może się znaleźć? Może być to np. przypisanie zmiennej określonej wartości (np. za x podstaw 3), wyświetlenie w danym momencie wyniku obliczeń, pobranie danych z dostępnej bazy danych. Mówimy, że podajemy instrukcje lub że będzie wykonana operacja. Dane (stałe, zmienne, parametry), które są przetwarzane za pomocą instrukcji, nazywamy obiektami. Wyróżnia się wiele obiektów - mogą to być liczby naturalne, rzeczywiste, znaki, słowa. Rozwiązanie dowolnego problemu polega na wykonaniu w określonej kolejności akcji na obiektach. Zbiór tych akcji nazywamy algorytmem.

Jakie mogą być rodzaje algorytmów?

1. iteracyjne - rodzaj algorytmu i programu, w których wielokrotnie wykonuje się pewne instrukcje, dopóki nie zostanie spełniony określony warunek,
2. rekurencyjne - takie procedury, które w swojej definicji posiadają wywołanie samej siebie,
3. sekwencyjne - instrukcje wykonywane są w porządku, w jakim zostały wprowadzone.

W jaki sposób można przedstawić algorytm? Pierwszy i najprostszy to opis słowny, np. po lekcjach pójdę do kiosku i kupię gazetę. Innymi przykładami mogą być: podyktowanie przez telefon przepisu na zaparzenie herbaty czy wyjaśnianie koledze, jak należy rozwiązać zadanie z matematyki. Przykładów takich zachowań, kiedy widzimy, że występuje jakaś kolejność przewidywalnych działań, można podawać bardzo wiele. To są przykłady opisów algorytmicznych.
Inny sposób to zapis algorytmu za pomocą schematu blokowego. Aby zapisać algorytm za pomocą takiego schematu, trzeba poznać stosowane symbole i ich znaczenie. Będziemy używać tzw. skrzynki - graficznego sposobu przedstawienia czynności wykonywanych przez komputer. Skrzynki te łączone są za pomocą strzałek. W ten sposób pokazujemy kolejność wykonywania akcji.

	Skrzynki START i STOP wskazują początek i koniec każdego algorytmu. Ze skrzynki START wychodzi tylko jedna droga, do skrzynki STOP wchodzi, co najmniej jedno połączenie.
	W skrzynce instrukcyjnej umieszcza się po-lecenia do wykonania (instrukcje) - podstawienie, obliczenie, wprowadzenie wartości.
	W skrzynce warunkowej umieszcza się warunek, który decyduje o wyborze dalszej drogi postępowania. Ze skrzynki wychodzą dwa połączenia: TAK (wybierane, gdy warunek jest spełniony), NIE, (gdy warunek nie jest spełniony).
	W skrzynce wejścia / wyjścia umieszcza się wprowadzane dane lub wyprowadzane wyniki. Ze skrzynki wychodzi tylko jedno połączenie.

Aby dobrze zrozumieć algorytmy, należy samemu spróbować go ułożyć. Będzie ciekawiej, gdy zaczniemy zadawać pytania i algorytm rozbudowywać.
Zacznijmy od najprostszego, książkowego algorytmu: chcę wyjść z domu i w zależności od pogody wezmę parasol lub nie.
Opis słowny: przed wyjściem z domu sprawdzam, jaka jest pogoda; jeżeli pada, zabieram parasol i wychodzę, jeśli nie pada, wychodzę. W tak prostym przypadku spotykamy się z sytuacją, w której występuje sprawdzenie warunku. Słowem, które będzie nas informować, że należy wprowadzić sprawdzenie warunku, jest słowo "jeśli".

Opis za pomocą schematu blokowego:

W algorytmie tym wykorzystujemy skrzynkę warunkową, ponieważ mamy do czynienia z sytuacją, gdy tok dalszego postępowania zależy od dokonanego wyboru (dokładnie: zależy od pogody).

Drugi przykład prostego algorytmu: oblicz objętość prostopadłościanu o krawędziach długości: 3cm·5cm·8cm.
Słowny opis postępowania: aby obliczyć objętość, należy pomnożyć przez siebie długości trzech krawędzi wychodzących z jednego wierzchołka; długości muszą mieć jednakowe miano.

Z podanej treści zadania wynika, że mamy dane długości potrzebnych krawędzi w jednakowych jednostkach. Zadanie to nie sprawi nikomu żadnej trudności. Warto jednak pomyśleć, czy nie można byłoby ułożyć takiego algorytmu, za pomocą, którego obliczymy objętość każdego prostopadłościanu.

Opis słowny:

START - podaj długość pierwszej krawędzi; a:= - podaj długość drugiej krawędzi; b:= - podaj długość trzeciej krawędzi; c:= - wykonaj obliczenie V:= a*b*c - podaj wynik; V:= STOP

W przykładzie tym wykonywane czynności następują jedna po drugiej. Instrukcje wykonywane są w takim porządku, w jakim zostały zapisane. Jest to przykład algorytmu zapisanego w postaci sekwencji.

Zad. domowe:
1. Zapisz powyższy algorytm za pomocą schematu blokowego.
2. Jakimi cechami musi charakteryzować się dobry algorytm?

Spotykamy się często z takim sytuacjami, że musimy wykonywać pewną czynność aż do momentu, gdy odniesiemy sukces, np. zrób dziesięć pompek; będziesz tak długo czytać wiersz, aż nauczysz się go na pamięć; dopóki będziesz siedzieć cicho, nie zapytam cię. Z tego wynika, że możemy spotkać się z trzema sytuacjami:, gdy musimy wykonać czynność bądź zadaną ilość razy, bądź do momentu spełnienia warunku.
Wykonaj instrukcję r razy, np. przeczytaj wiersz trzy razy.

Opis słowny:

START Przeczytaj wiersz pierwszy raz. Przeczytaj wiersz drugi raz. Przeczytaj wiersz trzeci raz. STOP

W tym przypadku mamy algorytm zapisany w postaci sekwencji.

Schemat blokowy:

Można też wykonać to inaczej:

Opis słowny:

START Przeczytaj wiersz trzy razy. Czytaj wiersz. Czy przeczytałeś wiersz trzy razy? a) jeśli tak, przejdź do kroku 4, b) jeśli nie, przejdź do kroku 2. Przeczytałeś wiersz trzy razy. STOP

Występuje tutaj sprawdzenie warunku. Gdy warunek nie jest spełniony, czynność trzeba wy-konać jeszcze raz.

Schemat blokowy:

Powtarzaj wykonanie instrukcji aż do spełnienia warunku.

Przykładem takiego algorytmu może być zmienione poprzednie zadanie: Czytaj wiersz tak długo, aż nauczysz się go na pamięć.

Opis słowny:

Opis słowny: START Przeczytaj wiersz. Czy umiesz wiersz na pamięć? a) jeśli tak, przejdź do kroku 3, b) jeśli nie, przejdź do kroku 1. Gratulacje, nauczyłeś się wiersza na pamięć! STOP

Wykonywanie polecenia "przeczytaj wiersz" trwa tak długo, aż nauczysz się go na pamięć.

Schemat blokowy:

Dopóki warunek nie jest spełniony, wykonuj podane instrukcje.
Są to polecenia typu: dopóki jest zimno, noś czapkę; dopóki nie poprawisz ocen, nie pójdziesz grać w piłkę; dopóki nie zdasz egzaminu, nie będziesz jeździć samochodem itd.

Dopóki jest czerwone światło dla pieszych, stój i czekaj.

Opis słowny: START Stój. Czy świeci się czerwone światło na przejściu dla pieszych? a) jeśli tak, przejdź do kroku 1, b) jeśli nie, przejdź do kroku 2. Możesz przejść przez ulicę, zachowując ostrożność. STOP

Stój tak długo, aż nie zapali się zielone światło! Warunkiem, który musi zostać spełniony, jest zmiana światła.

Schemat blokowy:

Przykładów tego rodzaju algorytmów jest bardzo wiele. W zasadzie większość czynności można opisać algorytmem. Będą one mniej lub bardzie rozbudowane, a zależy to od tego, do jakiego stopnia można przewidzieć zachowanie lub wykonywanie czynności w różnych sytuacjach. Algorytmami iteracyjnymi będą te, w których stosujemy pętlę, tzn. zapis, w którym nakażemy wykonanie pewnej akcji jeszcze raz po sprawdzeniu warunku, który trzeba spełnić.

Zad. domowe:
Twoim zadaniem będzie znalezienie przykładów zachowań algorytmicznych w życiu codziennym, które można zapisać jako iteracje.

1. Zbuduj algorytm, za pomocą, którego można obliczyć drugą i trzecią potęgę danej liczby.

BUDOWA ALGORYTMU: START - podaj liczbę a, - oblicz kwadrat liczby a, - oblicz sześcian liczby a, - podaj wartość kwadratu liczby a, - podaj sześcian liczby a. STOP

2. Zbuduj algorytm służący do rozwiązania równania typu ax + b = 0

BUDOWA ALGORYTMU: START - podaj wartość współczynnika a, - podaj wartość współczynnika b, - jeżeli a = 0, to sprawdź b, - jeżeli b = 0, to napisz, że jest to równanie tożsamościowe (nieskończenie wiele rozwiązań), - jeżeli b<>0, to napisz, że jest to równanie sprzeczne (nie ma rozwiązań), - jeżeli a<>0, to oblicz x - napisz rozwiązanie równania x:= STOP

Problemy do samodzielnego rozwiązania:

1. Na podstawie zadania 1 zbuduj algorytm obliczający kolejne potęgi podanej liczby (np. czwartą i piątą).
2. Zbuduj algorytm obliczający pierwiastek kwadratowy i sześcienny danej liczby.
3. Zapisz algorytm opisujący postępowanie przy poszukiwaniu pomyślanej liczby (z podanego zakresu w możliwie najmniejszej liczbie prób).
4. Zapisz algorytm rozwiązywania równania typu ax + b = c
5. Zapisz algorytm obliczający sumę pięciu liczb.
6. Zapisz algorytm obliczania średniej z pięciu liczb.
7. Zapisz algorytm obliczania średniej ocen ze świadectwa szkolnego.
8. Dane są długości trzech odcinków. Zbadaj, czy można zbudować z nich trójkąt.
9. Sprawdź, czy trójkąt o bokach a, b, c jest trójkątem prostokątnym.
10. Podaj algorytm obliczania pola figur płaskich:
    a) kwadratu,
    b) prostokąta,
    c) dowolnego trójkąta,
    d) trójkąta równobocznego,
    e) trapezu,
    f) rombu,
    g) równoległoboku.
11. Podaj algorytm obliczający pole powierzchni całkowitej i objętość:
    a) sześcianu,
    b) graniastosłupa,
    c) walca.

BUDOWA ALGORYTMU: START Zmierz masę ciała stałego m:= Zmierz za pomocą menzurki objętość ciałaV:= Oblicz gęstość ciała Podaj gęstość ciała (g/cm3) r:= STOP

Przedstaw za pomocą algorytmu sposób na obliczanie gęstości ciała stałego.

Zapisz za pomocą algorytmu sposób na rozpoznawanie rodzaju ruchu ciała ze względu na zmianę prędkości.

START

1. Podaj prędkość początkową v1:=
2. Podaj prędkość końcową v2:=
3. Oblicz przyrost prędkości
4. Czy ?
   a) jeśli tak, pisz: ruch jednostajny,
   b) jeśli nie, sprawdź, czy

i. jeśli tak, pisz: ruch jednostajnie przyspieszony,

ii. jeśli nie, pisz: ruch jednostajnie opóźniony.

STOP

Zapisz powyższy algorytm za pomocą schematu blokowego.
Zadania do samodzielnego rozwiązania:

1. Zapisz za pomocą algorytmu sposób obliczania ciężaru ciała na:
   a) Ziemi,
   b) Księżycu,
   c) Marsie,
   d) Wenus.
2. Zapisz za pomocą algorytmu sposób obliczania przyspieszenia ciała, gdy znamy przyrost prędkości ciała oraz czas, w którym ten przyrost nastąpił.
3. Zapisz algorytm obliczania drogi w ruchu:
   a) jednostajnym po linii prostej,
   b) jednostajnym po okręgu,
   c) jednostajnie przyspieszonym.
4. Zapisz za pomocą algorytmu sposób obliczania przyspieszenia ciała, gdy znamy wartość siły wypadkowej działającej na ciało oraz masę tego ciała. (II zasada dynami-ki).
5. Zapisz algorytm obliczania:
   a) pracy,
   b) mocy,
   c) energii potencjalnej ciężkości,
   d) energii kinetycznej ciała,
   e) oporu elektrycznego (prawo Ohma).
6. Zapisz algorytm opisujący własności obrazu w zależności od długości ogniskowej i odległości ciała od soczewki lub zwierciadła dla:
   a) zwierciadeł płaskich,
   b) zwierciadeł wklęsłych,
   c) zwierciadeł wypukłych,
   d) soczewek skupiających,
   e) soczewek rozpraszających.