Поняття алгоритму. Властивості та способи алгоритмів. Базові структури алгоритмів



Скачати 52.96 Kb.
Дата конвертації20.11.2016
Розмір52.96 Kb.

Лекція № 1


Тема: Поняття алгоритму. Властивості та способи алгоритмів. Базові структури алгоритмів.

План





  1. Поняття алгоритму. Властивості алгоритму. Форми подання алгоритмів.

  2. Базові структури алгоритмів




  1. Алгоритм – чітко задана послідовність кроків, які мають бути виконані для розв’язання завдання.


Властивості алгоритму:

    1. Масовість. Алгоритм повинен бути застосованим до будь – яких елементів з множини вихідних даних.

    2. Визначеність. Операції, які використовуються в алгоритмі, не повинні мати двоякого тлумачення; не повинно виникати питання: що саме і як треба робити? Порядок виконання операцій має бути строго визначеним.

    3. Дискретність. Процес розв’язування алгоритму повинен складатися з окремих завершених операцій, які виконуються послідовно і за скінчений час.

    4. Результативність. Виконання послідовності операцій алгоритму повинно приводити до цілком конкретного результату.

    5. Формальність. Будь – який виконавець, здатний сприймати і виконувати вказівки алгоритму ( навіть не розуміючи їх змісту), діючи за алгоритмом, може виконати постановлене завдання.


Форми подання алгоритмів (способи опису алгоритмів):

  1. словесний;

  2. формульний;

  3. графічний;

  4. алгоритмічною мовою.

Приклад опису алгоритму у словесній формі



Задача. Вказати послідовність дій, які необхідно виконати для обчислен­ня виразу (ах+b)х+с при заданих значеннях а, b, с, х.

Алгоритм можна описати таким чином:

Приклад 1.

1. Помножити а на х

2. До отриманого результату додати b.

3. Отриманий результат помножити на х

4. До отриманого результату додати с.

5.Кінець.

Приклад опису алгоритму у графічній формі

Для опису використовуються блок-схеми.

1. Блок-схема

Найбільш наочною формою запису алгоритмів є блок-схеми (графічний спосіб запису алгоритму).

Є два різновиди графічних схем: а) блок схеми; б) структурні схеми.

Блок схема складається з блоків декількох видів: овальних блоків "початок" і "кінець"; блоків "введення і виведення даних" у вигляді паралелограмів, прямокутних блоків (процес, присвоєння).

У блоці процес описують одну чи декілька команд присвоєння. Формули записують довільним чином (тобто, символ множення можна не писати).

Блоки зєднують лініями, які описують послідовність виконання команд. Ці лінії називають лініями потоків передавання інформації.Природні напрямки потоків зверху-вниз і зліва-направо. Якщо напрямок потоку інший, то лінія повинна мати стрілку.



2. Структурна схема

Усі команди записують у прямокутних блоках, накладених один на одний. Порядок розміщення блоків визначає порядок виконання команд.
Алгоритм <назва>

ввести а,b,с

р:=2*( а+b)

d:= a* b* с

вивести р,d



б) структурна схема

  1. Базові структури (алгоритмічні конструкції) алгоритмів



Існують три алгоритмічні конструкції:

  1. Лінійні ( прості, проходження );

  2. Розгалуження ( умовні, розвилка );

  3. Циклічні (цикл).


При описуванні базових структур для їх графічного подання у вигляді схем використовуються спеціальні позначення.

Прямокутником позначається дія, яку необхідно виконати, тобто виконати розрахунки за даними формулами.



мал.1

Ромбом позначається перевірка значення логічного виразу. У логічних виразах можуть використовуватися логічні операції «і», «або», «ні». Логічний вираз може набувати одне з двох зна­чень — істина або фальш . Іноді замість «істина» пишуть «так», замість «фальш» — «ні».


мал.2
Перевірка значення логічного виразу звичайно зводиться до перевірки виконання чи невиконання деяких умов. Розглянемо базові структури.


    1. Проходження (лінійний, простий).

Означає, що дії повинні виконуватися одна за одною.



мал.3

Наприклад: Розглянемо алгоритм Ранок.

Алгоритм Ранок

1. Встати о 7 – й годині.

2. Виконати гімнастичні вправи.

3. Умитися.

4. Поснідати.

5. Вийти з дому о 8 - й годині.


  1. Розгалуження ( умовний, розвилка).

Якщо команда містить якусь умову то такий алгоритм називається розгалуженим. Умову в інформатиці називають логічним виразом. Команду розгалуження утворюють за допомогою логічного виразу і трьох службових слів « ЯКЩО — ТО — ІНАКШЕ ». Вона має вигляд:

якщо логічний вираз, то команда 1, інакше команда 2.

Команда розгалуження – це вказівка виконати одну з двох команд: команду 1, якщо логічний вираз істинний, або команду 2, якщо логічний вираз фальшивий.



мал. 4

Наприклад: Розглянемо алгоритм Вечір.

Алгоритм Вечір

1. Повернутися зі школи додому після уроків.

2. Пообідати.

3. Якщо погода гарна, то попрацювати в саду, інакше піти в бібліотеку, взяти книжки, повернутися додому.

4. Зробити уроки.

5. Повечеряти.

6. Якщо є цікава телепередача, то подивитися телевізор, інакше почитати книжку.

7. Лягти спати.

Алгоритм складається з семи команд , команди 3 і 6 – це команди розгалуження, команда 3 містить серію команд. Простежимо за виконавцем алгоритму. Якщо погода гарна і є цікава телепередача, то після уроків працюватимете в саду, зробить уроки й подивиться телевізор.
3.Циклічні алгоритми.

Циклом називають повторне виконування однієї й тієї ж самої дії, або блоку дій, який називають тілом циклу, доти , доки логічний вираз, що знаходиться в циклі, залишатиметься істинним.

Цикл має такий вигляд:

доки логічний вираз, виконати команду

Цикл, зображений на мал. 5, називається «ЦИКЛ — ДОКИ». Спочатку — на першому кроці циклу — відбувається перевірка значення логічного виразу. Якщо він істинний, то виконується тіло циклу.

Потім — на другому кроці циклу — знову робиться перевірка значення логічного виразу і, якщо він все ще зали­шається істинним, знову виконується тіло циклу. Цикл завер­шується, коли значення логічного виразу стає фальшивим.



мал. 5

Можливі ситуації, коли тіло циклу не виконуватиметься жод­ного разу. Це відбувається тоді, коли на першому кроці циклу значення логічного виразу є фальшивим.

Наприклад: Розглянемо алгоритм Школа.

  1. Іти на перший урок.

  2. Доки не закінчилися уроки, іти на наступний урок.

  3. Іти додому.

Скласти алгоритм наповнення водою 10- літрового відра, користуючись 3- літровою банкою.

Розглянемо алгоритм Наповнити.

  1. Наповнити банку водою.

  2. Доки відро неповне, перелити воду з банки у відро, наповнити банку водою.

Прості команди (перелити та наповнити) він виконує в циклі чотири рази. Відро наповнить , у цьому випадку 2 л води проллє на землю.


База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка