Co to jest algorytm?




Pobierz 35.71 Kb.
NazwaCo to jest algorytm?
Data konwersji27.09.2012
Rozmiar35.71 Kb.
TypDokumentacja
Co to jest algorytm?

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?


a) iteracyjne - rodzaj algorytmu i programu, w których wielokrotnie wykonuje się pewne instrukcje, dopóki nie zostanie spełniony określony warunek,

b) rekurencyjne - takie procedury, które w swojej definicji posiadają wywołanie samej siebie,

c) 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

  1. Przeczytaj wiersz pierwszy raz.

  2. Przeczytaj wiersz drugi raz.

  3. 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

  1. Przeczytaj wiersz trzy razy.

  2. Czytaj wiersz.

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

  4. 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

  1. Przeczytaj wiersz.

  2. Czy umiesz wiersz na pamięć?
    a) jeśli tak, przejdź do kroku 3,
    b) jeśli nie, przejdź do kroku 1.

  3. 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

  1. Stój.

  2. Czy świeci się czerwone światło na przejściu dla pieszych?

  1. jeśli tak, przejdź do kroku 1,

  2. jeśli nie, przejdź do kroku 2.

  1. 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.


Przykłady algorytmów w matematyce


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.

  1. Podaj algorytm obliczający pole powierzchni całkowitej i objętość:

a) sześcianu,

b) graniastosłupa,

c) walca.


Przykłady algorytmów w fizyce


BUDOWA ALGORYTMU:

START

  1. Zmierz masę ciała stałego m:=

  2. Zmierz za pomocą menzurki objętość ciała V:=

  3. Oblicz gęstość ciała



  1. 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 ?

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

    2. 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.

  1. 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ł.

  2. Zapisz algorytm obliczania drogi w ruchu:

a) jednostajnym po linii prostej,

b) jednostajnym po okręgu,

c) jednostajnie przyspieszonym.

  1. 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).

  2. Zapisz algorytm obliczania:

a) pracy,

b) mocy,

c) energii potencjalnej ciężkości,

d) energii kinetycznej ciała,

e) oporu elektrycznego (prawo Ohma).

  1. 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.

Dodaj dokument na swoim blogu lub stronie

Powiązany:

Co to jest algorytm? iconAlgorytm algorytm jest pewną ściśle określoną procedurą obliczeniową, która dla właściwych danych wejściowych “produkuje żądane dane wyjściowe zwane wynikiem działania algorytmu

Co to jest algorytm? iconAlgorytm generowania liczby pi w aplikacji zostanie użyty algorytm Gauss’a-Legendre’a znany też jako algorytm Brent-Salamin’a. Opis algorytmu

Co to jest algorytm? iconCo to jest algorytm, a czym jest program komputerowy?

Co to jest algorytm? iconAlgorytmy lekcja 1: Co to jest algorytm?

Co to jest algorytm? iconAlgorytmy podstawy I zastosowanie Czym jest algorytm?

Co to jest algorytm? iconAlgorytm jest to, określony ciąg czynności, który prowadzi do rozwiązania danego problemu. 1

Co to jest algorytm? iconAlgorytm jest uporządkowanym zbiorem jednoznacznych, wykonywalnych kroków określających skończony proces

Co to jest algorytm? iconAlgebra liniowa jest pomysłem Grassmanna praca Teoria rozciągłości 1861 Algorytm Euklidesa

Co to jest algorytm? iconAlgorytm jest ściśle zdefiniowaną procedurą obliczeniową, która dla właściwych danych wejściowych produkuje żądane wyniki, zgodnie z warunkami zdefiniowanymi przez problem obliczeniowy

Co to jest algorytm? iconAlgorytm Euklidesa

Umieść przycisk na swojej stronie:
Rozprawki


Baza danych jest chroniona prawami autorskimi ©pldocs.org 2014
stosuje się do zarządzania
Rozprawki
Dom