ALGORYTMY

Algorytmem nazywamy skończony ciąg czynności, przekształcający zbiór danych wejściowych na zbiór danych wyjściowych (wyników) . Jest dokładnym przepisem na rozwiązanie problemu lub osiągnięcie jakiegoś celu, w skończonej liczbie kroków.

Algorytmy, które wykonują działania matematyczne na danych liczbowych nazywamy algorytmami numerycznymi.

Etapy rozwiązywania zadań za pomocą komputera:

1. Określenie specyfikacji zadania

1. Dane (dane wejściowe)

2. Wyniki (dane wyjściowe)

2. Zbadanie, czy analizowany problem ma rozwiązanie oraz wybór odpowiedniego algorytmu.

3. Zapisanie algorytmu w wybranej postaci.

4. Przeprowadzenie analizy i dowodu poprawności przedstawionego algorytmu.

5. Wykonanie obliczeń na komputerze.

6. Wykonanie obliczeń na komputerze.

7. Analiza własności wybranego algorytmu.

SPOSOBY ZAPISU ALGORYTMU:

• Opis słowny

• Lista kroków

• Pseudo język/kod

• Schemat blokowy

• Drzewa algorytmu

• Program

ALGORYTMY LINIOWE:

Algorytmy, w których kolejność wykonywania czynności jest zawsze taka sama i niezależnie od wartości danych wejściowych, nazywamy algorytmami liniowymi (sekwencyjnymi).

PRZYKŁADY:

Zadanie:

Oblicz sumę dwóch liczb naturalnych a i b.

SPECYFIKACJA ZADANIA:

Dane wejściowe: a, b ;

Dane wyjściowe: S;

OPIS SŁOWNY:

W programie wczytujemy dwie liczby naturalne a i b. Następnie liczby sumujemy i przypisujemy je sumie S. Następnie program wyświetla liczby.

LISTA KROKÓW:

1. Wczytujemy dwie liczby an turlane a i b;

2. Sumujemy a i b i przypisujemy pod S;

3. Wyświetlamy S;

4. Zakończ algorytm ;

PSEUDO JĘZYK/KOD:

- jest to język, który jest czytelny dla programistów. Ma naleciałości wynikające z języków programowania. Często używa się w im również języka angielskiego lub skrótów.

Start

Naturalne a,b;

Wczytaj a, b;

S=a+b;

Wyświetl S;

Zakończ

SCHEMAT BLOKOWY :

	Początek i koniec algorytmu.
	Blok wejścia i wyjścia (wczytywanie danych lub wprowadzenie wyników)
	Blok operacyjny (wykonywanie działań)
	Blok decyzyjny (konstruowanie warunków i sprawdzenie ich spełnienia)
	Łącznik - n oznacza numer połączenia (stosowany przy przenoszeniu schematu na następną stronę)
	Połączenia

Źródło: http://kasia315.republika.pl/kurs/lekcja2.htm

Strona do tworzenia schematów blokowych:

http://www.algorytm.org/narzedzia/edytor-schematow-blokowych.html

DRZEWA ALGORYTMU:

- sposób często używany do zapisu algorytmów rozgałęzionych.

PROGRAM:

#include <stdio.h>

#include <cstdlib>

int main()

{

int a,b;

scanf("%d",&a);

scanf("%d",&b);

S=a+b;

printf("%d", S);

system("PAUSE");

return 0;

}

ALGORYTMY WARUNKOWE:

Algorytm warunkowy(decyzyjny) to taki, w którym wykonanie instrukcji uzależnione jest od spełnienia lub niespełnienia warunku. W algorytmie tym występuje rozgałęzienie, czyli miejsce w algorytmie, w którym sprawdzany jest warunek i na podstawie wyniku tego sprawdzenia jest podejmowana decyzja, którą drogą mają przebiegać dalsze kroki.

W rzeczywistości, większość algorytmów ma bardziej rozbudowaną strukturę. Często występują w nich instrukcje, których wykonanie uzależnione jest od spełnienia pewnego warunku lub też spełnienie pewnego warunku powoduje wykonanie jednej instrukcji, a niespełnienie go innej. Taką instrukcję nazywamy instrukcją warunkową. Działa ona według jednego z dwóch przedstawionych schematów:

Jeśli spełniony jest warunek W, wykonaj instrukcję A.

Jeśli spełniony jest warunek W, to wykonaj instrukcję A; w przeciwnym razie wykonaj instrukcję B.

Instrukcja A i B opisuje jedną instrukcję lub instrukcję składającą się z ciągu instrukcji wykonywanych sekwencyjnie. Instrukcja warunkowa pozwala dokonać wyboru jednej z dwóch dalszych dróg wykonania algorytmu.

ALGORYTMY ITERACYJNE:

Algorytmy iteracyjne, czyli z pętlą, polegającą na wielokrotnym powtarzaniu instrukcji. Liczba powtórzeń może być z góry określona - tzw. pętla „for”; dana instrukcja jest powtarzana aż do spełnienia jakiegoś określonego warunku - tzw. pętla „do while”; najpierw jest sprawdzany warunek a jego spełnienie umożliwia wykonanie instrukcji - tzw. pętla „while do”).

Iteracja - jest to wielokrotne wykonanie ciągu instrukcji, które w kodzie programu zapisane są tylko raz. Iteracja składa się z trzech elementów:

• bloku instrukcji, które będą powtarzane;

• przynajmniej jednej zmiennej sterującej;

• warunku iteracji, w którym następuje porównanie zmiennej sterującej.

Przykładem iteracji może być obliczenie funkcji sumy ogólnej.

ALGORYTMY REKURENCYJNE:

Algorytm rekurencyjny (recursive algorithm), algorytm, który wywołuje sam siebie do rozwiązania tego samego problemu. Algorytm rekurencyjny jest często realizacją zasady “dziel i zwyciężaj”, która składa się z trzech kroków:

1) “dzielenia”, tj. podziału problemu na podproblemy;

2) rekurencyjnego rozwiązania podproblemów, chyba że można je rozwiązać metodą bezpośrednią - takie postępowanie prowadzi do “zwycięstwa” w sensie czasu rozwiązywania problemu;
3) “połączenia” rozwiązań podproblemów w rozwiązanie całego problemu.

Charakterystyczną cechą funkcji (procedury) rekurencyjnej jest to, że wywołuje ona samą siebie. Drugą cechą rekursji jest jej dziedzina, którą mogą być tylko liczby naturalne.
Najłatwiej zrozumieć mechanizm działania rekursji na przykładzie silni: rekurencyjny wzór na obliczenie n! zapisuje się w ten sposób: n!=n*(n-1)!

Ze wzoru tego wynika, że aby obliczyć np. 4!, należy najpierw obliczyć 3!. Ale żeby obliczyć 3! trzeba obliczyć 2! itd. aż dojdziemy do 0!, które jak wiemy wynosi 1.
Sposób obliczenia 4! wygląda więc następująco:

4!=4*3!=4*3*2!=4*3*2*1!=4*3*2*1*0!=4*3*2*1*1=24

Inne przykłady: sortowanie przez scalanie, algorytm Euklidesa.

Zadania:

1. W przedziale całkowitym <a,b> wyszukaj wszystkie liczby parzyste.

2. W przedziale całkowitym <a,b> wyszukaj wszystkie liczby nieparzyste.

3. W przedziale <a,b> liczb całkowitych wyszukać wszystkie liczby podzielne przez liczbę c.

4. Dla danych dwóch liczb naturalnych a i b znaleźć największą liczbę naturalną c, która dzieli bez reszty liczbę a i dzieli bez reszty liczbę b.

Zadania z olimpiady:

1. Napisz algorytm w postaci schematów blokowych, który przelicza temperatury pomiędzy Celsjuszem, Kelwinem i Fahrenheitem. Użytkownik wpisuje temperaturę, a następnie wybiera informację, w jakich stopniach została podana. W wyniku otrzymuje informację o tym, jakie wartości ma ta temperatura w pozostałych jednostkach.

Aby dokonać przeliczeń, musisz wiedzieć, że:

• Temperatura w Kelwinach = Temperatura w stopniach Celsjusza + 273,15

• Temperatura w Fahrenheitach = 32 + (9.0/5.0) * Temperatura w stopniach Celsjusza

2. Napisz algorytm w postaci schematów blokowych, który wylicza miesięczne wynagrodzenie pracownika. Użytkownik podaje ile godzin w tygodniu przepracował pracownik oraz stawkę za godziny normalne i nadliczbowe. Normalna liczba godzin to 40 tygodniowo. Sprawdzić czy podawane wartości nie są mniejsze od zera. Zakładamy, że w miesiącu przepracował 25 dni roboczych.

3. Mały Jaś dostał na sprawdzianie z informatyki następujące zadanie: (4 punkty)

"Wykonaj schemat blokowy prezentujący sumę 10 dowolnych liczb całkowitych wprowadzanych przez użyt-kownika algorytmu".

Ochoczo zabrał się do pracy i szybko stworzył schemat blokowy do zadania (schemat poniżej). Jasio był pewny, że zadanie ma poprawnie wykonane. Jakież było jego zdziwienie, gdy okazało się, że algorytm, który stworzył był błędny.

Popraw schemat blokowy Jasia, tak aby poprawnie rozwiązywał powyższe zadanie.

Algorytm Jasia:

4. Poniżej zaprezentowano dwa schematy blokowe.

1. Czy oba schematy blokowe realizują ten sam algorytm?

2. Jak nazywa się algorytm zaprezentowany po lewej stronie?

3. Jaki zwróci wynik algorytm zaprezentowany po prawej stronie dla a = 24, b = 18?

Gdańskie Autonomiczne Gimnazjum

n

n

STOP

START

---