Як називаються основні типи алгоритмів. Види алгоритмів. Графічний спосіб опису алгоритмів

В рамках структурного програмування задачі, що мають алгоритмічне рішення, можуть бути описані з використанням наступних алгоритмічних структур:

• Слідування. Передбачає послідовне виконання команд згори донизу. Якщо алгоритм складається лише із структур прямування, він є лінійним.
• Розгалуження. Виконання програми йде однією з двох, кількох чи безлічі гілок. Вибір гілки залежить від умови на вході розгалуження і даних, що надійшли сюди.
• Цикл. Передбачає можливість багаторазового повторення певних дій. Кількість повторень залежить від умови циклу.
• Функція (підпрограма). Команди, відокремлені від основної програми, виконуються лише у разі їхнього виклику з основної програми (з будь-якого її місця). Одна і та ж функція може викликатися з основної програми скільки завгодно разів.

Опис різних алгоритмічних структур мовою блок-схем

Розгалуження if
Це найпростіший тип розгалуження. Якщо результат обчислення висловлювання-умови повертає true (правда), то виконання алгоритму йде по гілці «Так», до якої включені додаткові вирази-дії. Якщо умова повертає false (брехня), виконання алгоритму йде по гілці «ні», тобто продовжує виконуватися основна гілка програми.

Розгалуження if-else
Якщо вираз-умова повертає true (правда), то виконання алгоритму йде по гілці «Так», якщо умова не виконується (false), то виконання по гілці «Ні». За будь-якого результату висловлювання-умови не можна повернутися в основну гілку програми, минаючи додаткові дії.

Розгалуження if-elif-else
Кількість умов може бути по-різному. Якщо виконується перше, то після виконання дій програма переходить до основної гілки, не перевіряючи подальші умови. Якщо перша умова повертає брехню, то перевіряється друга умова. Якщо друга умова повертає правду, виконуються дії, включені в другу гілку конструкції. Остання умова перевіряється лише в тому випадку, якщо жодна до нього не дала в результаті true. Цю алгоритмічну конструкцію (if – elif – else) не слід плутати з алгоритмічною конструкцією «Вибір».

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

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

Цикл for
Цей цикл також називають циклом «Для» (for). У його заголовку вказується три параметри: початкове значення змінної (від), звичайно значення (до) та її зміна за допомогою арифметичної операції на кожному звороті циклу (крок).

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

У алгоритмах команди записуються один за одним у певному порядку. Виконуються вони не обов'язково у записаній послідовності. Можуть існувати внутрішні посилання до різних команд.

Взагалі виконання команд за алгоритмом чимось нагадує настільні ігри, в яких учасники по черзі кидають кубики і ходять полями. Причому на полях можуть бути коментарі у стилі: «Поверніться на 2 клітинки назад» або «Пройдіть на 5 клітинок вперед» (рис. 1).

Мал. 1. Настільна гра ()

Більш складною моделлю виконання алгоритму є відома гра "Монополія" або "Менеджер" (рис. 2).

Мал. 2. Гра «Монополія» ()

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

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

Лінійні алгоритми;

Алгоритми із розгалуженнями;

Алгоритми із повтореннями.

«Монополія»

"Монополія" відноситься до однієї з найпопулярніших настільних ігор. Її правила досить прості та зрозумілі кожному, хто хоч раз у неї грав (рис. 4).

Мал. 4. Гра «Монополія» ()

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

Згідно з офіційними джерелами - компанії Parker Brothers, яка з 1935 року і досі випускає «Монополію», - легендарна настільна гра з'явилася на світ таким чином. У 1934 році безробітний інженер Чарльз Дарроу (рис. 5) запропонував вищевказаній конторі випустити вигадану ним гру про торгівлю нерухомістю.

Мал. 5. Чарльз Дарроу ()

Виявивши у настільній грі 52 дизайнерські помилки, брати Паркери відмовили винахіднику. Той із суто американською підприємливістю вирушив у друкарню, замовив 5 тисяч екземплярів гри та досить швидко їх розпродав. Усвідомивши, що прибуток витікає прямо в них з-під носа, Parker Brothers спішно придбали права на «Монополію», і вже наступного року вона стала настільною грою, що продається в США, а Дарроу - живим втіленням американської мрії.

Однак водночас відомі й більш ранні ігри, що вражає нагадування «Монополію». Виходить, Дарроу просто виявився першим, хто подметушився і отримав патент на «народну» забаву? І так і ні. Розслідування останніх років проливають світло на таємницю походження «Монополії».

У другій половині позаминулого століття у Сполучених Штатах жив та працював політекономіст Генрі Джордж. Він пропонував замінити всі побори одним-єдиним податком – на землю. Перейнявшись його ідеями, у січні 1904 року Мегі отримує патент на настільну гру The Landlord's Game, яка і правилами, і зовнішнім виглядом нагадує нинішню «Монополію». Вважається, що «Гра власника землі» мала два варіанти правил: зігравши партію за чинними законами оподаткування, гравці переходили до моделі, запропонованої Джорджем, і нібито переконувалися в її необхідних перевагах. Таким чином, гра була не розвагою, а інструментом ідеологічної боротьби.

До масового провадження справа не дійшла, зате The Landlord's Game поступово поширилася Північною Америкою в кустарних копіях. Сплеск інтересу до настільної гри припав на роки Великої депресії: тисячі безробітних були раді уявити себе грошовими мішками хоч би за ігровим столом. Поява заповзятливої ​​людини на кшталт Чарльза Дарроу стала справою кількох місяців - і він з'явився, на багато десятиліть надавши славу одноосібного винахідника «Монополії».

Знайшлися, звичайно, і ті, хто вважав за потрібне урвати шматок у правовласників. Неліцензійні «Монополії» затопили Китай. І в нашій країні випускалися і випускаються стрункі ряди клонів - Маклер, Кооператив, Менеджер (рис. 6).

Мал. 6. Гра «Менеджер» ()

У світлі недавнього переосмислення ролі Дерроу у створенні «Монополії» та закінчення дії авторських прав засудити такі компанії не вдасться. Навіть якщо припустити, що жодної Елізабет Мегі у світі не було, правила «Монополії» давно перейшли в суспільне надбання. Втім, частина патенту Hasbro все ще тримає при собі дизайн фішок, графічне оформлення, послідовність клітин на ігровому полі.

Алгоритм, в якому команди виконуються в порядку їх запису, тобто послідовно один за одним, називається лінійним.

Мал. 3. Лампочка ()

Наприклад, лінійним є наступний алго-ритм заміни лампочки, що перегоріла (рис. 3):

1. вимкнути вимикач світла;

2. викрутити лампочку, що перегоріла;

3. вкрутити нову лампочку;

4. увімкнути вимикач, щоб перевірити, чи лампочка горить.

За допомогою блок-схеми цей алгоритм можна зобразити так:

(блок-схему (рис. 7.) див. наприкінці конспекту)

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

Логіку ухвалення рішення можна описати так:

ЯКЩО<условие>, ТО<действия 1>,

Інакше<действия 2>

ЯКЩО будуть гроші, то купи хліба, інакше не купуй.

ЯКЩО будеш сьогодні в центрі, то набери мене, інакше не набирай.

Якщо уроки вивчені, то йди гуляти, інакше вчи уроки.

В деяких випадках<действия 2>можуть отсутствовать. Це може бути пов'язано як з його очевидністю (як, наприклад, у першому прикладі – зрозуміло, що якщо у тебе немає грошей, то хліба ти купити просто не зможеш), так і з відсутністю потреби у ньому.

ЯКЩО<условие>, ТО<действия 1>

ЯКЩО назвався грузде, то лізь у кузов.

ЯКЩО хочеш бути здоровим, ТО загартуйся.

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

Зобразимо у вигляді блок-схеми послідовність дій учня 6 класу, який забув ключі від квартири, яку він уявляє так: «Якщо мама вдома, то я прийду і сяду робити домашнє завдання. Якщо мами вдома немає, то я піду пограти з друзями у футбол, доки не прийде мама. Якщо друзів на вулиці не буде, то покатаюся на гойдалках доти, доки не прийде мама».

(блок-схему (рис. 8.) див. наприкінці конспекту)

Необхідні та достатні умови

Ми вже обговорювали з вами, що існують необхідні та достатні умови.

Прикладом необхідної умови може бути таке:

Щоб стати лікарем, необхідно здобути медичну освіту.

Умова наявності медичної освіти є необхідною для роботи лікарем, проте не є достатньою. Справді, не всі випускники медичних вишів стають лікарями.

Прикладом достатньої умови може стати таке:

Для того, щоб стало прохолодніше, достатньо включити кондиціонер.

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

Звичайно ж, існують необхідні та достатні умови одночасно (такі умови називаються рівносильними). Наприклад:

Для того, щоб настало літо, необхідно і достатньо, щоб закінчилася весна.

Справді, якщо весна закінчилася, настає літо, і якщо весна не закінчилася, то літо наступити неспроможна. Тобто умови закінчення весни та початку літа є рівносильними.

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

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

Наприклад, якщо вам необхідно перебрати ящик з яблуками, щоб відокремити гнилий від стиглих, то нам необхідно повторювати такі дії:

1. Взяти яблуко.

2. Подивитися, чи не гнилий воно.

3. Якщо гнилий - викинути, якщо ні - перекласти в інший ящик.

Виконувати цей набір дій необхідно доти, доки не закінчаться яблука в ящику.

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

Ситуація, за якої виконання циклу ніколи не закінчується, називається зациклюванням.

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

Розглянемо алгоритм роботи будильника на телефоні, який має задзвонити о 8:00 ранку, а потім дзвонити через кожні 10 хвилин, доки його не вимикають.

У цьому випадку його блок-схема виглядає так: (блок-схему (рис. 9) див. в кінці конспекту)

На цьому уроці ми обговорили три типи алгоритмів - лінійні алгоритми, алгоритми з розгалуженнями та алгоритми з повтореннями.

На наступному уроці ми практично обговоримо складання алгоритмів.

Решето Ератосфена

Згадаймо визначення простого натурального числа.

Натуральне число називають простим, якщо вономає лише два дільники: одиницю і саме це число. Інші числа називаються складовими. У цьому число 1 перестав бути ні простим, ні складовим.

Приклади простих чисел: 2, 3, 5, 7

Приклади складених чисел: 4, 6, 8.

У III столітті до нашої ери грецький математик Ератос-фен запропонував наступний алгоритм для знаходження всіх простих чисел, менших від заданого числа п:

1. виписати всі натуральні числа від 1 до n;

2. викреслити 1;

3. підкреслити найменше із невідзначених чисел;

4. викреслити всі числа, кратні підкресленому на попередньому етапі числу;

5. якщо в списку є невідзначені числа, то перейти до кроку 3, в іншому випадку всі підкреслені числа - прості.

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

Розглянемо результат цього алгоритму. Випишемо усі прості числа від 1 до 25.

Випишемо числа від 1 до 25.

Викреслимо 1. Тепер підкреслимо двійку. Викреслимо всі парні числа.

Оскільки не всі числа відзначені, то підкреслюємо 3. Тепер викреслюємо всі числа, які поділяються на 3.

Оскільки не всі числа відзначені, то підкреслюємо 5. Тепер викреслюємо число 25.

Так як не всі числа відзначені, то наголошуємо 7.

Викреслити нічого не можна, але не всі числа відзначені, тому наголошуємо 11.

Викреслити нічого не можна, але не всі числа відзначені, тому підкреслюємо 13. Знову не можна нічого викреслити – підкреслюємо 17, потім 19 та 23.

Тепер усі числа відзначені.

Отримуємо прості числа: 2, 3, 5, 7, 11, 13, 17, 19, 23.

Мал. 7.Блок-схема для зміни лампочки

Мал. 8. Блок-схема дій шестикласника

Мал. 9. Блок-схема роботи будильника

Список літератури

1. Босова Л.Л. Інформатика та ІКТ: Підручник для 6 класу. - М: БІНОМ. Лабораторія знань, 2012

2. Босова Л.Л. Інформатика: Робочий зошит для 6 класу. - М: БІНОМ. Лабораторія знань, 2010

3. Босова Л.Л., Босова А.Ю. Уроки інформатики у 5-6 класах: Методичний посібник. - М: БІНОМ. Лабораторія знань, 2010

1. Інтернет портал «Наша мережа» ()

2. Інтернет портал «Гіпермаркет знань» ()

3. Інтернет портал «kaz.docdat.com» ()

Домашнє завдання

1. §3.4 (Босова Л.Л. Інформатика та ІКТ: Підручник для 6 класу).

2. Стор. 81 завдання 2, 6 (Босова Л.Л. Інформатика та ІКТ: Підручник для 6 класу).

3. Стор. 82 завдання 9, 11, 13, 14 (Босова Л.Л. Інформатика та ІКТ: Підручник для 6 класу).

4. * Стор. 83 завдання 15 (Босова Л.Л. Інформатика та ІКТ: Підручник для 6 класу).

ДУ «Середня школа № 19 відділу освіти

акімата горда Костана»

Єлеусізова Айнаш Досимханівна

Тема:

Цілі:

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

Завдання:

1. Освітні

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

Ознайомити учнів із типами алгоритмів: лінійним, розгалуженим, циклічним;

Навчити уявленню алгоритмів у вигляді блок-схем;

2. Розвиваючі

Активізувати пізнавальну активність учнів через мультимедійні засоби навчання;

Розвивати образне, критичне, дивергентне мислення;

3. Виховні

Підвищення мотивації учнів під час уроку;

Досягнення свідомого рівня засвоєння матеріалу учнями;

Формування почуття колективізму та здорового суперництва;

Формування алгоритмічного мислення.

Вимоги до знань та вмінь:

Знати типи алгоритмів;

знати поняття: лінійний, циклічний алгоритми, що розгалужується;

вміти застосовувати отримані знання під час виконання практичних завдань.

Тип уроку:комбінований.

Технологія:формування комунікативної компетенції;

Методи:

частково-пошуковий, практичний.

інформаційний (словесний);

наочно-ілюстративний;

Хід уроку:

I. Організаційний момент.

Вітання хлопців.

Здрастуйте, хлопці! Сідайте! Який у вас настрій? Якщо гарне -посміхніться всім! Якщо ні – подивіться один на одного та посміхніться! Почнемо урок!

Я представила вам алгоритм у словесній формі. Подивіться на дошку. Той самий алгоритм зображено графічно. Сьогодні на уроці ми навчимося з вами представляти типи алгоритмів за допомогою блок-схем (сторінка фліпчарту 1).

Епіграфом до нашого уроку будуть слова знаменитого французького вченого Гюстава Гійома "Дорогу здолає той, хто йде, а інформатику мислячий".

2. Оголошення цілей уроку.

II. Актуалізація знань учнів

Але перш ніж приступимо до вивчення нового матеріалу. Ми маємо згадати, що вивчали на минулому уроці.

1. Перевірка домашнього завдання.

Перевірити кросворди, вирішені учнями вдома.

Відповіді:

графічний

кінцівка

інформація

виконавець

алгоритм

програмний

комп'ютер

інструмент

2. Робота з Activote (додаток 4) під музично-звукове супроводження (посилання на звуковий файл).

"Повторення - мати вчення" так говорили великі.

Вчитель пояснює алгоритм розв'язання тестових завдань. Діти на місцях працюють з Activote.

III. Вивчення нового матеріалу.

1. Теоретична частина.

Діти, щоб познайомитися з типами алгоритмів, ми з вами зараз переглянемо наступні сторінки фліпчарта, необхідні визначення потрібно записати в зошит.

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

Умовні позначення для блок-схем(Сторінка фліпчарту 5-6)

Початок або кінець програми

- ввід данних

- дії

-Умова рішення програми

-виведення даних або тексту

--цикл із параметром

-Підпрограма

Алгоритми бувають трьох типів: (сторінка фліпчарту 7)

Лінійний

Розгалужується

Циклічний

Лінійні алгоритми

Приклад 1 (Сторінка фліпчарту 9). Казка «Курочка Ряба»

Розгалужуваний алгоритм- алгоритм, у якому залежно від

виконання певної умови відбувається або одна, або інша послідовність дій (сторінка фліпчарту 10)

Повна форма(Сторінка фліпчарту 11)

Неповна форма

приклад 2. (Сторінка фліпчарта 12-13)

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

приклад 3. (Сторінка фліпчарта 12-13)

"Купити морозиво" .

Циклічний алгоритм- (Сторінка фліпчарту 14)

приклад 4.(Сторінка фліпчарта 15.) Алгоритм "Наповнення".

Н очало

Кінець

2. Первинне закріплення.Вирішення завдань-тренінгів(колективно)

(Сторінка фліпчарта 16-17).

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

Тренінг-завдання №1 (сторінка фліпчарту 18).«Почисти килим»

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

Тренінг-завдання №2 (сторінка фліпчарту 19).

Заповнити блок-схему прислів'ям «Хворий – лікуйся, а здоровий – бережись».

Назви тип алгоритму.

Тренінг-завдання №3 (сторінка фліпчарту 20).

Перевірити, перетягнувши рисунок на вільне місце.

Фізкультхвилинка(Сторінка фліпчарта 21).

Ми руками поведемо -

Наче в морі ми пливемо.

Один два три чотири -

Ось ми до берега припливли,

Щоб кісточки розім'яти,

Почнемо нахили виконувати -

Праворуч, ліворуч, праворуч, ліворуч.

Не забудемо і сісти -

Один два три чотири,

Ми виконали алгоритм і досягли певної мети: відпочили, розслабилися.

4. Виконання практичної роботи.Робота з різнорівневих карток.

(Сторінка фліпчарта 22).

І повертаємося до слів французького вченого Гюстава Гійома "Дорогу здолає той, хто йде, а інформатику мислячий".

Вкажіть стрілки, до якого типу алгоритму належать дані зображення.

Дайте назви алгоритмам (сторінка фліпчарту 23).

Заповнити таблицю двома прикладами на кожний тип алгоритму (сторінка фліпчарту 24).

Paint

Варіант 1.(сторінка фліпчарту 25).

"Посадка саджанця".

Варіант 2.(сторінка фліпчарту 26).

IV . Домашнє завдання(Сторінка фліпчарта 27).

1. Вивчити конспект.

2. Намалювати на А4 форматі приклад циклічного алгоритму та блок – схему до казки «Колобок».

V . Підсумок уроку.(Сторінка фліпчарта 28).

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

VI . Рефлексія. .(Сторінка фліпчарта 29).

Що вам сьогодні сподобалося на уроці?
– Що ви запам'ятали?
– Що було цікавого?

VII. Оцінювання.

Сьогодні у вас будуть замість позначок - смайлики, якими я оціню ваші успіхи на уроці.

Додаток 2

Технологічна карта №1

Тема урока: Типи алгоритмів: лінійні, циклічні, що розгалужуються.

Цілі уроку : Навчимося складати класифікацію типів алгоритмів;

Навчимося представляти алгоритми у вигляді блок-схем .

1. Перевірка домашнього завдання.

Виконання тестових завдань з тестера

2. Теоретична частина

Умовні позначення для блок-схем:

Початок або кінець програми

- ввід данних

- дії

-Умова рішення програми

-виведення даних або тексту

--цикл із параметром

-Підпрограма

- стрілки – напрямок процесу

Алгоритми бувають трьох типів: -лінійний

Розгалужується

Циклічний

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

приклад 1 . Казка «Курочка Ряба»

Розгалужуваний алгоритм- Алгоритм, в якому в залежності від виконання деякої умови здійснюється або одна, або інша послідовність дій.

У словесному описі алгоритму, що розгалужується, використовуються слова "якщо", "то", "інакше".

Повна форма: «якщо виконується умова, то … інакше …» . Дії передбачені і під час виконання умови, і за його невиконанні.

Неповна форма: «якщо виконується умова, то …» Дії передбачені лише за виконання умови. У разі невиконання умови.

приклад 2.

Якщо пішов дощ, то відкрийте парасольку, інакше парасольку покладіть у сумку (повна форма алгоритму, що розгалужується);

Якщо пішов дощ, то відкрийте парасольку (неповна форма алгоритму, що розгалужується).

приклад 3.

"Купити морозиво" .

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

П
ример 4. Алгоритм "Наповнення".

початок

1. Поки цебро неповне, повторювати:

2. Налити у відро кухоль води.

Кінець

3. Вирішення завдань-тренінгів(Колективна робота).

Тренінг-завдання №1.

Скласти алгоритм «Почисти килим».

Тренінг-завдання №2.

1. Назви тип алгоритму.

2. Заповни алгоритм.

Записати за допомогою блок-схеми прислів'я «Хворий – лікуйся, а здоровий – бережись».

Тренінг-завдання №3.

Хлопчик вчить напам'ять чотиривірш, заданий з літератури. Він один раз прочитує чотиривірш і намагається відтворити його з пам'яті. Так він робитиме доти, доки не розкаже чотиривірш без жодної помилки. Скласти дії хлопчика як блок-схеми.

4. Фізкультхвилинка.

Ми руками поведемо -

Наче в морі ми пливемо.

Один два три чотири -

Ось ми до берега припливли,

Щоб кісточки розім'яти,

Почнемо нахили виконувати -

Праворуч, ліворуч, праворуч, ліворуч.

Не забудемо і сісти -

Один два три чотири,

На рахунок п'ять – за парти сісти.

Приклади

лінійного алгоритму

Приклади

розгалужуваного алгоритму

Приклади

циклічного алгоритму

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

Варіант 1.(сторінка фліпчарту 25).

"Посадка саджанця".

Варіант 2.(сторінка фліпчарту 26).

Епізод із казки «Гусі-лебеді».

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

Алгоритмізація

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

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

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

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

Комп'ютер не вміє вирішувати завдання, він здатний лише виконувати прості дії у вказаному порядку. "Як же калькулятор?" - Запитайте ви. Він також є плодом праць програмістів, які створили програму, яка використовує певні алгоритми отримання необхідних результатів. Розглянемо абстрактну ситуацію. Що слід зробити, якщо попросити знайти коріння квадратного тричлена людини, яка не знайома з методами розв'язання рівнянь?

Очевидно, що його необхідно навчити розв'язувати квадратні рівняння. Відбувається це за такою схемою:

1. Вибрати спосіб розв'язання.
2. Вивчити всі деталі вибраного способу.
3. Пояснити перші два пункти майбутньому виконавцю зрозумілою йому мовою.

Потім можна буде давати виконавцю завдання рішення квадратного рівняння. І якщо перші два кроки прості та зрозумілі - всі способи рішення описані у відповідній літературі, то третій крок є складністю.

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

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

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

Основні властивості алгоритму

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

Визначеність. Кожен крок має бути зрозумілим і однозначним як за змістом, так і в ключі дії, яку потрібно зробити.

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

Масовість. Будь-який алгоритм, розроблений для вирішення будь-якої задачі, повинен бути застосовним до всіх завдань цього для всіх допустимих вихідних даних.

Можливості комп'ютера

p align="justify"> Для правильного створення алгоритмів під комп'ютери важливо розуміти їх можливості. Розглянемо спочатку величини, із якими працює ЕОМ. Загалом їх можна розділити на числові та текстові, постійні та змінні.

Під постійними числами розуміються всі числа: 3,15, 100, 10 5 їх особливістю є незмінність протягом всієї роботи програми. Змінні величини змінюють своє значення під час виконання коду і позначаються, як правило, літерами: x, y, max, min тощо.

Текстові змінні аналогічно числовим бувають постійними чи змінними. У першому випадку це просто текст: "добре", "a і b" та ін. У другому - таке ж символьне позначення, як і числових змінних: name, city і т.п. під зберігання такої змінної.

Операції, які здатний виконувати комп'ютер:

1. Зчитувати дані з пристроїв уведення (клавіатура, миша, файли).
2. Обчислення значень з використанням математичних функцій: додавання, віднімання, sin, cos, ln і т. д. - у кожній мові програмування свій набір вбудованих функцій.
3. Виведення даних (на екран, на папір, мережевий інтерфейс).
4. Перехід між етапами виконання програми.
5. Порівняння двох величин (більше, менше, одно).

Це основні операції, які можуть виконуватись більшістю мов програмування.

Способи опису алгоритмів

Словесний. Це найпростіший спосіб. Його прикладом може бути кулінарний рецепт. Допускається використання найпростіших математичних формул.

графічний. Опис за допомогою схем. Це особливий спосіб запису алгоритмів з використанням свого роду загальноприйнятої алгоритмічної мови - фігур і блоків, що мають певне значення: прямокутник - простий дію, похилий паралелограм - введення/виведення, ромб - умова і т.д.

Використання алгоритмічної мови. Аналогічно графічному, це також особливий спосіб запису алгоритму. Існує безліч алгоритмічних мов. Їхні правила не є суворими, інакше це була б мова програмування. Розглянемо приклад алгоритму розрахунку зарплати залежно від стажу, записаний з допомогою алгоритмічного мови.

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

Види алгоритмів

Існує безліч алгоритмів, створених для вирішення різних завдань. Наприклад, будь-який підручник вищої математики містить сотні алгоритмів: розв'язання системи лінійних рівнянь, знаходження екстремумів функції, обчислення інтеграла і т. д. Однак при детальному розгляді їх структури виявляється, що всі алгоритми можна поділити на кілька видів. Розглянемо ці види алгоритмів із прикладами.

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

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

Докладніше про кожен алгоритм обчислення з прикладами буде розказано нижче.

Принципи алгоритмізації

1. Визначити вихідні дані.
2. Вибрати спосіб розв'язання.
3. Розбити вибрані методи на кроки виходячи з можливостей комп'ютера (мови програмування).
4. Виконати алгоритм як схеми, визначивши чіткий порядок кроків.
5. Виведення результатів обчислень.
6. Визначити перехід до виходу схеми.

Налагодження алгоритму

Людина припускається помилок, і це факт. Головним параметром будь-якого алгоритму має бути правильність його роботи. Налагодження - це процес виявлення та виправлення помилок алгоритму. І тому береться певний набір вихідних даних, званих тестовими. Вони є, зазвичай, всілякі типи вихідних даних. Наприклад, якщо на введення подається число, то алгоритм слід перевірити на коректну роботу з урахуванням: позитивних, негативних, цілих та дійсних чисел, нульові значення тощо.

Головним інструментом для перевірки точності алгоритму залишається людський мозок. Звичайно, допустиме використання інших комп'ютерних інструментів для автоматизації перевірки, але так чи інакше підготовкою тестів та аналізом результатів займається людина. У такому разі виникає питання, а навіщо потрібний алгоритм, якщо людина виконує все сама? Тому, що головне завдання алгоритму – багаторазове вирішення певного типу задач.

Лінійні алгоритми

Лінійним є алгоритм, у якому кроки йдуть послідовно один за одним. Будь-який алгоритм, що не містить розгалужень та циклів, є лінійним. Розглянемо приклад алгоритму, який вирішує таке завдання: у двох клітинах сидять вовк і заєць, потрібно поміняти їх місцями.

Ключем до розв'язання цієї задачі є додаткова клітина temp, яку слід використовувати, щоб поміняти місцями тварин.

Розгалужувані алгоритми

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

Наведемо приклад алгоритму для розв'язання задачі про знаходження найбільшого серед трьох чисел.

Циклічний алгоритм

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

1. Привласнення початкового значення змінних. Без виконання цієї умови цикл, швидше за все, не зможе працювати або буде робити помилки.
2. Блок обчислення результатів. Це головне тіло циклу.
3. Перевірка умови закінчення циклічного процесу. Якщо забути вказати умову, за якої слід завершити цикл, алгоритм виконуватиметься нескінченно.
4. Зміна змінних. Цей блок набирає чинності після перевірки умови закінчення, якщо воно було хибним. Якщо забути про цей блок, цикл буде вічно виконувати одну дію і ніколи не завершиться. Тому важливо, щоб змінні зазнавали будь-яких змін на кожній ітерації циклу.

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

Побудуємо циклічний алгоритм з прикладу знаходження факторіалу числа N.

Інші типи алгоритмів

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

• Механічні алгоритми. Наприклад, робота двигуна внутрішнього згоряння або конвеєра складального.
• Ймовірнісні алгоритми. Їхня робота заснована на теорії ймовірності та математичної статистики.
• Евристичні алгоритми. Використовують практичні міркування у роботі, без суворого математичного обгрунтування.
• Генетичні алгоритми. Застосовують біологічні ідеї у своїй роботі.

Насправді найбільш поширені такі форми представлення алгоритмів:

· словесна (записи природною мовою);

· графічна (зображення з графічних символів);

· псевдокоди (напівформалізовані описи алгоритмів умовною алгоритмічною мовою, що включають як елементи мови програмування, так і фрази природної мови, загальноприйняті математичні позначення та ін);

· Програмна (тексти мовами програмування).

Словесний спосібзапису алгоритмів є опис послідовних етапів обробки даних. Алгоритм задається у довільному викладі природною мовою. Наприклад. Записати алгоритм знаходження найбільшого загального дільника (НДД) двох натуральних чисел.

Алгоритм може бути наступним:

· Задати два числа;

· Якщо числа рівні, то взяти будь-яке з них як відповідь і зупинитися,

в іншому випадку продовжити виконання алгоритму;

· Визначити більше з чисел;

· Замінити більше з чисел різницею більшого і меншого з чисел;

· Повторити алгоритм з кроку 2.

Описаний алгоритм застосовується до будь-яких натуральних чисел і має призводити до вирішення поставленого завдання.

Словесний спосібне має широкого поширення з таких причин:

· Такі описи строго не формалізуються;

· страждають багатослівністю записів;

· Допускають неоднозначність тлумачення окремих приписів.

Графічний спосібуявлення алгоритмів є компактнішим і наочним порівняно зі словесним.

Таке графічне уявлення називається схемою алгоритмуабо блок-схемою.

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

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

1) Блок початку-кінець

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

2) Блок дії

Виконання однієї чи кількох операцій, обробка даних будь-якого виду (зміна значення даних, форми подання, розташування). Усередині фігури безпосередньо записують самі операції, наприклад, операцію присвоєння: a = 10*b + c

3) Логічний блок

Відображає рішення або функцію перемикача з одним входом і двома або більше альтернативними виходами, з яких тільки один може бути обраний після обчислення умов, визначених усередині цього елемента. Вхід елемент позначається лінією, що входить зазвичай у верхню вершину елемента. Якщо виходів два або три, то зазвичай кожен вихід позначається лінією, що виходить з вершин, що залишилися (бічних і нижньої). Якщо виходів більше трьох, їх слід показувати однією лінією, що виходить з вершини (частіше нижньої) елемента, яка потім розгалужується. Відповідні результати обчислень можуть записуватись поруч із лініями, що відображають ці шляхи. Приклади рішення: у загальному випадку – порівняння (три виходи: >,<, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов).

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

Типи алгоритмів

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

Лінійний алгоритм - набір команд (вказівок), що виконуються послідовно в часі один за одним.

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