Politechnika Poznańska Wydział Maszyn Roboczych i Transportu
Instytut Maszyn Roboczych i Pojazdów Samochodowych
Wykład 15
Projektowanie algorytmów
dr inż. Michał Maciejewski
michal.maciejewski@put.poznan.pl
Systemy informacyjno-informatyczne
w transporcie
2
Plan wykładu
• Algorytm
• Schemat blokowy
• Zadania
Algorytm
• Skończony, uporządkowany ciąg jasno
zdefiniowanych czynności, koniecznych do
wykonania pewnego rodzaju zadań
• Algorytm ma przeprowadzić system z pewnego
stanu początkowego do pożądanego stanu
końcowego
• Badaniem algorytmów zajmuje się algorytmika
• Jako przykład stosowanego w życiu codziennym
algorytmu podaje się często przepis kulinarny
– sposób przyrządzenia potrawy podany jest krok po
kroku zdefiniowane
– istnieć kilka różnych przepisów dających na końcu
bardzo podobną potrawę
3
Algorytm
• Algorytm moża przedstawić na wiele różnych
sposobów
– w postaci opisu słownego,
– w postaci listy kroków,
– w postaci schematu blokowego (postać graficzna
algorytmu),
– za pomocą jednego z języków formalnych.
4
Algorytm
• MIN – problem:
– Znaleźć minimum spośród dwóch liczb całkowitych
a i b.
5
Algorytm
• MIN – opis słowny:
Po wczytaniu danych wejściowych a i b porównać
wprowadzone liczby. Jeśli a < b, to min = a.
Wyprowadzić wynik. W przeciwnym wypadku, jeśli a
>= b, to min = b. Wyprowadzić wynik.
6
Algorytm
• MIN – lista kroków:
Krok 1.
Wprowadź dwie liczby całkowite a i b.
Przejdź do kroku 2.
Krok 2.
Jeśli a < b, to podstaw min = a,
wyprowadź
wynik min = a. Przejdź do kroku 5. W
przeciwnym
przypadku przejdź do kroku 3.
Krok 3.
Sprawdź, czy b < a? Jeśli tak, to podstaw
min = b,
wyprowadź wynik min = b. Przejdź do kroku 5.
W przeciwnym przypadku przejdź do kroku 4.
Krok 4. Podstaw min = a, wyprowadź wynik min = a = b.
Przejdź do kroku 5.
Krok 5. Zakończ program.
7
Algorytm
• MIN – schemat blokowy
8
Algorytm
• MIN – Visual Basic
wariant A
wariant B
9
10
Plan wykładu
• Algorytm
• Schemat blokowy
• Zadania
Schemat blokowy
• Forma opisu algorytmu cechująca się:
– prosta zasada budowy
– elastyczność zapisów
– możliwość zapisu z użyciem składu wybranego
języka programowania
– łatwa kontrola poprawności algorytmu
11
Schemat blokowy
• Elementy budowy
– strzałka – wskazuje jednoznacznie powiązania i ich
kierunek,
– operand - prostokąt, do którego wpisywane są
wszystkie operacje z wyjątkiem instrukcji wyboru,
– predykat - romb, do którego wpisywane są
wyłącznie instrukcje wyboru,
– etykieta - owal służący do oznaczania początku
bądź końca sekwencji schematu (kończą, zaczynają
lub przerywają/przenoszą schemat).
12
Schemat blokowy
• Blok graniczny
– oznacza on początek, koniec, przerwanie lub
wstrzymanie wykonywania działania, np. blok startu
programu
13
Schemat blokowy
• Blok wejścia-wyjścia
– przedstawia czynność wprowadzania danych do
programu i przyporządkowania ich zmiennym dla
późniejszego wykorzystania, jak i wyprowadzenia
wyników obliczeń, np. podaj a, wypisz min.
14
Schemat blokowy
• Blok obliczeniowy
– oznacza wykonanie operacji, w efekcie której zmienią
się wartości, postać lub miejsce zapisu danych, np.
min = b.
15
Schemat blokowy
• Blok decyzyjny
– przedstawia wybór jednego z dwóch wariantów
wykonywania programu na podstawie sprawdzenia
warunku wpisanego w ów blok, np. a < b.
16
Schemat blokowy
• Łącznik wewnętrzny
– służy do łączenia odrębnych części schematu
znajdujących się na tej samej stronie, powiązane ze
sobą łączniki oznaczone są tym samym napisem, np.
A1, 7.
17
Schemat blokowy
• Algorytmy sprawdzenia poprawności numeru
karty kredytowej
– Numer karty kredytowej składa się z szesnastu cyfr.
Pierwsze sześć cyfr to numer identyfikujący bank.
Kolejne dziewięć cyfr ustala sam bank wydający
kartę, a ostatnia cyfra jest cyfrą kontrolną.
– Aby zweryfikować poprawność numeru musimy
postąpić według określonych zasad (algorytm)
18
Schemat blokowy
• Algorytmy sprawdzenia poprawności numeru
karty kredytowej
1. Pomnożyć kolejne cyfry przez odpowiednie wagi
2. Jeśli wynik mnożenia jest większy lub równy 10
należy od otrzymanej liczby odjąć 9
3. Wyniki mnożenia po wykonaniu korekty (2) należy
zsumować
4. Sumę należy podzielić modulo przez 10
5. Jeśli reszta wynosi 0 to numer karty jest poprawny
19
20
Brak
danych wej.
wagi=[2,1,...,1]
suma=0
i=1
Nr musi
być być w ‘’
Nr musi
mieć 16 zn.
Start
Czy podano
argument ?
Czy wpisano
tekst ?
Czy napis ma
16 znaków ?
Stop
Numer
poprawny
ity_skladnik=ity_skladnik-9
Czy
ity_skladnik >= 10
ita_cyfra={i-ty znak napisu}
ity_skladnik=ita_cyfra* {i-ta waga}
Czy i > 16
suma=suma+ity_skladnik
i=i+1
Czy reszta = 0 ?
reszta= suma mod 10 {ostatnia cyfra}
Numer
błędny
Nie
Nie
Nie
Tak
Nie
Tak
Nie
Nie
Tak
Tak
Tak
Tak
Schemat blokowy
• Przykład „nieprogramistyczny”: GTD
– Getting Things Done - popularna metoda organizacji
zajęć, oparta o kolekcjonowanie spraw i zarządzanie
listami zadań i projektów; autorstwa Davida Allena
21
22
Schemat blokowy
• Przykład „nieprogramistyczny”: kocioł gazowy
– schemat działania kotła gazowego sterowanego
termostatem
23
24
25
Plan wykładu
• Algorytm
• Schemat blokowy
• Zadania
Zadanie 1
• Problem
– Obliczanie sumy 3 liczb
26
Zadanie 1
• Schemat blokowy
27
Zadanie 2
• Problem
– Czy liczba jest parzysta?
28
Zadanie 3
• Problem
– Czy liczba mieści się w przedziale <0;100>?
29
Zadanie 4
• Problem
– Oblicz pierwiastki równania kwadratowego
30
Zadanie 5
• Problem
– Znaleźć minimum spośród n (n>0) wczytanych liczb
a
0
, a
1
, … a
n-1
. Wypisać minimum
31
32
33
Dziękuję…