sobota, 23 listopad 2024
 
Strona główna Algorytmy Podstawy algorytmiki

Podstawy algorytmiki

1. Sieci działań zasady tworzenia graficznej postaci algorytmów w postaci tzw "sieci działań", zwanej również "schematem blokowym".
2. Instrukcje Porównanie typowych instrukcji w kilku językach programowania:
Instrukcja złożona
Instrukcja warunkowa prosta - if-then
Instrukcja warunkowa złożona - if-then-else
Instrukcja wyboru - case
Pętla ze sprawdzaniem warunku na początku - while
Pętla ze sprawdzaniem warunku na końcu - repeat
Pętla z licznikiem - for
  1. Sieci działań

    Sieć działań jest graficznym sposobem opisu algorytmów. Charakteryzuje się dużą czytelnością i łatwością analizy algorytmów. Poniżej w tabeli przedstawione są najczęściej stosowane symbole w sieciach działań.
    Sieci działań często określa się nazwą "schemat blokowy". Moim zdaniem nie odpowiada to ich istocie. Schematy blokowe dotyczą raczej opisu urządzeń (np. schemat blokowy komputera), a nie czynności.

    Początek algorytmu. Wewnątrz symbolu wpisuje się zwykle słowo "START" lub nazwę podprogramu. W algorytmie może wystąpić tylko jeden taki symbol.
    Zakończenie algorytmu. Wewnątrz symbolu wpisuje się zwykle słowo "STOP" lub "WRÓĆ", "RETURN" (dla podprogramów). W algorytmie może wystąpić wiele takich symboli.
    Linie ze strzałkami określają kolejność wykonywanych czynności w algorytmie. Linii tych nie wolno rozgałęziać, natomiast mogą się schodzić w jednym punkcie (węźle).
    Pierwszy symbol oznacza ogólnie operację wejścia/wyjścia. Wygodniej jest jednak odróżnić kierunek wymiany danych.
    Drugi symbol oznacza operacje wejściowe (np. dane z klawiatury, z pliku lub parametry wywołania procedury).
    Trzeci symbol oznacza operacje wyjściowe (np. na ekran, drukarkę lub do pliku).
    Instrukcja warunkowa. Jest to jedyny sposób rozgałęzienia sieci działań. Wewnątrz symbolu wpisuje się wyrażenie warunkowe. Wychodzą z symbolu dwie ścieżki oznaczone jako T (tak, prawda) oraz N (nie, fałsz). Jeżeli wyrażenie jest rozbudowane, to można symbol rozszerzyć tak, aby zmieścić zapis wzoru.
    Odmiana instrukcji warunkowej oznaczająca wybór dalszej ścieżki zależnie od wartości zmiennej lub wyrażenia. Odpowiada ciągowi instrukcji warunkowych ale pozwala na bardziej zwarty zapis algorytmu i programu.
    Symbol "przetwarzanie danych". Wewnątrz opisuje się czynności przetwarzania danych, najczęściej za pomocą wzorów lub tekstu.
    Wywołanie podprogramu. Wewnątrz zwykle wpisuje się nazwę podprogramu i parametry wywołania.
    Łączniki umożliwiają połączenie odległych fragmentów sieci działań. Stosowane są przy dużych sieciach działań. Pierwsza para przedstawia łączniki wewnątrzstronicowe, druga międzystronicowe. Wewnątrz symbolu należy wpisać etykietę łącznika (np. litera lub cyfra), a w łączniku międzystronicowym również numer strony, do której prowadzi połączenie.
    Komentarze, czyli opisy różnych elementów sieci. Można w ten sposób zaznaczać np. istotne, węzłowe miejsca w programie lub dodatkowo opisać niektóre czynności.
    Bliżej nieokreślony ciąg instrukcji. Stosowany we wstępnych etapach konstruowania algorytmu.
    Symbol pętli typu for. Pętle konstruuje się zwykle przy pomocy instrukcji warunkowej. Jednak dla pętli for (zwłaszcza zagnieżdżonych) prowadzi do dość skomplikowanych i nieczytelnych struktur sieci. Ten symbol znacznie upraszcza sieć działań.
    do góry
  2. Instrukcje

    Poniżej przedstawiam podstawowe instrukcje w językach Pascal, C++, Java(Java Script) i PHP . Warto zauważyć niemal identyczną postać instrukcji w językach C++, Java Script i PHP.

    1. Instrukcja złożona (blok, ciąg instrukcji)

    W instrukcjach typu pętle lub warunki często norma języka przewiduje pojedyńczą instrukcję. Jeżeli chcemy użyć dłuższego ciągu instrukcji, to należy go przekształcić w tzw. instrukcję złożoną (blok instrukcji).)
    PascalC++ Java ScriptPHP 
    begin
    Instrukcja1;
    Instrukcja2;
    ...
    Instrukcjan
end;
    {   Instrukcja1;
    Instrukcja2;
    ...
    Instrukcjan;
}
    {   Instrukcja1;
    Instrukcja2;
    ...
    Instrukcjan;
}
    {   Instrukcja1;
    Instrukcja2;
    ...
    Instrukcjan;
}
    do góry

    2. Instrukcja warunkowa prosta - " if-then"

    Jeżeli warunek W jest spełniony to wykonaj instrukcję, w przeciwnym wypadku nie rób nic.

    PascalC++ Java ScriptPHP 
    if x>0 then
    Instrukcja;
________________________

if x>0 then
   begin
    CiągInstrukcji
   end;
    if (x>0)
    Instrukcja;
________________________

if (x>0)
{
    CiągInstrukcji;
}
    if (x>0)
    Instrukcja;
________________________

if (x>0)
{
    CiągInstrukcji;
}
    if ($x>0):
    CiągInstrukcji;
endif;
________________________

if ($x>0)
{
    CiągInstrukcji;
}
    do góry

    3. Instrukcja warunkowa złożona- " if-then-else"

    Jeżeli warunek W jest spełniony to wykonaj instrukcję 1, w przeciwnym wypadku wykonaj instrukcję 2.

    PascalC++ Java ScriptPHP 
    if x>0 then
    Instrukcja1
else
    Instrukcja2;
________________________

if x>0 then
   begin
    CiągInstrukcji1
   end
else
   begin
    CiągInstrukcji2
   end;
    if (x>0)
    Instrukcja1;
else
    Instrukcja2;
________________________

if (x>0)
{
    CiągInstrukcji1;
}
else
{
    CiągInstrukcji2;
}
    if (x>0)
    Instrukcja1;
else
    Instrukcja2;
________________________

if (x>0)
{
    CiągInstrukcji1;
}
else
{
    CiągInstrukcji2;
}
    if ($x>0):
    CiągInstrukcji1;
else:
    CiągInstrukcji2;
endif;
________________________

if ($x>0)
{
    CiągInstrukcji1;
}
else
{
    CiągInstrukcji2;
}
    do góry

    4. Instrukcja wyboru - " case"

    Jeżeli x=s1 to wykonaj Instr 1, jeżeli x=s2 to wykonaj Instr 2, itd. Jeżeli wartość x nie jest wymieniona, to wykonaj Inne

    Testowana jest wartość wyrażenia (lub zmiennej) typu porządkowego przez porównanie ze stałymi s1, s2 itd. Jeżeli nie zostanie znaleziona, to nastąpi przejście do frazy else / default, o ile ona występuje.

    Rzeczywiste działanie instrukcji wyboru w Pascalu i w pozostałych językach nieco się różni. W Pascalu po wykonaniu wskazanej instrukcji następuje wyjście za instrukcję wyboru, natomiast w C++, JS i PHP wykonywane są kolejne instrukcje (należące do następnej frazy case). Wyjście ze struktury instrukcji wyboru należy wymusić poleceniem break;

    PascalC++ Java ScriptPHP 
    case wyrażenie of
  s1:  Instrukcja1;
  s2:  Instrukcja2;
  s3:  Instrukcja3;
  ...
  else    Inne
end
    switch (wyrażenie)
{ case s1:  CiągInstr1;
            break;
  case s2:  CiągInstr2;
            break;
  case s3:  CiągInstr3;
            break;
  ...
  default:   Inne;
}
    switch (wyrażenie)
{ case s1:  CiągInstr1;
            break;
  case s2:  CiągInstr2;
            break;
  case s3:  CiągInstr3;
            break;
  ...
  default:   Inne;
}
    switch ($wyrażenie):
  case s1:  CiągInstr1;
            break;
  case s2:  CiągInstr2;
            break;
  case s3:  CiągInstr3;
            break;
  ...
  default:   Inne;
endswitch;
________________________

switch ($wyrażenie)
{ case s1:  CiągInstr1;
            break;
  case s2:  CiągInstr2;
            break;
  case s3:  CiągInstr3;
            break;
  ...
  default:   Inne;
}
    do góry

    5. Pętla ze sprawdzaniem warunku na początku - " while"

    Dopóki wyrażenie w jest prawdziwe wykonuj Instrukcję

    Warunek powtarzania pętli jest sprawdzany przed wejściem do niej. Z tego powodu zmienne wykorzystywane w wyrażeniu warunkowym muszą być określone przed instrukcją pętli.

    Jeżeli warunek jest fałszywy przy pierwszym testowaniu, to w ogóle nie nastąpi wykonanie pętli.

    PascalC++ Java ScriptPHP 
    while x<>0 do
   Instrukcja;
________________________

while x<>0 do
begin
   CiągInstrukcji
end
    while (x!=0)
   Instrukcja;
________________________

while (x!=0)
{
   CiągInstrukcji;
}
    while (x!=0)
   Instrukcja;
________________________

while (x!=0)
{
   CiągInstrukcji;
}
    while ($x!=0):
   CiągInstrukcji;
endwhile;
________________________

while ($x!=0)
{
   CiągInstrukcji;
}
    do góry

    6. Pętla ze sprawdzaniem warunku na końcu - " repeat"

    Powtarzaj Instrukcje aż do spełnienia warunku w.(Pascal)
    Powtarzaj Instrukcje dopóki warunek w jest spełniony.(C++, JS i PHP)

    Ponieważ warunek pętli sprawdzany jest na końcu, to jej treść zostanie wykonana przynajmniej raz.
    Istotną różnicą między językami jest znaczenie wyrażenia warunkowego:
    - w Pascalu jest to warunek zakończenia pętli,
    - w C++, PHP i JS jest to warunek kontynuacji pętli. Ilustrują to sieci działań.
    Ze względu na tą różnicę w celu uzyskania takiego samego efektu w Pascalu i językach C++, JS i PHP należy w tych drugich odwrócić warunek.
    PascalC++ Java ScriptPHP 
    repeat
   CiągInstrukcji
until x=0;
    do
   CiągInstrukcji;
while (x!=0);
    do
   CiągInstrukcji;
while (x!=0);
    do
   CiągInstrukcji;
while ($x!=0);
    do góry

    7. Pętla z licznikiem - " for"

    Pascal:

    Dla i zmienniającego się od wartości początkowej (wp) do wartości końcowej (wk) z krokiem 1 wykonuj Instrukcję

    W Pascalu istnieje druga wersja z krokiem -1 (zamiast to należy wpisać downto).

    W językach C++, JS i PHP jej działanie jest inne, bardziej uogólnione:

    for(inicjacja ; warunek ; modyfikacja)
    Instrukcja;

    Wykonaj instrukcje inicjujące. Następnie, dopóki warunek jest spełniony wykonuj Instrukcję i Instrukcje modyfikujące

    Taka postać instrukcji jest bardzo elastyczna i pozwala na realizację dość skomplikowanych i nietypowych pętli.

    PascalC++ Java ScriptPHP 
    for i:=1 to 20 do
   Instrukcja;
________________________

for i:=1 to 20 do
begin
   CiągInstrukcji
end;
    for(i=1; i<=20 ;i++)
   Instrukcja;
________________________

for(i=1; i<=20 ;i++)
{
   CiągInstrukcji;
}
    for(i=1; i<=20 ;i++)
   Instrukcja;
________________________

for(i=1; i<=20 ;i++)
{
   CiągInstrukcji;
}
    for($i=1; $i<=20 ;$i++)
   Instrukcja;
________________________

for($i=1; $i<=20 ;$i++)
{
   CiągInstrukcji;
}
    do góry

    8. Pętla dostępu do tablic - " foreach"

    Instrukcja pę tli foreach występuje tylko w języku PHP. Daje możliwość obróbki wszystkich elementów tablicy bez znajomości kluczy lub indeksów.

    Dla wszystkich elementów tablicy wykonaj Instrukcję

    Taka postać pętli for wynika z nietypowej konstrukcji tabel w PHP.

    PascalC++ Java ScriptPHP 
    nie istnieje
    nie istnieje
    nie istnieje
    foreach($tablica as $wartość)
{
   CiągInstrukcji;
}
________________________

foreach($tablica as $klucz => $wartość)
{
   CiągInstrukcji;
}
    do góry
© mgr inż. Piotr Kotarski, Kalety