Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Поняття алгоритму

Читайте также:
  1. I. Поняття зворотної дії в часі закону про кримінальну відповідальність.
  2. III. Поняття комунікації, комунікаційного процесу, методи його удосконалення
  3. Адміністративні стягнення: поняття та види
  4. Алгоритм и требования к алгоритму (свойства алгоритма )
  5. Види тлумачення норм права: поняття, мета
  6. Визначення поняття
  7. Визначте поняття держави. Проаналізуйте класифікацію держави за формою правління та устрою, за політичними режимами.
  8. Відмінності між поняттями „виключення” і „ви­хід” учасника з ТзОВ
  9. Відпустки:поняття та види.
  10. Відпустки:поняття та види.

Слово алгоритм походить від algorithmi – латинської форми написання імені великого математика ІХ ст. Аль Хорезмі, який сформулював правила виконання арифметичних операцій. Спочатку під алгоритмом розуміли лише правила виконання чотирьох арифметичних операцій над багатоцифровими числами. Надалі це поняття стали використовувати для позначення послідовності дій, що приводять до розв’язання поставленого завдання. Під час розв’язання будь-якого завдання ми дотримуємося певної послідовності дій, тобто виконуємо інструкції відповідно до деякого алгоритму. Точне дотримання інструкцій сприяє досягненню зазначеної мети – розв’язання поставленого завдання.

Отже, надалі під алгоритмом будемо розуміти зрозумілі і точні приписи (вказівки) виконавцеві на реалізацію послідовності дій, спрямованих на досягнення зазначеної мети або на розв’язання поставленого завдання.

Алгоритми за формою подання поділяються на: словесні, словесно-формульні, формульні та графічні ( у вигляді блок-схем ).

У словесних алгоритмах використовують лише словесні команди. У словесно-формульних алгоритмах поряд із словесними командами використовують і формули. У формульних алгоритмах використовують лише формули.

Прикладами словесних та словесно-формульних алгоритмів можуть бути: рецепти для приготування їжі, інструкції для виконання певних видів роботи тощо.

Прикладами формульних алгоритмів можуть бути алгоритми для розв’язання різноманітних математичних задач.

За типом розрізняють лінійні, розгалужені, циклічні та змішані алгоритми.

Лінійний алгоритм – це найпростіший тип алгоритму, що містить одну серію простих команд, які виконуються послідовно.

 

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

 

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

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

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

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

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

Любий правильно складений алгоритм має такі властивості:

Ø дискретність (розрив на порції). Порція – це одна закінчена дія (команда алгоритму);

Ø результативність – виконання кожної команди алгоритму має приводити до певного результату;

Ø скінченність (результативність). Алгоритм має містити кінцеву кількість команд і обов’язково давати результат;

Ø зрозумілість (формальність). Алгоритм має бути зрозумілим для виконавця, для якого він складений;

Ø визначеність. Кожна команда алгоритму має бути строго визначена для виконавця. Не повинно бути «недовизначеності» у тлумаченні команди;

Ø масовість. За допомогою одного й того самого алгоритму можна розв’язувати однотипні задачі і робити це неодноразово.

2.3. Приклади алгоритмів

Приклад 1. Побудувати за допомогою циркуля і лінійки бісектрису кута.

Алгоритм побудови має вигляд:

1.Встановити ніжку циркуля у вершину кута А.

2.Провести коло довільного радіуса.

3.Позначити точки перетину В і С із сторонами кута.

4.Провести коло з точки В тим самим радіусом.

5.Провести коло з точки С тим самим радіусом.

6.Позначити точку D їх перетину (що не збігається з вершиною кута).

7.Провести пряму AD. Бісектрису кута побудовано.

Приклад 2. Розв’язати лінійне рівняння ax+b=0.

Пригадаємо, як ми розв’язували такі рівняння. Якщо , то маємо єдиний розв’язок якщо , то будь-які значення х є розв’язком даного рівняння; якщо тоді таке рівняння не має розв’язку.

Запишемо алгоритм у вигляді команд:

1.Перевірити, чи a дорівнює нулю. Якщо так перейти до пункту 5, якщо ні – продовжити обчислення.

2.Розділити b на а.

3.Видати результат: «х=».

4.Закінчити роботу.

5.Перевірити, чи дорівнює b нулю. Якщо так, перейти до пункту 8, якщо ні – продовжити обчислення.

6.Видати результат: «х – будь-яке число».

7.Закінчити роботу.

8.Видати результат: «Рівняння не має розв’язку».

9.Закінчити роботу.

Залежно від значень а і b в алгоритмі будуть виконуватися або команди 1, 2, 3, 4 (якщо ), або 1, 5, 6, 7 (якщо ), або 1, 5, 8, 9 (якщо ).

У наведеному прикладі в алгоритмі передбачено випадок, коли а=0. Якщо не досліджувати чи а і b дорівнюють нулю, то алгоритм буде значно коротшим:

1.Розділити b на a.

2.Видати результат: «х=».

3.Закінчити роботу.

Але в тому випадку, коли виявиться, що а=0, виконавець перерве роботу, тому що виконувати ділення на нуль неможливе, і не буде відомо, який з двох випадків мав місце: «рівняння не має розв’язку», або «має нескінченну множину розв’язків».

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

Отже, під час складання алгоритмів необхідно пам’ятати про властивості алгоритмів.

Приклад 3. Виконати операцію ділення двох натуральних чисел (а:b) шляхом віднімання. Результат ділення подати у вигляді цілої частини і залишку.

Запишемо алгоритм обчислення у вигляді команд:

1.Комірку для зберігання цілої частини частки «обнулити» (k:=0).

2.Порівняти числа а і b (a=b) і якщо умова істинна, то перейти до пункту 3, інакше перейти до пункту 6.

3.Лічильник цілої частини збільшити на одиницю (k:=k+1).

4.Від а відняти b і результат помістити в комірку а (a:=a – b).

5.Перейти до пункту 2.

6.Видати результат: «у комірці k значення цілої частини числа, а в комірці а – залишок від ділення».

Отже, ми розглянули приклади лінійного, розгалуженого та циклічного алгоритмів. Обмежимося цими прикладами, а ви спробуйте самі згадати відомі вам алгоритми.

2.4. Формальне виконання алгоритмів

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

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

Отже, наведемо приклади неформального і формального виконання алгоритму.

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

1.Помножити задумане число на 5.

2.Додати 8.

3.Суму помножити на 2.

За отриманим результатом необхідно вгадати задумане число. Розв’язання цього завдання виконується за допомогою рівняння (х*5+8)*2=а,

де х – задумане число, а – отриманий результат.

Приклад 2. «Угадування» х можна доручити виконавцеві, який зовсім не знає умови задачі. Але йому достатньо дати такий алгоритм:

1.Відняти від результату 16.

2.В отриманій різниці відкинути крайню праву цифру. Отримане число й буде шуканим.

Як бачимо, у другому випадку (приклад 2) виконання алгоритму є формальним.

Наведемо ще один приклад формального виконання алгоритму.

Приклад 3. Першокласникові важко дається множення чисел на 9. Йому можна запропонувати замість множення чисел на 9, виконувати додавання цифр у результуючому числі так, щоб їхня сума дорівнювала 9:

1*9=9 (0+9=9)

2*9=18 (1+8=9)

3*9=27 (2+7=9)

4*9=36 (3+6=9)

5*9=45 (4+5=9)

6*9=54 (5+4=9)

7*9=63 (6+3=9)

8*9=72 (7+2=9)

9*9=81 (8+1=9)

Отже, першокласник має пам’ятати, що сума цифр у результуючому числі завжди має дорівнювати 9. При цьому цифра десятків змінюється від 0 до 8, а цифра одиниць – від 9 до 1

 




Дата добавления: 2014-12-19; просмотров: 40 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.014 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав