czwartek, 13 sierpień 2020
 
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