Programowanie
Podstawy Informatyki
Sformułowanie problemu.
Opracowanie metodyki rozwiązania.
Metalurgia, I rok
Opracowanie algorytmu.
Napisanie kodu z
ródłowego (zakodowanie) w wybranym
języku (Pascal, Fortran, C++, itp.).
Kompilacja kodu z
ródłowego
Uruchomienie programu na komputerze.
Wykład 4
Wykonanie obliczeń.
Algorytmy
Analiza otrzymanych wyników.
Usunięcie błędów programu (debugging).
Co to jest algorytm?
Istotne cechy algorytmu
Jeżeli mamy do wykonania jakieś zadanie, budujemy sposób,
" Definicja zadania = co algorytm ma zrobić.
przepis realizacji tego zadania. Taki przepis to algorytm.
" Opis ciągu czynnosci, które po kolei mają być wykonane.
Przykłady:
" Czynności te muszą być na tyle proste (i możliwe do wykonania),
" przepis kucharski,
aby wykonawca algorytmu mógł je bez dodatkowego tłumaczenia,
" instrukcja składania mebla/urządzenia. . . ,
wykonać �!operacje elementarne;
odpowiednio dobrany poziom szczegółowości.
" zapis nutowy,
" Skonczona ilość operacji elementarnych �!skończony czas
" wykonywanie pisemne dodawania/mnożenia/dzielenia...
działania.
" Algorytm dostaje pewne informacje (dane wejściowe) i zwraca
Algorytm (definicja nieformalna)
jakieś (oczekiwane) wyniki  dane wyjściowe.
to sposób postępowania (przepis) umożliwiający rozwiązanie
" Może istnieć kilka przepisów, które dają w efekcie te same
określonego zadania (klasy zadań), podany w postaci
wyniki.
skończonego zestawu czynności do wykonania, ze wskazaniem
ich następstwa.
Algorytm sekwencyjny - opis słowny
Algorytm
Postawienie problemu:
Pochodzenie nazwy:
- Co należy zrobić, aby zobaczyć film  Katyń ?
od nazwiska w wersji łacińskiej Algorithmus, Algorismus
Algorytm 1a:
perskiego matematyka Muhammeda ibn Musy zwanego al
Idz
do kina
Chuwarismi, żyjącego w IX w (podał on algorytmy
Kup bilet
wykonywania działań arytmetycznych na liczbach
dziesiętnych.
Obejrzyj film
Wróć do domu
Algorytmika - dział wiedzy zajmujący się badaniem algorytmów
Sposoby zapisu algorytmu:
Algorytm powyższy zawiera 4 podstawowe składniki, z
" słowami, których każdy wymaga zakończenia wykonania pewnej
akcji przed rozpoczęciem następnej.
" za pomocą schematu blokowego,
W komputerze każdy składnik będzie zapisany jako
" w pseudokodzie, instrukcja lub grupa instrukcji (procedura).
Algorytm powinien być kolejno uściślany, by mógł być w
" w jednym z języków programowania
swojej ostatecznej postaci zrozumiały dla komputera, oraz
Program - formalnie spisana wersja algorytmu. by uwzględniał wszystkie okoliczności przewidziane przez
projektanta.
Przykład algorytmu:
Algorytm 1b:
sumowanie zarobków pracowników
POCZ
TEK
Dane: lista pracowników z zarobkami (tablica A)
jeżeli nie wyświetlają filmu "Katyń
(1) zanotuj "na boku"(zmienna suma) liczbę 0;
to znajdz
sobie inne zajęcie
Powtarzaj
w przeciwnym razie { idz
do kina
jeżeli jest kolejka to ustaw się w kolejce (na końcu?) (2) przeglądaj ankiety i dodawaj zarobki każdego pracownika do
liczby "na boku";
dopóki przed Tobą stoją ludzie wykonuj przesuwaj się do
przodu
Aż do
jeżeli są wolne miejsca to {kup bilet, znajdz
swoje miejsce
(3) kiedy osiągniesz koniec listy, przedstaw wartość liczby "na boku"
dopóki trwa projekcja jako wynik (suma).
wykonuj oglądaj film}
Cechy tego algorytmu:
w przeciwnym razie zaklnij po cichu, wyjdz
z kina
" Działa na różnych zestawach danych, ale daje poprawne wyniki.
wróć do domu }
" Sam tekst algorytmu jest ograniczony i krótki, ale proces który
KONIEC
opisuje zmienia się wraz z długościa listy pracowników.
Algorytmy przedstawione powyżej wykorzystują język
Oprócz algorytmów słownych, często
naturalny oraz słowa kluczowe. Słowa kluczowe definiują
stosuje się zapis algorytmu w postaci
podstawowe struktury sterujące programu oraz procesy
podejmowania decyzji występujących w algorytmie:
schematów blokowych.
jeżeli ..... to ..... w przeciwnym razie
dopóki ..... wykonuj
Schemat blokowy (block diagram, flowchart) to diagram,
powtarzaj ..... aż do
na którym algorytm jest reprezentowany przez opisane
Te słowa kluczowe mają swoje odpowiedniki w każdym z
figury geometryczne, połączone liniami zgodnie z
języków programowania.
kolejnością wykonywania czynności wynikających z
Wprowadzenie słów kluczowych do opisu słownego
algorytmu jest częścią tzw. pseudo - kodu,
przyjętego algorytmu rozwiązania zadania; pozwala
wykorzystywanego do zapisu algorytmu.
dostrzec istotne etapy algorytmu i logiczne zależności
Szczegółowy algorytm jest podstawą dla prawidłowo
między nimi;
zakodowanego programu.
Algorytm z  wcięciami pozwala na bardziej czytelny zapis, i
stanowi nieformalną metodę ułatwiającą śledzenie  dróg
programu.
START
Schematy blokowe
czytaj:
n,a(i), dla i=1,...n
Start
Stop
suma=0
suma=suma + a(i)
instrukcja
i=i+1
czytanie danych,
tak wydruk wyników
i d" n
d"
d"
d"
tak
?
nie
druk: suma
nie
STOP
Algorytm Euklidesa
Problem: mając dane dwie liczby naturalne a i b znalez
ć
" strzałka wskazuje kierunek przebiegu sterowania programem,
ich największy wspólny dzielnik.
łączy inne bloki,
Pierwotnie problem ten sprowadzał się do czysto
" operand (prostokąt)  wszystkie operacje z wyjątkiem instrukcji
geometrycznego problemu znalezienia wspólnej miary dla
wyboru,
dwóch odcinków.
" predykat (romb)  instrukcja wyboru,
" etykieta (owal)  początek lub koniec sekwencji schematu.
" wejście/wyjście (równoległobok).
Zadanie algorytmiczne:
Dane: a, b " N,
Wynik: NWD(a,b).
Schemat blokowy
Opis słowny:
" dane są dwie liczby a i b;
START
" jeśli a jest równe b, to NWD jest równe a,
" w przeciwnym wypadku, jeżeli a jest większe od b, to zmień a
czytaj:
na równe a - b, a jeżeli a jest mniejsze od b to zmień b na b - a;
a, b
" zacznij od początku.
a<>b
Drukuj a
nie
tak
a>b
nie
tak
STOP
a=a-b b=b-a
Algorytm Euklidesa (metoda 2)
Algorytm Euklidesa (metoda 1)
" Język C
if(a < b) {
" Pseudokod
t = a;
loop
a = b;
if a = b then return a;
b = t;
else if a > b then a := a -b;
}
else b := b -a;
while(b != 0) {
" Język C
c = a % b;
while(a != b) {
a = b;
if(a > b) a -= b;
else b -= a; b = c;
}
}
return a;
return a;
 Zdanie proste
Przy opracowywaniu algorytmu zwracamy uwagę na:
Określa elementarny lub bardziej złożony krok algorytmu.
jego poprawność semantyczną (składnię),
Jeżeli jest to krok elementarny, to wystarczy przy tworzeniu programu
prostotę,
zapisać ten krok w języku programowania.
czas działania,
Jeżeli natomiast jest to złożony krok algorytmu, to podczas
uszczegółowienia algorytmu zostanie on zastąpiony sekwencją
ilość zajmowanej pamięci komputera,
prostszych zdań.
optymalność,
ograniczenia
Przykład elementarnego kroku - instrukcja podstawienia (przypisania):
przypisz zmiennej suma wartość zero
FORTRAN: suma = 0.0
C: suma = 0.0 ;
PASCAL: suma :=0.0 ;
Zdanie złożone:
PODEJMOWANIE DECYZJI W PROGRAMIE
oblicz pierwiastek równania kwadratowego
Jest to złożony krok algorytmu wymagający uszczegółowienia.
Zdanie decyzyjne  jeśli
W programie jest to realizowane poprzez instrukcję złożoną grupującą
ciąg instrukcji prostych.
Zdanie to zawiera strukturę opisującą decyzje
podejmowane w algorytmie. Istnieją 2 rodzaje struktur:
struktura prosta : jeśli ..... to
struktura z alternatywą: jeśli ..... to .... w przeciwnym
razie
Struktura prosta Przykład:
jeśli średnia ocen studenta jest większa od 4.5 to
jeśli warunek to wpisz studenta na listę nagród
zdanie
gdzie warunek jest wyrażeniem przyjmującym dwie warunek : średnia ocen studenta jest większa od 4.5
wartości:
- wartość prawdy,
Jeżeli warunek jest prawdziwy, to wykonywane jest
- wartość fałszu
zdanie:
wpisz studenta na listę nagród
Jeżeli warunek przyjmie wartość prawdy, to wykonuje się
zdanie, a gdy warunek przyjmie fałsz, to zdanie nie
zostanie wykonane.
Rozważmy następujący problem:
Struktura z alternatywą
W zależności od wartości jakie przyjmuje zmienna x (np
ocena) należy wydrukować następujące komunikaty:
jeśli warunek to
zdanie 1
dla x <3 komunikat  negatywna
w przeciwnym razie
dla 3 <= x <= 6 komunikat  pozytywna
zdanie 2
dla x > 6 komunikat  niemożliwa
Algorytm przyjmie postać:
jeżeli x <3 to
wypisz  negatywna
w przeciwnym razie
jeżeli 3 <= x i x <= 6 to
wypisz  pozytywna
w przeciwnym razie
wypisz  niemożliwa
W programach numerycznych warunkiem jest najczęściej
FORTRAN:
wyrażenie logiczne:
a).
IF ( warunek ) THEN
nie, lub, i
zdanie 1
ENDIF
Np.: a lub b,
(a lub b) i c, .....
b).
IF ( warunek ) THEN
W wyrażeniach logicznych występują też relacje:
zdanie 1
= , <>, >, <, <=, >=
ELSE
zdanie 2
Np.: a > b,
ENDIF
c <= d
Przykład zdania decyzyjnego:
jeśli (a > b) lub (c <= d) to
podstaw x = 0
PASCAL: C:
a). a).
IF warunek THEN IF warunek
zdanie 1; zdanie 1;
b). b).
IF warunek THEN IF warunek
zdanie 1 zdanie 1;
ELSE ELSE
zdanie 2; zdanie 2;
Instrukcja decyzyjna wybierz Przykład:
Zdanie wybierz służy do wyboru jednej z kilku możliwości. Program cenzurka1
Ma ono postać:
....
....
wybierz przełącznik z
wybierz ocena z
wartość_1: zdanie_1
6: pisz( celujacy );
....
5: pisz( bardzo dobry );
wartość_n: zdanie_n
4: pisz( dobry );
w przeciwnym razie akcja awaryjna
3: pisz( dostateczny );
2: pisz( niedostateczny );
Przykład:
w przeciwnym razie pisz( blad danych )
wybierz p z
....
1: wykonaj wariant pierwszy
....
2: wykonaj wariant drugi
Koniec
3: wykonaj wariant trzeci
w przeciwnym razie wydrukuj komunikat o błędzie
Program cenzurka2
Blok instrukcji
.....
jeżeli ocena = 6 to
W przypadku, gdy w danej instrukcji, np. instrukcji
pisz( celujacy )
warunkowej, powinna wykonać się więcej niż jedna
w przeciwnym razie
instrukcja, wówczas stosowany jest blok instrukcji.
jeżeli ocena = 5 to
pisz( bardzo dobry )
Pascal:
C:
w przeciwnym razie
jeżeli ocena = 4 to
begin
{
pisz( dobry )
instrukcja1;
instrukcja1;
w przeciwnym razie
jeżeli ocena = 3 to
instrukcja2;
instrukcja2;
pisz( dostateczny )
instrukcja3;
w przeciwnym razie instrukcja3;
jeżeli ocena = 2 to
........
........
pisz( niedostateczny )
w przeciwnym razie
end;
}
pisz( blad danych )
Iteracja warunkowadopóki(while)
Działanie pętli:
dopóki(wyrażenie) wykonuj instrukcja1;
" Obliczana jest wartość wyrażenia
" Jeśli wyrażenie jest równe fałszywe to instrukcja1 nie jest
w ogóle wykonywana
" Wpp. wykonywana jest instrukcja1.
nie
" Ponownie obliczana jest wartość wyrażenia i ponownie
wyrażenie
sprawdzana jego prawdziwość itd.
tak " Jeśli wyrażenie będzie fałszywe, to działanie pętli zostanie
przerwane
instrukcja1
Uwaga: obliczenie wartości wyrażenia odbywa się przed
wykonaniem instrukcji1
Instrukcja1 może nie wykonać się ani jeden raz!
Iteracja warunkowapowtarzaj ...aż do ...
Działanie pętli:
(repeat ... until ...)
" Wykonywana jest instrukcja1
powtarzaj instrukcja1 aż do(wyrażenie) ;
" Obliczana jest wartość wyrażenia
" Jeśli wyrażenie jest równe fałszywe to instrukcja1 jest
wykonywana kolejny raz
instrukcja1
" Ponownie obliczana jest wartość wyrażenia i ponownie
sprawdzana jego prawdziwość itd.
tak
" Jeśli wyrażenie będzie prawdziwe, to działanie pętli
wyrażenie
zostanie przerwane
nie
Uwaga: obliczenie wartości wyrażenia odbywa się po
wykonaniu instrukcji1
Instrukcja1 musi wykonać się conajmniej jeden raz!
Iteracja ograniczonadla(for)
dla od do (z krokiem )
Działanie pętli:
wykonuj instrukcja1 ;
" Wykonanie instrukcji inicjalizujących pętlę
�!
�!
�!
�!
�!
" Sprawdzenie wyrażenia warunkowego
+
d" .
d"
d"
d"
nie Jeśli fałsz, praca pętli zostaje zakończona,
zmienna d"
Jeśli prawda, wykonana zostanie instrukcja1
" Wykonanie instrukcji
instrukcja1
zwiększ o
tak
Uwaga: sprawdzenie wyrażenia d"
d"
d"
d"
Instrukcja1 może nie wykonać się ani jeden raz!
odbywa się przed wykonaniem instrukcja1
Instrukcje wejścia/wyjścia
Umożliwiają komunikowanie się programu z
użytkownikiem.
Umożliwiają czytanie danych jak również
wypisywanie komunikatów i wyników prowadzonych
obliczeń.
Np.: Pascal -
" read(a,b);
{ z klawiatury wprowadzamy : np. 12 5 }
" writeln(a);
{drukujemy na ekranie wartość a (np. 12) }