Типи алгоритмів: лінійні, циклічні, що розгалужуються. Види алгоритмів та приклади Що таке типи алгоритмів
Алгоритми можуть бути простими, складними, однак у всіх є спільні риси. Ось з цих рис і прийнято виділяти три типи алгоритмів, з якими ми й познайомимося.
У алгоритмах команди записуються один за одним у певному порядку. Виконуються вони не обов'язково у записаній послідовності. Можуть існувати внутрішні посилання на різні команди.
Взагалі виконання команд за алгоритмом чимось нагадує настільні ігри, в яких учасники по черзі кидають кубики і ходять полями. Причому на полях можуть бути коментарі в стилі: «Поверніться на 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 класу).
Ціль : Ознайомити студентів із основами алгоритмізації.
Навчальні питання:
1. Алгоритм та його властивості. Способи запису алгоритмів.
2. Основні типи алгоритмів. Блок-схеми типових алгоритмів.
Вивчивши цю тему, студент має:
Знати:
· властивості алгоритму;
· Блоки для побудови схем;
· Основні типи алгоритмів;
Вміти :
· Будувати алгоритми за умовою завдання;
Поняття алгоритму
Поняття алгоритму – одне з фундаментальних понять інформатики, яке історично оформилося у самостійну дисципліну «теорія алгоритмів», близьку до іншої дисципліни «математична логіка». З іншого боку, дисципліну «теорія алгоритмів» можна розглядати проміжною між двома дисциплінами: математикою та інформатикою, пов'язаною з розділом програмування.
Алгоритмізація відноситься до загальних методів інформатики, що має велике значення при вирішенні складних завдань. Перш ніж написати програму розв'язання задачі на ЕОМ, необхідно переглянути послідовність дій, які повинні бути виконані для правильного розв'язання задачі.
Алгоритм це послідовність арифметичних, логічних та інших операцій, необхідні виконання на ЕОМ.
Для отримання правильного результату алгоритм повинен бути складений так, щоб під час його виконання всі команди трактувалися однозначно. Тому з'явилися обов'язкові вимоги, які мають враховуватись при складанні алгоритмів. Вимоги формулюються як властивостей.
Алгоритм може бути завжди результативним, мати властивість повторюваності і може бути розрахований на конкретного виконавця. У техніці таким виконавцем є ЕОМ. Для забезпечення можливості реалізації на ЕОМ алгоритм повинен бути описаний мовою зрозумілою ЕОМ, тобто машинною мовою. Проте, перш ніж уявити алгоритм мовою зрозумілою для ЕОМ (машинному мові), необхідно написати програму з допомогою алгоритмічного мови програмування.
Алгоритм може бути представлений у різний спосіб, зокрема:
1) словесно (вербальний опис);
2) таблично;
3) як блок-схеми;
4) алгоритмічною мовою.
Досить поширеним способом представлення алгоритму є його запис алгоритмічною мовою, що представляє в загальному випадку систему позначень і правил для одноманітного і точного запису алгоритмів та їх виконання. Цей спосіб представлення алгоритму передбачає запис його як програми.
Програма– це запис алгоритму мовою програмування, що веде до кінцевого результату за кінцеве число кроків.
Переважно до запису алгоритмічною мовою представити алгоритм у вигляді блок-схеми. Для побудови алгоритму як блок-схеми необхідно знати призначенні кожного з блоків. У таблиці 13. наводяться типи блоків та його призначення.
Таблиця 13
Призначення блоку | Коментар (Блок відповідає оператор) |
||
Початок чи кінець блок-схеми | |||
Введення або виведення даних | введення/виведення |
||
Процес (зокрема обчислювальний) | привласнення |
||
| |||
| Модифікатор циклу |
5.2. Основні типи алгоритмів
Алгоритмізація постає як набір певних практичних прийомів, особливих специфічних навичок раціонального мислення у межах заданих мовних засобів. Алгоритмізація обчислень передбачає вирішення задачі у вигляді послідовності дій, тобто рішення, представлене у вигляді блок-схеми. Можна виділити типові алгоритми. До них відносяться: лінійні алгоритми, алгоритми, що розгалужуються, циклічні алгоритми.
Лінійні алгоритми
Лінійний алгоритм є найпростішим. У ньому передбачається послідовне виконання операцій. У цьому алгоритмі не передбачено перевірку умов або повторень.
Приклад : Обчислити функцію z = (х-у) / x + y2.
Скласти блок-схему обчислення функції лінійного алгоритму. Значення змінних х, у можуть бути будь-які, крім нуля, вводити їх із клавіатури.
Рішення: Лінійний алгоритм обчислення функції заданий як блок-схеми на рис.8. При виконанні лінійного алгоритму значення змінних уводяться з клавіатури, підставляються в задану функцію, обчислюється результат, а потім виводиться результат.
Рис.8. Лінійний алгоритм
Призначення блоків у схемі на рис.8:
· Блок 1 у схемі служить як логічний початок.
· Блок 3 представляє арифметичну дію.
· Блок 4 виводить результат.
· Блок 5 у схемі служить як логічне завершення схеми.
Алгоритми розгалужень
Розгалужуваний алгоритм передбачає перевірку умов вибору рішення. Відповідно, в алгоритмі з'являться дві гілки для кожної умови.
У прикладі розглядається алгоритм, що розгалужується, де в залежності від умови вибирається один з можливих варіантів рішень. Алгоритм представляється як блок-схеми.
Приклад : При виконанні умови x>0 обчислюється функція: z= ln x+ y, інакше, а саме, коли х = 0або x<0 , обчислюється функція: z= x+ y2 .
Скласти блок-схему обчислення функції алгоритму розгалуження. Значення змінних х, у можуть бути будь-які, вводити їх із клавіатури.
Рішення : На рис.9 представлений алгоритм, що розгалужується, де в залежності від умови виконається одна з гілок. У блок-схемі з'явився новий 3 блок, який перевіряє умову завдання. Інші блоки знайомі з лінійного алгоритму.
https://pandia.ru/text/78/136/images/image008_57.gif" width="300" height="360 src=">
Рис.9. Алгоритм розгалуження
Приклад : Знайти максимальне значення трьох різних цілих чисел, введених з клавіатури. Скласти блок-схему розв'язання задачі.
Рішення : Цей алгоритм передбачає перевірку умови. Для цього вибирається будь-яка з трьох змінних та порівнюється з іншими двома. Якщо вона більша, то пошук максимального числа закінчено. Якщо умова не виконується, то порівнюються дві зміни, що залишилися. Одна з них буде максимальною. Блок-схема цієї задачі представлена на рис 10.
https://pandia.ru/text/78/136/images/image010_48.gif" width="492" height="456 src=">
Мал. 10. Блок-схема пошуку максимуму
Циклічні алгоритми
Циклічний алгоритм передбачає повторення однієї операції або кількох операцій, залежно від умови завдання.
З циклічних алгоритмів виділяють два типи:
1) із заданою кількістю циклів або з лічильником циклів;
2) кількість циклів невідома.
Приклад : У циклі обчислити значення функції z=x*yза умови, що одна із змінних x змінюється у кожному циклі на одиницю, а інша змінна у не змінюється і може бути будь-яким цілим числом. В результаті виконання циклу при початковому значенні змінної х = 1можна отримати таблицю множення. Кількість циклів може бути будь-якою. Скласти блок-схему розв'язання задачі.
Рішення : У прикладі кількість циклів задається. Відповідно, вибирається алгоритм циклів першого типу. Алгоритм цього завдання наводиться на рис. 11.
У другому блоці вводяться кількість циклів n і будь-які цілі числа х, y .
У блок-схемі з'явився новий блок 3, в якому змінна i вважає кількість циклів, після кожного циклу збільшуючись на одиницю, поки лічильник не буде дорівнює i=n . При i=n буде виконано останній цикл.
У третьому блоці вказується діапазон зміни лічильника циклу (від i =1до i=n).
У четвертому блоці змінюються значення змінних: z, x.
У п'ятому блоці виводиться результат. Четвертий та п'ятий блоки повторюються у кожному циклі.
11 . Циклічний алгоритм із лічильником циклів
Цей тип циклічних алгоритмів є кращим, якщо дано кількістю циклів.
Якщо кількість циклів невідома, блок-схеми циклічних алгоритмів можуть бути представлені у вигляді малюнків 12, 13.
Приклад : Обчислити у=у-xпоки що y> x, якщо y=30 , x=4. Підрахувати кількість виконаних циклів, кінцеве значення змінної у . У циклі вивести значення змінної у, кількість виконаних циклів. Скласти блок-схему розв'язання задачі.
Рішення : У прикладі кількість циклів невідома. Відповідно, вибирається алгоритм циклів другого типу. Алгоритм цього завдання наводиться на рис. 12.
Умова перевіряється на вході у цикл. У тілі циклу виконується два блоки:
1) у=у-х;i= i+1 ;
2) виведення значень змінних i, y.
Цикл виконується доти, доки виконується умова y>x. За умови рівності цих змінних у=хабо y
Алгоритм, представлений на рис.12, називається циклічний алгоритм із передумовою, Оскільки умова перевіряється на початку циклу або на вході в цикл. > x на вході до циклу. Якщо умова виконується, перехід до блоку 4, інакше на блок 6.
У четвертому блоці обчислюється значення змінної у i= i+1 .
У п'ятому блоці виводиться результат:
· Значення змінної у,
i.
Приклад : Скласти блок-схему прикладу (рисунок 12), перевіряючи умову виходу з циклу. У цьому прикладі умова завдання не змінюється, і результат виведеться той самий, але блок-схема буде іншою.
Рішення : У цьому випадку перевіряється умова на вихід із циклу: y<=x . При цьому цикл не виконується. Умову блок-схеми слід перенести в кінець циклу, після виведення на друк. Цикл виконується доти, доки виконується умова y>x.
Алгоритм, якщо умову перенести до кінця циклу, називається алгоритмом циклу з постумовою. Алгоритм цього завдання наводиться на рис. 13.
У другому блоці вводяться y=30 , x=4 .
У третьому блоці обчислюється значення змінної у , підраховується кількість виконаних циклів i= i+1 .
У четвертому блоці виводиться результат:
· Значення змінної у,
· Кількість виконаних циклів i.
У п'ятому блоці перевіряється умова y <= x на вихід із циклу. Якщо умова виконується, то перехід до блоку 6, інакше блок 3 і цикл повторюється.
13 . Алгоритм циклу з постумовою
Контрольні питання
1. Поняття алгоритму.
2. Види алгоритмів.
3. Основні алгоритмічні структури.
4. Основні блоки графічного алгоритму.
5. Лінійна алгоритмічна структура. приклад.
6. Розгалуження. приклад.
7. Циклічні алгоритмічні структури. приклад.
В рамках структурного програмування задачі, що мають алгоритмічне рішення, можуть бути описані з використанням наступних алгоритмічних структур:
- Слідування. Передбачає послідовне виконання команд згори донизу. Якщо алгоритм складається лише із структур прямування, він є лінійним.
- Розгалуження. Виконання програми йде однією з двох, кількох або безлічі гілок. Вибір гілки залежить від умови на вході розгалуження і даних, що надійшли сюди.
- Цикл. Передбачає можливість багаторазового повторення певних дій. Кількість повторень залежить від умови циклу.
- Функція (підпрограма). Команди, відокремлені від основної програми, виконуються лише у разі їхнього виклику з основної програми (з будь-якого її місця). Одна й та сама функція може викликатися з основної програми скільки завгодно разів.
Опис різних алгоритмічних структур мовою блок-схем
Розгалуження if
Це найпростіший тип розгалуження. Якщо результат обчислення висловлювання-умови повертає true (правда), то виконання алгоритму йде по гілці «Так», до якої включені додаткові вирази-дії. Якщо умова повертає false (брехня), виконання алгоритму йде по гілці «ні», тобто продовжує виконуватися основна гілка програми.
Розгалуження if-else
Якщо вираз-умова повертає true (правда), то виконання алгоритму йде по гілці «Так», якщо умова не виконується (false), то виконання по гілці «Ні». За будь-якого результату висловлювання-умови не можна повернутися в основну гілку програми, минаючи додаткові дії.
Розгалуження if-elif-else
Кількість умов може бути по-різному. Якщо виконується перше, то після виконання дій програма переходить до основної гілки, не перевіряючи подальші умови. Якщо перша умова повертає брехню, то перевіряється друга умова. Якщо друга умова повертає правду, виконуються дії, включені в другу гілку конструкції. Остання умова перевіряється лише в тому випадку, якщо жодна до нього не дало в результаті true. Цю алгоритмічну конструкцію (if – elif – else) не слід плутати з алгоритмічною конструкцією «Вибір».
Цикл while
Поки умова виконується (результат логічного виразу дає true), виконуватимуться дії тіла циклу. Після чергового виконання вкладених умов умова знову перевіряється. Щоб виконання алгоритму не зациклилося, у тілі циклу (крім інших дій) має бути вираз, у результаті якого змінюватиметься змінна, використовувана за умови. Тіло циклу може жодного разу не виконатись, якщо умова від самого початку давала false.
Цикл do
У цьому циклі вперше умова перевіряється лише після виконання дій тіла циклу. Якщо умова повертає true, вирази-дії повторюються знову. Якою б умовою не було, тіло даного циклу хоча б раз, але виконається.
Цикл for
Цей цикл також називають циклом «Для» (for). У його заголовку вказується три параметри: початкове значення змінної (від), звичайно значення (до) та її зміна за допомогою арифметичної операції на кожному звороті циклу (крок).
Анотація: Алгоритм є базовим поняттям для тих, хто хоче розпочати програмування будь-якою мовою програмування. Будь-яке завдання може бути формалізовано алгоритмічно. Щоб зрозуміти, із чого почати, розглянемо основні види алгоритмів. Мета цієї лекції – ознайомити студентів із поняттям алгоритму; показати, що така абстрактна річ як алгоритм оточує нас у повсякденному житті.
Приклад псевдокоду:
алг Знаходження приватного двох чисел почало виведення ("задайте ділене і дільник") введення (ділене, дільник) якщо дільник ≠ 0 то приватне = ділене / дільник висновок(приватне) інакше висновок("немає рішення") кон алг Знаходження приватного двох чисел
У цьому прикладі використовується три змінні: ділене, дільник і приватне. Ділимо і дільник задаються виконавцем довільними числами. Приватне вважається лише тому випадку, якщо дільник не дорівнює нулю.
Графічна реалізація алгоритму є блок-схемою. Блок-схема складається із блоків певної форми, з'єднаних стрілками. Відповідь при цьому отримує людина, яка виконує команди згідно з блок-схемою. Докладніше про блок-схеми буде розказано у Лекції 2.
Програмна реалізація алгоритму – це комп'ютерна програма, написана якоюсь алгоритмічною мовою програмування, наприклад: С++, Pascal, Basic тощо. Програма складається із команд певної мови програмування. Зазначимо, що та сама блок-схема може бути реалізована різними мовами програмування. Відповідь у своїй отримує ЕОМ, а чи не людина. Докладніше про складання програм мовою програмування С++ дивитись Лекцію 3.
Розрізняють три основні види алгоритмів:
- лінійний алгоритм,
- алгоритм, що розгалужується,
- циклічний алгоритм.
Лінійний алгоритм– це алгоритм, у якому дії виконуються одноразово та суворо послідовно.
Найпростіший приклад реалізації лінійного алгоритму – шлях із університету додому.
Словесний спосіб запису даного алгоритму:
- вийти із університету на зупинку;
- зачекати на потрібний автобус;
- сісти на потрібний автобус;
- сплатити за проїзд;
- вийти на потрібну зупинку;
- дійти до будинку.
Вочевидь, що це приклад належить до лінійному алгоритму, т.к. всі дії слідують одна одною, без умов і повторень.
>> Типи алгоритмів
В алгоритмах команди записуються один за одним у певному порядку. Виконуються вони не обов'язково у записаній послідовності: залежно від порядку виконання команд можна виділити три типи алгоритмів:
Лінійні алгоритми;
алгоритми із розгалуженнями;
алгоритми із повтореннями.
Лінійні алгоритми
У якому команди виконуються порядку їх записи, тобто послідовно друг за одним, називається лінійним.
Наприклад, лінійним є наступний алгоритм посадки дерева:
1) викопати у землі ямку;
2) опустити в ямку саджанець;
3) засипати ямку із саджанцем землею;
4) полити саджанець водою.
За допомогою блок-схеми цей алгоритм можна зобразити так:
Алгоритми про розгалуження
Ситуації, коли відома послідовність необхідних дій, зустрічаються вкрай рідко. У житті часто доводиться приймати рішення в залежності від обстановки, що склалася. Якщо йде дощ, ми беремо парасольку і надягаємо плащ; якщо жарко, одягаємо легкий одяг. Трапляються і складніші умови вибору. У деяких випадках від обраного рішення залежить подальша доля людини.
Логіку прийняття рішення можна описати так:
ЯКЩО<условие>ТО<действия 1>Інакше<действия 2>
Приклади:
ЯКЩО хочеш бути здоровий, ТО загартуйся, інакше валяйся весь день на дивані;
Якщо низько ластівки літають, то буде дощ, інакше дощу не буде;
Якщо уроки вивчені, то йди гуляти, інакше вчи уроки.
В деяких випадках<действия 2>можуть бути відсутніми;
ЯКЩО<условие>ТО<действия 1>
Приклад:
ЯКЩО назвався грузде, ТО лізи в кузов.
Форма організації дій, коли він залежно від виконання деякої умови відбувається одна чи інша послідовністькроків називається розгалуженням.
Зобразимо у вигляді блок-схеми послідовність дій учня 6 класу Мухіна Васі, яку він уявляє собі так: "Якщо Павлик удома, вирішуватимемо завдання з математики. Інакше слід зателефонувати Марині і разом готувати доповідь з біології. Якщо ж Марини немає вдома, то треба сісти за твір.
А ось так, за допомогою блок-схеми можна дуже наочно уявити міркування при вирішенні наступного завдання.
З трьох монет однакової гідності одна фальшива (легша). Як її знайти за допомогою одного зважування на чашкових вагах без гір?
Алгоритми із повтореннями
Насправді часто зустрічаються завдання, у яких одне чи кілька дій буває необхідно повторити кілька разів, доки дотримується деяке заздалегідь встановлене умова.
Алгоритм, що містить циклиназивається циклічним алгоритмом або алгоритмом з повтореннями.
Ситуація, коли виконання циклу будь-коли закінчується, називається зацикливанием. Слід розробляти алгоритми, які не допускають таких ситуацій.
Розглянемо приклад із математики.
Натуральне число називають простим, якщо воно має лише два дільники: одиницю і саме це число1.
2, 3, 5, 7 – прості числа; 4, 6, 8 – ні. У III столітті до нашої ери грецький математик Ератосфен запропонував наступний алгоритм для знаходження всіх простих чисел, менших від заданого числа n:
1) виписати усі натуральні числа від 1 до n;
2) викреслити 1;
3) підкреслити найменше із невідзначених чисел;
4) викреслити всі числа, кратні підкресленому на попередньому етапі;
5) якщо списку є невідзначені числа, то перейти до кроку 3, інакше всі підкреслені числа - прості.
Це циклічний алгоритм. При виконанні повторення кроків 3-5 відбувається, поки у вихідному списку залишаються невідзначені числа.
Ось так виглядає блок-схема дій школяра, якому перед вечірньою прогулянкою слід виконати домашнє завдання з математики:
Нагадаємо, що число 1 не відносять ні до складових (що мають більше двох дільників), ні до простих чисел.
Найголовніше
Залежно від порядку виконання команд можна виділити три типи алгоритмів:
> лінійні алгоритми;
> алгоритми з розгалуженнями;
> алгоритми із повтореннями.
Алгоритм, у якому команди виконуються порядку їх записи, тобто послідовно друг за одним, називається лінійним.
Форма організації дій, коли він залежно від виконання деякої умови відбувається одна чи інша послідовність кроків, називається розгалуженням.
Форма організації дій, коли він виконання однієї й тієї ж послідовності команд повторюється, поки виконується деяке заздалегідь встановлене умова, називається циклом (повторенням).
Запитання та завдання
1. Які алгоритми називають лінійними?
2. Наведіть приклад лінійного алгоритму,
3. Виконавець «Обчислювач» вміє виконувати лише дві команди: множити на 2 і додавати. Придумайте для нього найбільш короткий план отримання з числа 50.
4. Яка форма організації дій називається розгалуженням?
5. Які умови мала виконати героїня оповіді «Гусі-лебеді»?
6. Наведіть приклад алгоритму, що містить розгалуження»
7. Прочитайте уривок із вірша Дж. Родарі «Чим пахнуть ремесла?»:
У кожної справи запах особливий:
У булочній пахне тістом та здобою.
Повз столярну йдеш майстернею -
Стружкою пахне і свіжою дошкою.
Пахне маляр скипидаром та фарбою.
Пахне скляр віконною замазкою.
Куртка водія пахне бензином,
Блуза робітника - олією машинною.
Перефразуйтепро професії за допомогою слів «ЯКЩО... ТО»/
8. Згадайте, герої яких російських народних казок роблять вибір, що визначає їхню долю.
9. З 9 монет однакової гідності одна фальшива (легша). За скільки зважувань на чашкових вагах без гирь ви можете визначити?
10. Яка форма організації дій називається повторенням?
11. Наведіть приклад алгоритму, що містить повторення.
12. У яких відомих літературних творах має місце циклічна форма організації дій?
13. Де виявиться виконавець, який виконав 16 разів поспіль наступну групу команд?
пройти 10 метрів уперед
повернути на 90° за годинниковою стрілкою
14. Яку групу дій і скільки разів слід повторити під час вирішення наступного завдання?
Сорок солдатів підійшли до річки, якою на човні катаються двоє хлопчиків. Як солдатам переправитися на інший берег, якщо човен вміщує лише одного солдата або двох хлопчиків, а солдата та хлопчика вже не вміщує?
15. Згадайте задачу про Обчислювач, який вміє тільки множити на 2 і додавати 1. Розробляти для нього раціональні алгоритми буде значно простіше, якщо скористатися наступною блок-схемою:
Використовуючи цю блок-схему, розробте раціональні алгоритми одержання з числа 0 чисел 1024 та 500.
Босова Л. Л. Інформатика: Підручник для 6 класу/Л. Л. Босова. - 3-тє вид., Випр. та дод. - М: БІНОМ. Лабораторія знань, 2005. – 208 с.: іл.
Зміст уроку конспект уроку та опорний каркас презентація уроку інтерактивні технології акселеративні методи навчання Практика тести, тестування онлайн завдання та вправи домашні завдання практикуми та тренінги питання для дискусій у класі Ілюстрації відео- та аудіоматеріали фотографії, картинки графіки, таблиці, схеми комікси, притчі, приказки, кросворди, анекдоти, приколи, цитати Доповнення шпаргалки фішки для допитливих статті (МАН) література основна та додаткова словник термінів Вдосконалення підручників та уроків виправлення помилок у підручнику заміна застарілих знань новими Тільки для вчителів календарні плани навчальні програми методичні рекомендації
