Алгоритми з повторенням та розгалуженням

Слово «алгоритм» походить від імені перського вченого, астронома і математика Мухаммеда Ібн Муси Аль Хорезмі. І

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

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

Ви вже зрозуміли, що «розмовляти» з комп’ютером мовою Scratch — означає складати скрипти.

ВПРАВА 10

Завдання 1. Скласти у вікні програми Scratch для спрайта Рудого кота скрипт за таким алгоритмом:

• кіт стає у вихідне положення;

• чекає 2 с;

• переміщується на 70 кроків;

• змінює свій образ;

• стоїть на місці 1 с;

• переміщується на 50 кроків;

• набуває попереднього вигляду.

1. Складіть для кота скрипт, як на рис. 3.3.

2. Додайте до скрипта блок-заголовок (заголовки мають форму

, який вважаєте за потрібний, та вико

найте відповідну дію, щоб перевірити, як працює проект.

Завдання 2. Скласти для спрайта восьминога скрипт за алгоритмом поданим у вигляді блок-схеми на рис. 3.4.

1. Виконайте команду Файл ► Новий, щоб відкрити вікно нового проекту, та додайте до нього спрайт восьминога (файл Octopusl-а з папки Animals бібліотеки програми Scratch).

2. Складіть для спрайта скрипт, як на рис. 3.5.

3. Понатискайте на клавішу 1, аби перевірити, як працює проект. (Гру барабанів ви почуєте, якщо до вашого комп'ютера під'єднано колонки чи навушники).

4. Збережіть проект під назвою Впр10_Прізвище.

Алгоритм, що містить одну або кілька умов і, відповідно, дві та більше гілок, називають алгоритмом з розгалуженням. На рис. 3.7 наведено приклад блок-схеми алгоритму з розгалуженням.

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

Багаторазове виконання тієї самої послідовності команд доти, доки виконується визначена наперед умова, називають циклом (повторенням). Алгоритм, що містить цикли, називають циклічним алгоритмом або алгоритмом з повторенням. На рис. 3.8 наведено приклад блок-схеми такого алгоритму.

Майже всі мови програмування містять оператори розгалужень і циклів. Не є винятком і Scratch. «Словник» його мови містить п’ять блоків, що за формою нагадують букву «С», і один подібний до букви «Е». їх ще іноді називають обгортками, оскільки всередину цих блоків можна вставляти інші.

Висновки

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

Алгоритми можна подавати по-різному: текст, блок-схема, мова програмування тощо.

Залежно від порядку виконання команд можна виділити три типи алгоритмів: лінійні (слідування), з розгалуженням, з повторенням.

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

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

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

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

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

Контрольні запитання та завдання

1. Які алгоритми називають лінійними? Наведіть приклади лінійних алгоритмів.

2. Які алгоритми називають розгалуженими? Наведіть приклади алгоритмів з розгалуженням.

3*. Наведіть приклади прислів’їв, де дія виконується в залежності від виконання певної умови.

4. Які алгоритми називають циклічними? Наведіть приклади алгоритмів з повторенням.

5*. Наведіть приклади відомих казок або оповідань, де певні дії виконуються циклічно.

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

Пригадати базові структури алгоритмів ви зможете на диску.

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

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

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

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

Перший блок у блок-схемі цього оператора зображує лічильник, значення N (кількість повторювань) у якому щоразу після виконання тіла циклу зменшується на 1, аж доки не набуде значення «0». На рис. 3.12 зображено відповідний Scratch-оператор.

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

Щоб побудувати зображення зірки, введіть скрипт, зображений на рис. 3.13.

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

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

У табл. 3.1 пояснено покрокове виконання тіла циклу команди повторити.

Таблиця 3.1. Команди Scratch для побудови зірки із восьми променів

Команда Scratch	Положення спрайта	Пояснення дій спрайта
		Початкове положення спрайта
		Повертає на кут 45° проти годинникової стрілки
		Переміщується на 3° кроків

Завдання. Виконати проект, у якому кіт буде ходити по екрану зліва направо.

1. Відкрийте програму Scratch.

2. Оберіть блок завжди з категорії Керувати та розмістіть усередині команди, як на рис. 3.14.

Клацнувши 2 рази на команді, ви переконаєтеся, що кіт буде пересуватися зліва направо.

Примітка. Щоб кіт не перевертався при зворотньому русі, треба змінити режим руху об'єкта за допомогою кнопки (S) (приймати тільки зліва направо).

3. Додайте до попереднього скрипта команди наступний образ із категорії Вигляд і чекати 1 секунд із категорії Керувати. Розташуйте дані команди, як на рис. 3.15. (Ці команди потрібні для того, щоб кіт не ковзав, а переставляв лапки, змінюючи через певний час свій образ).

Щоб дізнатись, які образи містить спрайт, або додати нові образи до спрайта, слід перейти до вкладки Образи (розташована по центру вікна середовища). Тут, як бачите, два коти: перший має назву — образі, а другий — образ2. І саме другий переставляє лапи на відміну від першого (рис. 3.16).

4. Зменшіть час на відображення певного образу, змінивши в команді чекати 1 секунд значення 1 на 0,1 (рис. 3.17).

5. Додайте до одержаного скрипта команду коли натиснуто прапорець.

6. Збережіть проект під назвою Впр12_Прізвище.

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

Таблиця 3.2. Види команд повторення

Команда Scratch	Тип циклу	Пояснення
	Безумовний цикл	Тіло циклу виконується нескінченно
	Цикл з лічильником	Тіло циклу виконується вказану кількість разів
	Цикл з передумовою	Тіло циклу виконується доти, доки істинною залишається вказана перед його початком умова
	Цикл з післяумовою	Умова в циклі перевіряється після виконання його тіла

ВПРАВА 14

ВПРАВА 15

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

1. Відкрийте вікно нового проекту та додайте до нього спрайт будь-якого метелика. На сцені проекту намалюйте червону рамку, дещо меншу, ніж сцена.

2. Складіть для спрайта метелика скрипти, зображені на рис. 3.23.

Підказка. Блок доторкається кольору? має вказувати на колір рамки. Щоб це сталося, клацніть спочатку на квадратик у блоці, а коли вказівник мишки перетвориться на піпетку — на рамку на сцені проекту.

3. Клацніть кнопку із зеленим прапорцем і почекайте, коли буде створено рамку з метеликів.

4. Збережіть проект під назвою Впр15_Прізвище.

ВПРАВА 16

Завдання. Створити проект зображення восьмикутника (рис. 3.24), використовуючи пояснення до побудови зірки з вісьмома променями. Зберегти проект під назвою Впр16_Прізвище.

Скласти алгоритми з повтореннями ви зможете, виконавши вправи на диску.

Висновки

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

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

' і

Контрольні запитання та завдання

1. Опишіть та порівняйте принципи виконання безумовного циклу та циклів з умовами.

2. Які команди використовують у Scratch для виконання різних видів циклів?

3. Як ви думаєте, чому всі сучасні мови програмування використовують команди реалізації циклів?

2. Додайте до проекту спрайт ЫЛ_1, а спрайт ШЛ_2 зробіть образом для спрайта ШН_1. Для цього виділіть спрайт ШЛ_1, відкрийте вкладку Образи, натисніть кнопку Імпортувати, оберіть спрайт ШЛ_2.

3. Додайте до проекту спрайт із зображенням цифри 1 та розмістіть її зображення над дверима ліфта.

а) Натисніть кнопку

Висловлювання. Істинні та хибні висловлювання

10.1.

ПОНЯТТЯ ВИСЛОВЛЮВАННЯ, ВИДИ ВИСЛОВЛЮВАНЬ

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

Своє розуміння навколишнього світу людина передає у формі висловлювань. Висловлювання будується на основі понять і за характером є розповідним реченням. Проте не кожне речення виражає висловлювання.

Висловлювання — це розповідне речення, яке можна охарактеризувати як істинне або хибне.

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

Хибним висловлювання буде в тому випадку, коли воно не відповідає дійсності, наприклад: «Процесор є пристроєм для друку».

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

Висловлювання можуть бути простими або складними.

Висловлювання називають простим, якщо воно не включає в себе самостійні частини, які є висловлюваннями.

Складне висловлювання складається з простих висловлювань, що з’єднані логічними зв’язками (операціями).

Логічними зв’язками є сполучники «і», «або» та частка «не».

Так висловлювання «Василь читає книгу» та «Василь п’є чай» є простими. А висловлювання «Василь читає книгу і п’є чай» — складним.

ЛОГІЧНІ ОПЕРАТОРИ В СЕРЕДОВИЩІ SCRATCH

Логіка побудови висловлювань дуже гармонійно поєднується з принципами роботи комп’ютера і основними методами його програмування. Всі апаратні компоненти комп’ютера

побудовані на логічних мікросхемах. Вам відомо, що система подання інформації в комп’ютері заснована на понятті біта, що має лише два стани — 0 та 1 (відповідно ХИБНІСТЬ та ІСТИНА). Логічні оператори використовують у всіх мовах програмування. У Scratch з їх допомогою задають умови зміни поведінки об’єктів. Які це умови, немає жодного значення, головне, якими вони є — істинними чи хибними. У Scratch-проектах важливо, наприклад, чи було натиснуто якусь клавішу, і немає жодного значення, хто її натиснув, коли і якою рукою. Створювати в Scratch умови зміни поведінки об’єктів можна, додаючи до скриптів оператори порівняння:

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

, зазвичай використовують усередині С-блоків під час створення розгалужень і циклів — конструкцій алгоритмів, які керують порядком виконання програм і здатні формувати ілюзію розумної поведінки спрайтів. На рис. 3.34 наведено приклади блоків логіки.

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

1. Додайте до проекту спрайт Ghostl з папки Fantasy в бібліотеці програми, два його образи (Ghost2-a і Ghost2-b) та будь-який фон для цієї сцени на вибір.

2. Складіть для спрайта привиду скрипт, як показано на рис. 3.36.

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

4. Збережіть проект під назвою Впр17_Прізвище.

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

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

Висновки

Висловлювання — це розповідне речення, яке можна охарактеризувати як істинне або хибне.

Висловлювання можуть бути простими або складними.

Висловлювання називають простим, якщо воно не включає в себе самостійні частини, які є висловлюваннями.

Складне висловлювання складається з простих висловлювань, що з’єднані логічними зв’язками (операціями).

Логічними зв’язками є сполучники «і», «або» та частка «не».

Контрольні запитання та завдання

1. Що таке висловлювання?

2. Які висловлювання називають простими? Наведіть приклади простих висловлювань.

3. Які висловлювання називають складними? Наведіть приклади складних висловлювань.

4*. Назвіть блоки логіки в середовищі Scratch.

11.1. АЛГОРИТМИ З РОЗГАЛУЖЕННЯМ У СКОРОЧЕНІЙ ФОРМІ

Таблиця 3.3. Блоки логічних операторів

Команда	Дія
	Істинна, якщо клавішу миші натиснуто
	Істинна, якщо вказану клавішу натиснуто (обирається зі списку)
	Істинна, якщо спрайт торкається вказаного спрайта, краю або вказівника миші (обирається зі списку)
	Істинна, якщо спрайт торкається вказаного кольору (коліробирається піпеткою)
	Істинна, якщо перший колір (у межах спрайта) торкається другого кольору (у фоні або іншому спрайті) (кольори обираються піпеткою)
	Істинна, якщо обидві умови справджуються
	Істинна, якщо будь-яка умова справджується
	Істинна, якщо умова не справджується. Хибна, якщо умова справджується

У наступній вправі розглянемо випадок використання неповної команди розгалуження.

6. Збережіть проект під назвою Впр19_Прізвище.

11.2.

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

Так у наступному скрипті (рис. 3.42) реалізовано використання повної форми команди розгалуження. Залежно від одержаної відповіді, чи є сніг на вулиці, персонаж вирішує, на чому він буде кататися — на санчатах чи на велосипеді. Поряд із скриптом наведено алгоритм у вигляді блок-схеми.

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

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

Scratch не обмежує кількість вкладених умовних операторів, тож тут можна реалізовувати будь-які складні розгалуження

Завдання. Створити проект розв'язання задачі.

Дано значення величини кута трикутника. Визначити його тип: гострий, прямий чи тупий.

Розглянемо послідовність дій для розв'язання поставленої задачі. Якщо кут буде < 90°, то цей кут — гострий, якщо = 90° — прямий, якщо > 90° — тупий. Створимо блок-схему розв'язання задачі (рис. 3.44).

1. Реалізуйте алгоритм, представлений у вигляді блок-схе-ми, за допомогою скрипта проекту в середовищі Scratch (рис. 3.45).

2. Збережіть проект під назвою Впр20_Прізвище.

1. Які алгоритми називаються розгалуженими?

2. Які є форми оператора розгалуження?

3. Наведіть приклад алгоритму із скороченою формою розгалуження.

4. Наведіть приклад алгоритму із повною формою розгалуження.

5. Які команди розгалуження використовують у середовищі Scratch? 6*. У яких випадках використовують вкладені умовні оператори?

Скільки їх може бути в Scratch?

ПРАКТИЧНА РОБОТА №4

Складання та виконання алгоритмів з розгалуженням у визначеному навчальному середовищі виконання алгоритмів

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

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

Хід роботи

1. До нового проекту завантажте чотири фони для сцени з різними порами року, спрайт дівчинки та три її образи (одяг дівчинки має відповідати порам року). (Зображення образів спрайта і фонів сцен є в папці FILES^nP4 на диску.)

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

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

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

програми. Щоб перервати виконання команд усередині С-блока завжди, треба встановити оператор з умовою про їх зупинення та заглушкою (на рис. 3.52 цей оператор обведено рамкою).

Як бачимо, в наведеному прикладі поєднано команди повторення та розгалуження.

Досить часто для створення проектів у Scratch використовують сукупність команд безумовного циклу та скороченої форми розгалуження у вигляді блоків завжди і якщо (рис. 3.53).

Ви можете слушно зауважити, що немає сенсу використовувати вкладену конструкцію, адже в Scratch передбачено оператор завжди якщо, що відповідає команді повторення з передумовою (рис. 3.54).

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

Перевірити свої знання, пройти тест і розгадати кроворд ви зможете на диску.

ВПРАВА 23

Завдання. Створити проект відображення руху літака та машин уздовж дороги.

1. Виконайте оформлення сцени та спрайтів за зразком на рис. 3.55.

4. Виділіть спрайт кота та складіть для нього скрипт, як на рис. 3.58.

5. Запустіть проект на виконання та поспостерігайте за тим, що відбуватиметься з його героями після виконання заданої у С-блоці якщо умови.

6. Збережіть проект під назвою Впр26_Прізвище.

ВПРАВА 27

Завдання. Створити проект, у якому при введенні кількості кутів геометричної фігури — «3» або «4» — буде побудовано відповідну фігуру — трикутник або квадрат. У випадку іншої відповіді повинно з'явитися повідомлення про помилку.

Проект виконати за поданою блок-схемою на рис. 3.59.

Завдання. Скласти програму, яка б відтворювала дії світлофора. Використати в проекті спрайти trafific lights_1, trafific lights_2, trafific lights_3 з папки Scratch (папка FILES^BnpaBa_29 на диску). Під час створення сценарію врахувати, що червоний сигнал світлофора, так само як і зелений, має відображатися 2с,а жовтий — лише 0,5 с. Додати до скрипта команду завершення роботи світлофора за умови натиснення на клавішу ^ (стрілка вгору). Зберегти проект під назвою Впр29_Прізвище.

Висновки

У середовищі Scratch для створення проектів використовують різноманітні комбінації команд повторення та розгалуження.

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

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

У середовищі Scratch комбінування блоків завжди та якщо рівносильне до команди завжди якщо. Проте оператор завжди якщо виконується швидше, а завдяки сукупності операторів завжди та якщо можна вставити скільки завгодно вкладень умовного оператора, а також використати оператор розгалуження із повною формою якщо — інакше.

Контрольні запитання та завдання

1. З якою метою використовують комбінування операторів повторення та розгалуження?

2. Як можна здійснити завершення команди завжди в середовищі Scratch?

3. У чому відмінність оператора завжди якщо від сукупності операторів завжди та якщо?

4. Які види алгоритмів реалізовано завдяки операторам завжди та якщо?

ПРАКТИЧНА РОБОТА №5

Складання та виконання алгоритмів з повторенням і розгалуженням у визначеному навчальному середовищі виконання алгоритмів

Хід роботи

Завдання 1. Виконавши завдання цієї вправи, ви розробите проект, що відтворюватиме роботу торгового апарата для приготування напоїв. Залежно від сплаченої суми — 2, 4 чи 5 грн — автомат видаватиме чай, каву чи сік відповідно.

1. Відкрийте у вікні програми Scratch файл з шаблоном проекту Automat, збережений на диску в папці Scratch (з папки FILES^nP5 на диску).

2. Виділіть під областю сцени спрайт склянки з напоєм, перейдіть на вкладку Скрипти та складіть сценарій, за яким апарат після натискання на клавіатурі клавіші З видаватиме склянку з чаєм (рис. 3.65).

3. Складіть подібні скрипти для кави та соку.

4. Додайте до сценарію команди

запустіть

проект на виконання та понатискайте клавіші 2, 4, 5.

5. Збережіть файл під назвою Пр5_1_Прізвище.

Завдання 2. Виконавши завдання, ви створите проект, в якому після натиснення клавіші стрілка вгору ваш спрайт підстрибуватиме, а після натискання клавіш стрілка вліво і стрілка вправо — рухатиметься у відповідному напрямку.

1. Завантажте до проекту спрайт Fantasy13, що міститься в папці Fantasy.

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

а) Перетягніть на вкладку Скрипти команду якщо та вставте в неї умову клавішу стрілка вгору натиснуто?.

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