niedziela, 01 sierpień 2010
 
  Start
template designed by peekmambo.com
 
Menu główne
Start
 
Algorytmy
Kryptografia
Struktury danych
Kurs algorytmiki
Praktyka
Prawo IT
 
Mapa serwisu
Historia strony
Współautorzy
 
Forum
Narzędzia
Napisz artykuł
Zgłoś błąd
Szukaj
Logowanie

Schematy blokowe
Schematy blokowe są tzw. metajęzykiem. Oznacza to, że jest to język bardzo ogólny, służy do opisywania algorytmów w taki sposób, by na jego podstawie można było je zaimplementować w każdym języku.
Częściami składowymi schematów blokowych są proste figury geometryczne, np. prostokąt, romb, koło, równoległobok itd... W tych figurach umieszczamy warunki oraz proste instrukcje, przy czym mogą być one związane z jakimś konkretnym językiem (np. symbolem instrukcji przypisania może być ":=" tak, jak w Pascalu lub "=" tak, jak w C) Jeśli tworząc schemat nie jesteśmy jeszcze zdecydowani w jakim języku będziemy pisali nasz program lub tworzymy schemat dla kogoś, to lepiej jest stosować notację bardziej symboliczną, np. instrukcję przypisania zapisywać jako strzałkę skierowaną od wartości przypisywanej do zmiennej.
Za chwilę przedstawię elementy składowe schematów blokowych, przedtem jednak powiem coś o narzędziach do ich konstruowania.
Zasadniczo najszybciej schematy pisze się na zwykłej kartce, pojawia się jednak problem, gdy schemat trzeba umieścić w jakimś dokumencie (np. dokumentacji projektu). Można wtedy skorzystać z popularnych edytorów tekstu (np. Word pod Windows lub KWord pod Linux). Mają one wbudowane opcje do tworzenia figur schematu, ale nie są one zbyt wygodne w użyciu.
Alternatywą dla nich są programy specjalnie przeznaczone do opisywania algorytmów. Jednym z nich są Magiczne Bloczki (281 KB). Jest to program autorstwa Rafała Barana, studenta informatyki na Politechnice Krakowskiej. Kontakt z autorem: , jego strona www to: www.rafalbaran.net/mb. Program ten posiada bardzo przydatną opcję testowania działania algorytmu (podobnie jak w Debuggerze). Ta opcja może znacznie ułatwić życie, zwłaszcza początkującym programistom, którzy mają problemy z wyszukiwaniem błędów w programach.
Teraz przejdźmy do opisu schematów.

Image Poszczególne elementy schematu łączy się za pomocą strzałek. W większości przypadków blok ma jedną strzałkę wchodzącą i jedną wychodzącą, lecz są także wyjątki (omówię je poniżej).
Image Ta figura oznacza początek lub koniec algorytmu. W każdym algorytmie musi się znaleźć dokładnie jedna taka figura z napisem "Start" oznaczająca początek algorytmu oraz dokładnie jedna figura z napisem "Stop" oznaczająca koniec algorytmu. Najczęściej popełnianym błędem w schematach blokowych jest umieszczanie kilku stanów końcowych, zależnych od sposobu zakończenia programu. Jest to niedopuszczalne, w programie mamy przecież dokładnie jedną instrukcję "end." Blok symbolizujący początek algorytmu ma dokładnie jedną strzałkę wychodzącą a blok symbolizujący koniec ma co najmniej jedną strzałkę wchodzącą.
Image Jest to figura oznaczająca proces. W jej obrębie umieszczamy wszelkie obliczenia lub podstawienia. Proces ma dokładnie jedną strzałkę wchodzącą i dokładnie jedną strzałkę wychodzącą.

Image Romb symbolizuje blok decyzyjny. Umieszcza się w nim jakiś warunek (np. "x>2"). Z dwóch wybranych wierzchołków rombu wyprowadzamy dwie możliwe drogi: gdy warunek jest spełniony (strzałkę wychodzącą z tego wierzchołka należy opatrzyć etykietą "Tak") oraz gdy warunek nie jest spełniony. Każdy romb ma dokładnie jedną strzałkę wchodzącą oraz dokładnie dwie strzałki wychodzące.
Image Równoległobok jest stosowany do odczytu lub zapisu danych. W jego obrębie należy umieścić stosowną instrukcję np. Read(x) lub Write(x) (można też stosować opis słowny np. "Drukuj x na ekran"). Figura ta ma dokładnie jedną strzałkę wchodzącą i jedną wychodzącą.
ImageTa figura symbolizuje proces, który został już kiedyś zdefiniowany. Można ją porównać do procedury, którą definiuje się raz w programie, by następnie móc ją wielokrotnie wywoływać. Warunkiem użycia jest więc wcześniejsze zdefiniowanie procesu. Podobnie jak w przypadku zwykłego procesu i tu mamy jedno wejście i jedno wyjście.

Image Koło symbolizuje tzw. łącznik stronicowy. Może się zdarzyć, że chcemy "przeskoczyć" z jednego miejsca na kartce na inne (np. by nie krzyżować strzałek). Możemy w takim wypadku posłużyć się łącznikiem. Umieszczamy w jednym miejscu łącznik z określonym symbolem w środku (np. cyfrą, literą) i doprowadzamy do nie go strzałkę. Następnie w innym miejscu kartki umieszczamy drugi łącznik z takim samym symbolem w środku i wyprowadzamy z niego strzałkę. Łącznik jest często porównywany do teleportacji (z jednego miejsca na kartce do drugiego). Łączniki występują więc w parach, jeden ma tylko wejście a drugi wyjście.
Image Ten symbol to łącznik międzystronicowy. Działa analogicznie jak pierwszy, lecz nie w obrębie strony. Przydatne w złożonych algorytmach, które nie mieszczą się na jednej kartce. Uwaga: jeśli stosujemy oba typy łączników w schemacie, to najlepiej jest stosować liczby do identyfikowania jednych i litery do drugich. Dzięki temu nie dojdzie do pomyłki.

Teraz opiszemy przykładowy algorytm za pomocą schematu blokowego.
Zdefiniujmy iteracyjną wersję silni. Dla przypomnienia: rekurencyjna definicja silni wygląda następująco
silnia(0)=1
silnia(n)=n*silnia(n-1)
Image



Odsłon: 208529

  Komentarze (21)
1. Dodane przez lola,
w dniu - 25-09-2009 13:01
powiem ci ze tak na serio to ta twoja praca nie jest zachwycajaca... znalazlam lepsze. :grin :p :upset
2. Dodane przez Adam,
w dniu - 02-10-2009 21:34
Hmm... Kolega wyżej napisal ze nie jest zachwycajaca... Moze i mial racje, ale z drugiej strony opisujesz wszystko tak ze nawet ktos kto nie mial z algorytmami do czynienia polapalby sie w tym... Dlatego ode mnie 5 i oby tak dalej
3. Dodane przez marika,
w dniu - 05-10-2009 22:09
napisane bardzo dobrze, Miałam pierwsze wyklady o tym i nic nie rozumiałam, jak to przeczytałam to juz cos łapie :)
4. Dodane przez Informatyk,
w dniu - 08-10-2009 08:33
brawo, przydał sie przyklad silni :)
5. Dodane przez Pan i Władca,
w dniu - 21-10-2009 13:47
Podziękował:D Mam 4+ Dzięki tobie;]
6. Dodane przez Pawelek_AsKaNa,
w dniu - 25-10-2009 11:37
spoko jest, bo zrozumiałem schemat a nigdy go nie rozumiałem :) :p
7. Dodane przez :),
w dniu - 01-12-2009 21:14
Może znacie jakieś strony na których są zadnia z turbo pascala ze schematem i napisanym programem
8. Dodane przez Pan B,
w dniu - 05-12-2009 17:43
Niezle ale ja jestem z 2 gimy i szczerze mowiac nie rozumie a co chodzi juz w tym rysunku :/
9. Dodane przez Eddy,
w dniu - 07-12-2009 06:18
w pierwszym kółku podstawiasz za silnia:= licznik * silnia, biorą pod uwagę, że na początku licznik równy jest zero. Czyli z prostego rachunku wychodzi, że silnia = 0, więc już w każdym następnym kółku chyba będzie 0. Nie powinien być licznik 1 na początku ?
10. Dodane przez Tomasz Lubiński,
w dniu - 07-12-2009 22:30
Rzeczywiście na początku licznik jest równy zero. Ale przed pierwszą operacją mnożenia jest on zwiększany o 1, a więc w pierwszym mnożeniu mamy silnia := licznik * silnia = 1 * 1.
11. Dodane przez mys,
w dniu - 15-12-2009 22:07
no ja też jestem z gim.. zaczęłam naukę na własną rękę i wszystko było ok do kiedy nie zobaczyłam tego schematu :sigh
12. Dodane przez macbialy,
w dniu - 14-01-2010 10:52
Podoba mi się bardzo twoja praca. Uważam, że można się wiele z niej nauczyć. Zachęcam innych do przeczytania jej. ;) :p 8)
13. Dodane przez iwonaa,
w dniu - 17-02-2010 15:11
:cry noo moze byc!!
14. Dodane przez CombatCode,
w dniu - 23-02-2010 13:34
Quote:
w pierwszym kółku podstawiasz za silnia:= licznik * silnia, biorą pod uwagę, że na początku licznik równy jest zero. Czyli z prostego rachunku wychodzi, że silnia = 0, więc już w każdym następnym kółku chyba będzie 0. Nie powinien być licznik 1 na początku ?

 
Dobrze jest. Jeżeli licznik nie jest równy n to program dodaje do licznika + 1 i dopiero wykonuje mnożenie, nie odwrotnie.
15. Dodane przez wojtek,
w dniu - 02-03-2010 21:04
co oznacza strzałka w zapisie 
licznik
16. Dodane przez lala,
w dniu - 12-03-2010 13:14
co oznacza strzałka z wapisie?
17. Dodane przez Romek,
w dniu - 14-04-2010 01:46
Strzałka w bloczku oznacza instrukcję podstawienia, czyli licznik
18. Dodane przez Dziwny człekxDD,
w dniu - 14-05-2010 19:36
Na informatyce uczyliśmy sie tego ale nie zrozumiałem a dzięki tobie rozumiem :P dzięki ;) ;) ;) ;) ;)
19. Dodane przez darek,
w dniu - 31-05-2010 10:59
:? ehhh 
algorytm algorytmem ale skad wziasc strzalke na dol???? 
hmmm to jest problem :zzz
20. Dodane przez 19arek93,
w dniu - 11-06-2010 07:26
Bardzo dobrze opisane. :)
21. Dodane przez Adam,
w dniu - 21-06-2010 00:03
Jak dla mnie, to super praca. Wszystko (no prawie, bo chyba brakuje mi bloku np. decyzyjnego, którego właśnie szukałem), ładnie i w uporządkowany sposób ukazane. Jestem za, jak najwięcej takich prac dla potomnych, uczących się programowania jak i dla tych pragnących wiedzy :D

Napisz komentarz
  • Jeżeli jesteś zarejestrowanym użytkownikiem, zaloguj się przed dodaniem komentarza.
  • Treść komentarza powinna być związana z tematem artykułu.
  • Komentarze promujące własne strony, produkty itp. będą usuwane.
Imię:
BBCode:Web AddressEmail AddressBold TextItalic TextUnderlined TextQuoteCodeOpen ListList ItemClose List
Komentarz:



Kod antyspamowy:* Code

Powered by AkoComment Tweaked Special Edition v.1.4.6

Nowości
  • Zamiana liczby na słowa z polską gramatyką
    Bardzo często spotykam się na forach i w programach z problemem zamiany liczb na postać słowną. Zauważyłem że prawie nigdzie nie jest uwzględniona polska gramatyka, przykładowo liczba 112004033 wygląda co najmniej tak jed*jed*dwa*zero*zero*cztery*zero*trzy*trzy lub w najlepszym przypadku tak sto dwanascie mln. cztery tys. trzydziesci trzy. Dla każdego rzędu wielkości w polskiej...
  • Algorytm Cohena-Sutherlanda
    Załóżmy, że mamy dany pewien zbiór odcinków oraz okno, które definiuje nam obszar widziany przez użytkownika. W zależności od wielkości okna oraz jego położenia część odcinków znajdzie się w oknie - powinna zostać pokazana, a część znajdzie się poza oknem - nie powinna być brana pod uwagę. Takie zadanie sprawnie...
  • Całkowanie numeryczne - metoda Simpsona
    Załóżmy, że chcemy obliczyć całkę z funkcji f(x) w przedziale <xp; xk>. Definicja całki oznaczonej Riemana, mówi nam, że wartość całki równa jest sumie pól obszarów pod wykresem krzywej w zadanym przedziale całkowania. Sumę taką możemy obliczyć w przybliżeniu dzieląc obszar całkowania na n równych części. W metodach prostokątów (?option=com_content&task=view&id=198&Itemid=28)...
  • Edytor Grafów
    /* The default text style used on every page */ #hover .center .top #toolbar_wrapper form a, a:visited a:visited:hover, a:link:hover a img select, input { font-family:"lucida grande", tahoma, verdana, arial, sans-sarif; font-size:11px; background-color:#FFFFFF; border:1px solid #8FB6BD; height:18px; } textarea textarea:focus /* ------- Button formating ------ */ .bluebutton, .lightbluebutton, .greybutton { border-style:...
  • Silnie spójne składowe
    Dla grafów nieskierowanych zostało zdefiniowane pojęcie spójnych składowych, czyli maksymalnych fragmentów grafu, które są spójne (pomiędzy każdymi dwoma wierzchołkami istnieje ścieżka). Do sprawdzania czy graf jest spójny oraz znajdowania jego spójnych składowych wykorzystywany jest algorytm DFS lub BFS (?option=com_content&task=view&id=98&Itemid=28). Odpowiednikiem tej definicji dla grafów skierowanych są silnie spójne składowe. Silnie spójna...


Popularne
  • Schematy blokowe
    Schematy blokowe są tzw. metajęzykiem. Oznacza to, że jest to język bardzo ogólny, służy do opisywania algorytmów w taki sposób, by na jego podstawie można było je zaimplementować w każdym języku. Częściami składowymi schematów blokowych są proste figury geometryczne, np. prostokąt, romb, koło, równoległobok itd... W tych figurach umieszczamy warunki oraz...
  • Rekurencja
    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!,...
  • Sortowanie szybkie (quicksort)
    Algorytm sorotwania szybkiego jest uważany za najszybszy algorytm dla danych losowych. Zasada jego działania opiera się o metodę dziel i zwyciężaj (?option=com_content&task=view&id=63&Itemid=26). Zbiór danych zostaje podzielony na dwa podzbiory i każdy z nich jest sortowany niezależnie od drugiego. Dla zadanej tablicy a[l..p] wybieramy element v=a[l] i przeszukujemy resztę tablicy (tzn....
  • Grafy i ich reprezentacje
    Na początek kilka definicji: W informatyce grafem nazywamy strukturę G=(V, E) składającą się z węzłów (wierzchołków, oznaczanych przez V) wzajemnie połączonych za pomocą krawędzi (oznaczonych przez E). Grafy dzielimy na grafy skierowane i nieskierowane: Rys.1. Graf nieskierowany Rys.2. Graf skierowany Jeśli krawędź łączy dwa wierzchołki to jest z nimi incydentna. Pętla własna to krawędź łączące wierzchołek z...
  • Algorytm Dijkstry
    Algorytm Dijkstry służy do wyznaczania najmniejszej odległości od ustalonego wierzchołka s do wszystkich pozostałych w skierowanym grafie (?option=com_content&task=view&id=44&Itemid=27), w odróżnieniu jednak od Algorytmu Forda-Bellmana (?option=com_content&task=view&id=94&Itemid=0), graf wejściowy nie może zawierać krawędzi o ujemnych wagach. W algorytmie tym pamiętany jest zbiór Q wierzchołków, dla których nie obliczono jeszcze najkrótszych ścieżek, oraz...


Najwyżej oceniane
  • REGON
    Regon jest numerem identyfikującym podmioty gospodarcze w Polskim Rejestrze Gospodarki Narodowej. Dawniej numer ten był 7-cyfrowy, później REGON rozszerzono na 9 cyfr. Dawne numery 7-cyfrowe poprzedzono dwoma 0, uzyskując w ten sposób numery 9-cyforwe. Jak mówi rozporządzenie "Sposób i metodologia prowadzenia i aktualizacji rejestru podmiotów gospodarki narodowej...", Dz.U.99.69.763 numer REGON składa...
  • Współliniowość trzech punktów
    Zrozumienie tego algorytmu wymaga zaznajomienia się ze wstępem do geometrii obliczeniowej (?option=com_content&task=view&id=56&Itemid=26) Wzajemne położenie trzech punktów a, b i c można bardzo łatwo określić korzystając z wyznacznika det(a,b,c) macierzy kwadratowej postaci: det (a,b,c)>0 : punkt c znajduje się po lewej stronie wektora AB - det (a,b,c)=0 : punkty a, b, i c...
  • Zbiór Mandelbrot'a
    Po raz pierwszy pojęcie fraktala zostało użyte przez Benoit Mandelbrota w latach 70-tych XX wieku. Po łacinie fractus oznacza podzielny, ułamkowy, cząstkowy. Nazwa ta nie ma ścisłej matematycznej definicji. Oznacza ona obiekty, które mają nietrywialną strukturę w każdej skali oraz są samopodobne - czyli każda ich część przypomina całość....
  • EAN-13
    By kod EAN-13 (http://www.algorytm.org/index.php?option=com_content&task=view&id=143&Itemid=54) mógł zostać automatycznie "przeczytany" przez urządzenia skanujące musi zostać przetworzony do postaci kodu kreskowego. Sposób kodowania jest na pierwszy rzut oka nieco skomplikowany a to wszystko za sprawą kodu UPC-A (?option=com_content&task=view&id=207&Itemid=54), z którym musiał być on zgodny. Jest on 12-cyfrowy a EAN-13 jest 13-cyfrowy. Trzeba było...
  • Odległość Levenshteina (odległość edycyjna)
    Algorytm Levenshteina, służy do liczenia odległości edycyjnej (odległości Levenshteina). Jest to najmniejsza liczba działań prostych, przeprowadzająca jeden napis w drugi. Działania proste to: wstawienie nowego znaku usuniecie znaku zamiana na inny znak Idea algorytmu to stworzenie tablicy dwuwymiarowej, o wymiarach n+1 na m+1 gdzie n i m to odpowiednio długości porównywanych słów. Pierwszy wiersz i kolumnę...


Nagłówki RSS
Bookmarki







Gościmy
Aktualnie jest 15 gości online

Sonda
Czy znalazłeś na stronach www.algorytm.org to czego szukałeś?
  

www.algorytm.org (c) 2000-2009