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

[e-mail]

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ę…