[ Pobierz całość w formacie PDF ]
(Wprowadzenie do Algorytmów)
Definicja i geneza algorytmów
Najważniejszym pojęciem w informatyce jest algorytm
. Nazwa ta ma swoje korzenie w średniowieczu i wzięła się ze
zniekształconego nazwiska wielkiego uczonego arabskiego
Al Chuwarizmiego
, który żył na przełomie VIII i IX wieku.
Al Chuwarizmi nie był oczywiście pierwszym człowiekiem, który stosował podejście algorytmiczne do rozwiązywania
problemów. W rzeczywistości każdy z nas stosuje algorytmy w rozmaitych sytuacjach życiowych. Człowiek pierwotny
miał algorytm polowania na mamuty, czy rozpalania ognia. Dzisiaj często wykonujemy pewne algorytmy, nie zdając
sobie sprawy.
Co to są zatem algorytmy? Ogólnie określamy tym mianem
wszelkie przepisy postępowania, które doprowadzają do
uzyskania pożądanego efektu
– rozwiązania zadania. Dla informatyków algorytmy wiążą się nierozerwalnie
z
programowaniem
.
Prawdziwe problemy pojawiają się, gdy chcemy algorytm zakodować w taki sposób, żeby był dobrze wykonany przez
maszynę. Komputer niczego się nie domyśla, ba, nie rozumie języka naturalnego i potrzebna będzie nam
precyzyjna
notacja do komunikacji
. Istotą programowania jest bowiem wyrażanie algorytmów w sposób ścisły, podlegający
rygorom skończonej liczby reguł, których znaczenie w jednoznaczny sposób jesteśmy określić.
Przykłady z życia codziennego, ścisłość zapisu, kontekst
Warto przytoczyć parę przykładów algorytmów z życia codziennego:
Przepisy kucharskie - Typowy przepis zawiera deklaracje obiektów (składników pichcenia) ich początkowe
wartości (miary) oraz opis działań doprowadzający do przyrządzenia potrawy;
Zapis nutowy muzyki. Za pomocą szczególnego systemu notacyjnego określa się wysokości i względne czasy
trwania nut i pauz między nimi;
Instrukcje montażu - Często do zestawów mebli, czy klocków lego, dołączona jest kartka z instrukcją montażu
zapisaną za pomocą sekwencji rycin obrazujących kolejne fazy powstawania składanego obiektu. Użytkownik,
porównując zmiany na poszczególnych obrazkach, ma się domyślić, jakie czynności, w jakiej kolejności i za
pomocą jakich części ma wykonywać. Zauważmy, że i tu występuje charakterystyczny dla algorytmów opis
danych: najczęściej zestaw części składowych jest wyrysowany obok historyjki obrazkowej z zaznaczeniem
liczby poszczególnych elementów;
…i wiele innych.
Właściwie niemal wszystko, co robimy, podlega jakiemuś algorytmowi działania – przy czym warto podkreślić, że
ludzie nie muszą mieć algorytmów objaśnianych
dokładnie
: wiele mogą
wywnioskować z kontekstu
, doświadczenia,
po prostu domyślając się, o co może chodzić. Kucharce nie trzeba wyjaśniać, co to znaczy "
zeszklić cebulkę na
ciemnozłoty kolor
", a monterowi - co znaczy "
zaizolować przewody
".
Z komputerami jest inaczej. Jeśli dokładnie nie wytłumaczymy, co mają zrobić, stają się bezradne. Sztuczna
inteligencja, nawet jeśli istnieje, bazuje na ściśle określonych algorytmach działania i
nie ma tam miejsca na intuicję
.
Komputery bezlitośnie wyłapują błędy w opisie działania i nie ma mowy, żeby domyśliły się jaka akcje mają wykonać
na podstawie nieścisłego zapisu.
Zadanie:
Czy znacie Państwo jakieś przykłady na bezsensowne zachowania komputerów? Z czego one mogą wynikać?
Pojęcie zmiennej, instrukcja przypisania
Zmienna to informacja, której nadano strukturę. W informatyce związana jest z obszarem pamięci przechowującym tę
zmienną w postaci ciągu bitów.
O sposobie prezentacji tych danych decyduje
typ
zmiennej. MoŜna na róŜne sposoby klasyfikować zmienne. Na nasze
potrzeby wystarczy podzielić zmienne ze względu na typ danych, jaki przechowują. Najbardziej oczywistym typem są
zmienne liczbowe
(przechowujące liczby).
Tutaj moŜe wyróŜnić takie podtypy jak:
zmienne całkowite;
Mogą one przechowywać liczby tylko dodatnie lub ze znakiem
zmienne zmiennoprzecinkowe;
Typy zmiennych charakteryzują się:
zakresem
(np. od 128 do + 127)
dokładnością
(np. maksymalnie do 10 liczb po przecinku)
zbiorem operacji
, które moŜna na zmiennych wykonywać (np. dzielenie zmiennoprzecinkowe jest niedozwolone
(problematyczne) dla zmiennych całkowitych).
Zmienne w informatyce (jak i nazwy wszelkich
OBIEKTW
)zazwyczaj symbolizowane są przez ciąg znaków i cyfr (ciąg
alfanumeryczny), bez odstępów (spacji), bez polskich znaków, z moŜliwym znakiem podkreślenia, nie zaczynający się
od cyfry. Konkretne zasady związane są z przyjęciem konkretnego systemu (np. danego języka programowania)
2
.
Tak więc poprawne ciągi, które mogą symbolizować zmienne to np.:
ala
nazwa_zmiennej
zmienna3
malyKotek
pi
Z kolei poniŜsze nazwy z reguły nie mogą być wykorzystane jako nazwy zmiennych:
7UP
bo zaczyna się od cyfry
Liczba
2
bo jest odstęp w nazwie
wąskiPas
no korzysta z „polskiej litery” „ą”
NajwaŜniejszą cechą zmiennych jest to, Ŝe mogą one przechowywać
DANE
o określonym typie. Aby zmienne
przechowywała określone dane, musimy je
przypisać
. W informatyce funkcjonuje
bardzo waŜne
określenie tzw.
instrukcji przypisania
, a symbolizowane jest ona najczęściej przez symbol
:=
(dwukropek i równa się)
3
.
Kompletne instrukcje na ogół kończy się znakiem ; (średnik).
Na przykład:
Liczba := 5;
// przypisaliśmy zmiennej o nazwie Liczba wartość 5
Liczba := 10;
// zmieniliśmy zdanie i teraz ma wartość 10
Liczba := Liczba + 2;
// Teraz do poprzedniej wartości dodaliśmy 2, więc mamy razem 12
Uwaga: bardzo waŜne jest, aby odróŜniać instrukcję przypisania od znaku „równa się” w sensie matematycznym.
Zadanie:
Przy zapisie:
Liczba1 := 5;
Liczba2 := 10;
Liczba2 := Liczba2 + 2 * Liczba1 + 3;
Liczba1 := Liczba1 + Liczba2;
Jaka wartość zostanie przypisana do zmiennych
Liczba1
i
Liczba2
po wykonani się powyŜszych instrukcji?
Liczba1= …. Liczba2= ….
Dokładnie typami, zmiennymi i reprezentacją danych będziemy zajmować się w dalszej części zajęć. Na razie
wystarczy wprowadzenie pojęcia
zmienna
,
instrukcja
,
instrukcja przypisania
.
Blokowa reprezentacja algorytmów
Algorytmy wygodnie jest zapisywać w postaci diagramów czy schematów blokowych
. Takie schematy przedstawiają
w formie graficznej każdy krok wykonywanego algorytmu. W ten sposób można prezentować nawet dość abstrakcyjne
problemy.
Jest to dość powszechny, ale nie jedyny sposób zapisu algorytmów. Alternatywą jest np. zastosowanie
pseudokodu
.
Graficzna reprezentacja poszczególnych operacji i ich znaczenie przedstawia poniższa tabela:
2
Na przykład w popularnym języku PASCAL nie ma odróżniania dużych i małych liter. Tak więc ciąg ALA, ala, Ala będzie oznaczał ten samą nazwę.
W językach C i pochodnych duże i małe litery są rozróżniane i ciągi te będą oznaczały
różne nazwy
.
3
Tutaj znów instrukcja przypisania różnie jest zapisywana w różnych językach. Przyjęło się jednak, że w zapisach ogólnych stosuje się := . Zapis taki
stosuje się także języku PASCAL.
REPREZENTACJA
GRAFICZNA OPERACJI
OPIS OPERACJI
UWAGI
START
POCZĄTEK ALGORYTMU
WYSTĘPUJE JEDEN
START,
JEDNO POŁĄCZENIE
WYCHODZĄCE ŻADNYCH
WCHODZĄCYCH,
POSIADA 1 POŁĄCZENIE
WCHODZĄCE
ZAKOŃCZENIE
KONIEC
WPROWADŹ
lub
WYPROWADZ
BLOK WEJŚCIA/WYJŚCIA
PO 1 WCHODZĄCYM I
WYCHODZĄCYM
BLOK DECYZYJNY
(WARUNKOWY)
JEDNO WEJŚCIOWE, DWA
WYJŚCIOWE,
TAK – SPEŁNIONY
WARUNEK,
NIE NIESPEŁNIONY
CZY
L>0
Przykłady algorytmów
Średnia trzech liczb:
Algorytm realizuje następujące operacje:
1.WPROWADŹ A, B, C
2.OBLICZ SUMA = A+B+C
3.OBLICZ SREDNIA = SUMA/ 3
4. WYPROWADŹ SREDNIĄ
Reprezentacja graficzna:
START
WPROWADŹ
(A,B,C)
SUMA:=A+B+C
SR:=SUM/ 3
KONIEC
Wartość bezwzględna liczby:
1.WPROWADŹ LICZBĘ
2.JEŻELI LICZBA WIĘKSZA LUB RÓWNA 0 TO WYNIK RÓWNA SIĘ L
W PRZECIWNYM WYPADKU WYNIK RÓWNA SIĘ -L
4.WYPROWADŹ WYNIK
Reprezentacja graficzna:
Sprawdź działanie:
START
WPROWADŹ (L)
CZY
L>=0
W:= L
W:= L
WYPROWADŹ (W)
KONIEC
WYZNACZENIE MIEJSC ZEROWYCH RÓWNANIA KWADRATOWEGO
1.WPROWADŹ A, B, C
2.JEŻELI A RÓŻNE OD ZERA TO OBLICZ DELTĘ = B*B-4AC W PRZECIWNYM WYPADKU KONIEC ALG.
3.JEŻELI DELTA >= TO OBLICZ X1 I X2 W PRZECIWNYM WYPADKU KONIEC ALG
4.WYPROWADŹ X1, X2
Reprezentacja graficzna:
START
Sprawdź działanie:
WPROWADŹ (A, B, C)
CZY A
RÓŻNE
OD 0
OBLICZ DELTĘ
B*B4AC
KONIEC
CZY
DELTA
>= OD 0
OBLICZ X1, X2
WYPROWADŹ (X1, X2)
KONIEC
Obliczanie wartości n!
Operator ! (silnia) oznacza kolejne mnożenia liczb naturalnych, n! = 1 * 2 * 3 * 4 … (n-1) * n.
1. Wczytaj liczbę silnia
2. Ustaw zmienną i na 0, zmienną wynik na 1;
3. Zwiększ zmienną i o 1
4. Sprawdź, czy i jest mniejsze niż silnia?
jeśli tak to oblicz wynik := wynik*(silnia – i), ich do (3)
5. Czy silnia równa się 0?
Jeśli tak to ustaw wynik na 0
6. Wypisz wynik
Reprezentacja graficzna:
Sprawdź działanie:
[ Pobierz całość w formacie PDF ]
© 2009 Po zniszczeniu przeszłości przyszedł czas na budowanie przyszłości. - Ceske - Sjezdovky .cz. Design downloaded from free website templates