Розділ 3. Алгоритми з повторенням і розгалуженням » Народна Освіта


Народна Освіта » Інформатика » Розділ 3. Алгоритми з повторенням і розгалуженням






Розділ 3. Алгоритми з повторенням і розгалуженням

У цьому розділі ви дізнаєтеся про:

3.1. ПОВТОРЕННЯ (ЦИКЛ). АЛГОРИТМИ З ПОВТОРЕННЯМ

1. Що таке алгоритм? Назвіть кілька відомих вам алгоритмів.

2. Які явища природи, події у вашому житті неодноразово повторюються?

3. Пригадайте правило, яке передбачає послідовність дій, що повинні повторитися кілька разів.

ЦИКЛІЧНІ ПРОЦЕСИ

У природі можна спостерігати процеси, які багаторазово повторюються. Так, наприклад, кожного дня Сонце сходить над горизонтом і заходить за горизонт (мал. 3.1), кожного місяця можна бачити на небосхилі одне й те саме змінення фаз Місяця (мал. 3.2), кожного року Сонце проходить через одні й ті самі сузір’я - сузір’я Зодіаку (мал. 3.3) та інше.

Зодіак (грец. £о8ихк6<; кі'кХос; -звірине коло) - уявна смуга, яка розміщена обабіч і вздовж великого кола небесної сфери, по якому відбувається видимий річний рух Сонця.

 

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

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

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

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

І таких прикладів можна навести багато.

ПОВТОРЕННЯ (ЦИКЛ) В АЛГОРИТМАХ

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

Розглянемо таку задачу.

Задача. У дворі є порожні діжка і відро ємністю 50 л і 10 л відповідно та колодязь (мал. 3.4). Потрібно наповнити діжку водою.

Очевидно, для розв’язування цієї задачі потрібно виконати такий алгоритм:

1. Узяти відро.

2. Повторити 5 разів

1. Підійти до колодязя.

2. Набрати з колодязя повне відро води.

3. Підійти з повним відром води до діжки.

4. Вилити воду з відра в діжку.

3. Поставити відро.

Цей алгоритм містить команду 2:

Повторити 5 разів

1. Підійти до колодязя.

2. Набрати з колодязя повне відро води.

3. Підійти з повним відром води до діжки.

4. Вилити воду з відра в діжку.

 

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

1. Підійти до колодязя.

2. Набрати з колодязя повне відро води.

3. Підійти з повним відром води до діжки.

4. Вилити воду з відра в діжку повинні виконатися 5 разів поспіль.

Вони утворюють тіло циклу.

Сама команда Повторити 5 разів задає кількість повторень тіла циклу. Її називають заголовком циклу.

Загальний вигляд команди циклу з лічильником:

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

Блок-схему алгоритму розв’язування цієї задачі наведено на малюнку 3.5.

У блок-схемі використано блок Повторити N разів

 

 

який задає

кількість повторень команд тіла циклу.

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

ПОВТОРЕННЯ В SCRATCH

У середовищі Scratch також можна складати алгоритми із циклами. Для цього в системі команд виконавців є спеціальні команди. Зокрема, для організації в алгоритмі циклу з лічильником

можна використати команду

 

 

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

Наприклад, виконавши наведений алгоритм, що містить цикл, Рудий кіт намалює орнамент (мал. 3.6).

 

 

Орнамент (лат. ornamentum -прикраса) - прикраса у вигляді візерунка, що складається із симетрично розміщених художніх елементів.

 

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

Звертаємо вашу увагу, що в тілі циклу алгоритму малювання орнамен-

 

ту дві команди

 

повторюються 4 рази поспіль.

 

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

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

У кінці тіла зовнішнього циклу (мал. 3.7)

 

Кут

 

повороту в ній дорівнює саме 60°, тому що цей кут, помножений на кількість повторень тіла циклу (6), дає 360°, що відповідає повороту по повному колу.

 

є команда

 

Якщо змінити кількість повторень тіла циклу, наприклад на 20, то й кут у команді зовнішнього циклу потрібно змінити на 18°. У цьому разі Рудий кіт намалює інший орнамент (мал. 3.8).

 

Команду циклу з лічильником можна використати для циклічного змі-нення кольору малювання. У Scratch кожному кольору олівця відповідає певне число, код цього кольору. В алгоритмі, наведеному на малюнку 3.9, перед командою циклу розміщено команду, яка задає початковий колір

 

олівця. Під час виконання команди

 

тіла наведе-

 

ного циклу кожного разу код кольору олівця збільшується на ЗО. Тим самим змінюється колір малювання, як це показано на малюнку 3.9.

 

 

Для того щоб Рудий кіт намалював квадрат саме такого розташування на Сцені, потрібно задати відповідне початкове положення виконавця. Це можна зробити поворотом зображення виконавця, розміщеного над ярликами вкладок (мал. 3.9).

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

Наведемо ще приклад алгоритму із циклом, виконавши який, Рудий кіт намалює коло (мал. 3.10). 15 16 17 18 19 20 21 22 23 24 25

Працюємо з комп’ютером

 

 

12. Розмістіть в області скриптів алгоритм, наведений на малюнку 3.12.

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

14. Виконайте алгоритм. Проаналізуйте отримане зображення.

15. Збережіть створений проект у своїй папці у файлі вправа 3.1.2.

Найважливіше в цьому пункті

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

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

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

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

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

Дайте відповіді на запитання

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

Який алгоритм називають алгоритмом із циклом?

Як називають цикл, який входить у тіло іншого циклу? Який цикл називають зовнішнім і який - внутрішнім?

Виконайте завдання

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

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

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

а) 2; б) 4; в) 8?

Виконайте алгоритм:

1. Записати чотирицифрове число.

2. Надати змінній х значення 0.

3. Повторити 4 рази

1. Узяти останню цифру останнього записаного числа.

2. Додати її до значення змінної х.

3. Відкинути останню цифру останнього записаного числа і записати отримане число.

4. Повідомити значення змінної х.

Для розв’язування якої задачі можна використати цей алгоритм? Складіть блок-схему цього алгоритму.

Складіть блок-схему алгоритму обчислення п’ятого числа в послідовності чисел, у якій перше число х = 7, а кожне наступне число утворюється множенням попереднього числа на 2 і додаванням до добутку числа 3. Виконайте складений алгоритм.

Складіть блок-схему алгоритму обчислення шостого числа в послідовності чисел, у якій перше число х = 3, а кожне наступне число утворюється множенням попереднього числа на 3 і відніманням від добутку числа 2. Виконайте складений алгоритм.

, Складіть алгоритм піднесення числа а до п’ятого степеня. Подайте його в словесній формі та у формі блок-схеми. Виконайте складений алгоритм для одного додатного та одного від’ємного числа а. Складіть алгоритм для Рудого кота, щоб він намалював зображення, наведене на малюнку 3.13. Збережіть створений проект у своїй папці у файлі з іменем завдання 3.1.8.

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

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

«Складання та виконання алгоритмів з повторенням у середовищі Scratch»

1. Запустіть програму Scratch.

2. Складіть алгоритм, щоб отримати зображення, наведене на малюнку 3.15.

3. Збережіть створений проект у своїй папці у файлі з іменем практична 3.1.

4. Складіть алгоритм, щоб отримати зображення, наведене на малюнку 3.16.

5. Збережіть створений проект у своїй папці у файлі з іменем практична 3.2.

6. Закрийте вікно програми Scratch.

3.2. ВИСЛОВЛЮВАННЯ. ІСТИННІ ТА ХИБНІ ВИСЛОВЛЮВАННЯ. УМОВНЕ ВИСЛОВЛЮВАННЯ

1. Що ви можете сказати про твердження «Київ — столиця України»?

2. Що ви можете сказати про твердження «2 + 2 = 5»?

3. Що ви можете сказати про твердження «Завтра об 11-й годині буде дощ»?

ВИСЛОВЛЮВАННЯ.

ІСТИННІ ТА ХИБНІ ВИСЛОВЛЮВАННЯ

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

Вислювання може бути істинним або хибним.

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

Прикладами істинних висловлювань є:

• Україна розміщена в Європі.

• У жовтні 31 день.

• Гусінь перетворюється на метелика.

• Дніпро ділить Україну на Лівобережну та Правобережну.

• Художник малює картину.

Прикладами хибних висловлювань є:

• У лютому місяці будь-якого року 28 днів.

• Пароплав пливе в хмарах.

• Автомобіль плете павутиння.

• Слово дерево - дієслово.

• 1 - просте число.

А ось приклади речень, які не є висловлюваннями:

• Завтра випаде сніг.

• Піднеси число 2,3 до третього степеня.

• Скільки тобі років?

УМОВНІ ВИСЛОВЛЮВАННЯ

На уроках геометрії ви вивчали такі властивості кутів: «Вертикальні кути рівні» і «Сума суміжних кутів дорівнює 180°». Ці твердження є істинними для будь-яких вертикальних кутів і для будь-яких суміжних кутів.

Ці властивості кутів можна сформулювати іншими реченнями, а саме: «Якщо кути вертикальні, то вони рівні» та «Якщо кути суміжні, то їх сума дорівнює 180°». Такі висловлювання називають умовними, бо кожне з них містить умову: «Якщо кути вертикальні, ...» і «Якщо кути суміжні, ...», а також висновок: «..., то вони рівні» і «..., то їх сума дорівнює 180°».

Умовні висловлювання можуть бути більш складними. Наприклад таке: «Якщо сума цифр натурального числа ділиться на 3, то число ділиться на 3, інакше число не ділиться на 3». Це висловлювання, крім умови, містить два висновки. Якщо взяти конкретне натуральне число, наприклад 237, то сума його цифр дорівнює 12, отже, число ділиться на 3. Якщо ж узяти інше натуральне число, наприклад 679, то сума його цифр дорівнює 22, і тоді істинним є висновок, який записано після слова інакше.

Наведемо приклад хибних умовних висловлювань. Наприклад, хибним є висловлювання: «Якщо довільні два кути рівні, то вони вертикальні».

Хибним є також висловлювання: «Якщо деяке довільне число додатне, то воно більше від нуля, інакше воно менше від нуля». Дійсно, якщо взяти число 0, то для нього умова є хибна, але й хибним для нього є й висновок «..., інакше воно менше від 0».

Найважливіше в цьому пункті

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

Висловлювання може бути істинним або хибним.

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

Висловлювання «Якщо — то» називають умовним, бо воно містить умову.

Дайте відповіді на запитання

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

Які висловлювання називають істинними, а які - хибними?

Чому висловлювання «Якщо — то» називають умовним?

Як перевірити, істинним чи хибним є умовне висловлювання «Якщо — то»?

Виконайте завдання

Наведіть приклади істинних висловлювань.

Наведіть приклади хибних висловлювань.

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

Визначте, які з наведених речень є істинними висловлюваннями, хибними висловлюваннями і не є висловлюваннями:

а) Ти - учень 7-го класу.

б) У якому місті ти народився?

в) Закрий вікно.

г) Число 243 ділиться націло на 5.

д) Якщо число ділиться на 2, то воно ділиться на 6.

е) Якщо число ділиться на 6, то воно ділиться на 2.

ж) Якщо число просте, то воно не ділиться на жодне число.

з) Якщо кути вертикальні, то вони рівні, інакше вони не рівні.

и) Квадрат будь-якого числа є додатним числом.

к) Інформатика - цікавий предмет.

л) Тарас Шевченко — великий український поет.

3.3. АЛГОРИТМИ З РОЗГАЛУЖЕННЯМ

1. Що таке висловлювання? Наведіть приклади істинних і хибних висловлювань. Наведіть приклад речення, яке не є висловлюванням.

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

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

 

КОМАНДА ПРИСВОЮВАННЯ

Розглянемо задачу на обчислення значення виразу.

Задача 1. Обчислити значення виразу (а - Ь) * (с - д), де а, Ь, с, й - цілі або дробові числа (символом * в інформатиці позначається операція множення).

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

Запишемо алгоритм розв’язування цієї задачі для такого виконавця у словесній формі.

1. Увести значення змінних а, Ь, с, й.

2. Обчислити значення виразу а - Ь і результат присвоїти змінній х(запам’ятати як значення цієї змінної).

3. Обчислити значення виразу с - сі і результат присвоїти змінній у(запам’ятати як значення цієї змінної).

4. Обчислити значення виразу х * у і результат присвоїти ЗМІННІЙ 2.

5. Повідомити значення змінної г.

У командах 2, 3 і 4 обчислюється значення

виразу і результат обчислення присвоюється (запам’ятовується як значення) певній змінній. Такі команди називають командами присвоювання. Для них зручно використовувати таку форму запису:

 

 

 

Знак := називають знаком присвоювання, він складається з двох символів: двокрапки і дорівнює, які записуються без пропуску між ними. Команду виду у := с - в, називають командою присвоювання.

Наведемо блок-схему цього алгоритму (мал. 3.17).

 

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

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

Такий алгоритм або такий фрагмент алгоритму називають лінійним, або слідуванням.

РОЗГАЛУЖЕННЯ В АЛГОРИТМІ

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

Задача 2. Обчислити значення виразу (а - Ь) / (с - d), де a, b, с, d - цілі або дробові числа (символом / в інформатиці позначають операцію ділення).

Перш за все звернемо увагу на те, що значення цього виразу, на відміну від попереднього, можна обчислити не при будь-яких значеннях змінних a, b, с, d. Адже цей вираз містить дію ділення на вираз зі змінними, який може дорівнювати нулю. Тобто якщо значення різниці с - d дорівнює нулю, то значення виразу (а - b) / (с - d) обчислити не можна, а якщо не дорівнює - то можна.

Це означає, що система команд виконавця повинна містити команду порівняння двох чисел, наприклад таку: «s = t?», де s і t - або числа, або змінні, або вирази, які мають певні числові значення. Така команда є прикладом команди перевірки умови.

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

Алгоритм розв’язування цієї задачі виглядатиме так:

1. Увести значення змінних a, b, с, d.

2. х := с - d.

3. x =0?

4. Якщо результат виконання команди перевірки умови істина, то повідомити «Вираз значення не має: ділення на нуль», після чого виконати команду 8, інакше (тобто якщо результат виконання команди перевірки умови хиба) виконати команду 5. 26 27

Хід виконання цього алгоритму залежатиме від результату виконання команди перевірки умови. І залежно від цього результату (істина чи хиба) виконавець буде виконувати різні команди. Так, у наведеному алгоритмі, якщо результат виконання команди перевірки умови істина, то виконуватимуться команда виведення повідомлення: «Вираз значення не має: ділення на нуль» і команда 8, а якщо результат виконання команди перевірки умови хиба, то виконуватимуться команди 5-8.

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

 

 

Оскільки результатом виконання команди перевірки умови

 

може бути або істина, або хиба, то із цього блока є два виходи. Вихід Так означає, що результатом виконання команди перевірки умови є істина, а вихід Ні - що результатом виконання команди перевірки умови є хиба. Наведемо блок-схему цього алгоритму (мал. 3.18).

 

 

Розглянемо фрагмент алгоритму на малюнку 3.18 від блока Рішення до блока Термінатор (не включаючи цей блок).

 

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

Такий фрагмент алгоритму називають розгалуженням.

Алгоритм, який містить розгалуження, називають алгоритмом з розгалуженням.

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

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

В алгоритмах використовують розгалуження двох видів: повне розгалуження (мал. 3.19) і неповне розгалуження (мал. 3.20)

 

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

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

 

РОЗГАЛУЖЕННЯ В SCRATCH

 

У Scratch можна використати команду якщо-інакше

 

для

 

організації повного розгалуження і команду якщо

 

для організації

 

неповного розгалуження.

 

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

На Сцені введено систему координат (мал. 3.21) для того, щоб положення виконавця на Сцені можна було задавати значеннями двох координат: х і у.

За замовчуванням довжина видимої частини Сцени 480 кроків виконавця, а ширина - 360 кроків. Тому якщо виконавець розміщується у видимій частині Сцени, то абсциса його положення може змінюватися від -240 до 240, а ордината - від -180 до 180.

Ця система координат може відображатися на Сцені, а може й не відображатися.

 

 

На початку алгоритму, наведеному на малюнку 3.22, використано ко

 

манду

 

з групи Рух для орієнтації виконавця на

 

Сцені в потрібному напрямку.

Щоб виконавець багаторазово виконував команду переміститися на 10

 

кроків, її включено в тіло циклу Завжди

 

Команди тіла цього

 

циклу виконуються доти, доки не буде натиснута кнопка Зупинити все

 

 

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

 

 

, У ході кожного виконання в тілі циклу цієї команди

 

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

Якщо результат виконання команди перевірки умови Ні (тобто виконавець ще не вийшов за праву границю Сцени), то команда задати значення х -240 не виконується. Після цього команди тіла циклу починають виконуватися в черговий раз і виконавець переміщується вправо.

 

Працюємо з комп’ютером

 

1. Запустіть програму Scratch.

2. Розмістіть Рудого кота в середині сцени.

3. Розмістіть в області скриптів алгоритм, наведений на малюнку 3.22. Зауваження. Для правильного вставляння умови в команду розгалуження потрібно:

 

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

 

 

з групи Оператори.

2. Уставити в ліве поле блока порівнян

 

ня блок

І з групи Рух.

 

3. Увести в праве поле блока порівняння потрібне число.

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

5. Зупиніть виконання алгоритму, вибрав-

 

ши кнопку Зупинити все

 

 

6. Видаліть алгоритм з області скриптів.

7. Розмістіть в області скриптів алгоритм, наведений на малюнку 3.23.

8. Виконайте алгоритм. Спостерігайте за рухом виконавця.

 

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

 

 

10. Збережіть створений проект у своїй папці у файлі вправа 3.3.1.

 

Найважливіше в цьому пункті

 

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

 

Команда перевірки умови визначає істинність чи хибність певної умови.

Якщо умова виконується, то вважається, що результатом виконання команди перевірки умови є істина, або true. Інакше, тобто якщо умова не виконується, то вважається, що результатом виконання цієї команди є хиба, або false.

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

Рішення

 

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

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

Алгоритм, який містить розгалуження, називають алгоритмом з розгалуженням.

Дайте відповіді на запитання

Який фрагмент алгоритму називають лінійним?

Чим відрізняється лінійний фрагмент алгоритму від циклу?

Що таке розгалуження в алгоритмі?

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

Чим характерне розгалуження як фрагмент алгоритму?

Чим відрізняється лінійний фрагмент алгоритму від розгалуження? Чим відрізняється розгалуження від циклу?

Як організувати розгалуження в Scratch?

Виконайте завдання

1°. Виконайте алгоритм:

1. Записати в зошит два цілих числа.

2. Записати в зошит суму записаних чисел.

3. Визначити, істинна чи хибна умова «Записана сума більша ніж ЗО?».

4. Якщо умова істинна, то записати в зошит «Сума більша ніж ЗО» і виконати команду 8, якщо умова хибна, виконати команду 5.

5. Визначити, істинна чи хибна умова «Записана сума менша ніж ЗО?».

6. Якщо умова істинна, повідомити «Сума менша ніж ЗО» і виконати команду 8, якщо умова хибна, то виконати команду 7.

7. Повідомити «Сума дорівнює ЗО».

8. Закінчити виконання алгоритму.

2°. Виконайте алгоритм визначення більшого з двох різних чисел за

наведеною блок-схемою (мал. 3.24) для таких наборів значень змінних:


3°. Виконайте алгоритм порівняння двох чисел за наведеною блок-схемою (мал. 3.25) для таких наборів значень змінних: а) а = 5,1, Ь = -2,8; б) а = 3,1, Ь = 3,1; в) а = -4,5, Ъ = -3,7. Наведіть три інших набори значень змінних, щоб для різних наборів виконання алгоритму відбувалося по-різному.

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

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

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

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

(а + ft) - с : (а - 2ft). Виконайте його при різних значеннях a, ft, с. Доберіть значення так, щоб для різних наборів значень виконання алгоритму відбувалося по-різному.

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

Складіть алгоритм руху виконавця вліво в середовищі Scratch. Дійшовши до лівої границі Сцени, виконавець повинен з’явитися біля правої границі Сцени і продовжувати рух уліво. Збережіть створений проект у своїй папці у файлі з іменем завдання 3.3.8. Складіть алгоритм руху виконавця вгору в середовищі Scratch. Дійшовши до верхньої границі Сцени, виконавець повинен з’явитися біля нижньої границі Сцени і продовжити рух угору. Збережіть створений проект у своїй папці у файлі з іменем завдання 3.3.9.

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

«Складання та виконання алгоритмів з розгалуженням у середовищі Scratch» 28 29 30 31 32 33

7. Збережіть створений проект у своїй папці у файлі з іменем практична 4.3.

8. Закрийте вікно програми Scratch.

3.4. ЦИКЛИ З ПЕРЕДУМОВОЮ

1. Що таке цикл? Чим характерний цикл як фрагмент алгоритму?

2. Що таке розгалуження? Чим характерне розгалуження як фрагмент алгоритму?

3. Чим цикл відрізняється від розгалуження?

ЦИКЛ З ПЕРЕДУМОВОЮ

Розглянемо таку задачу.

Задача 1.Є діжка, відро і колодязь з водою. Використовуючи відро, потрібно наповнити діжку водою.

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

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

Розглянемо виконавця з такою системою команд:

1. Наповнити відро водою.

2. Вилити воду з відра в діжку.

3. Перевірити умову «Діжка не повна?».

Алгоритм розв’язування цієї задачі для розглянутого виконавця у словесній формі виглядатиме так:

1. Перевірити умову «Діжка не повна?».

2. Якщо істина, то виконати команду 3, інакше (якщо хиба) виконати команду 6.

3. Наповнити відро водою.

4. Вилити воду з відра в діжку.

5. Виконати команду 1.

6. Закінчити виконання алгоритму.

На малюнку 3.26 наведено блок-схему цього алгоритму.

У цьому алгоритмі команди 3-5 можуть бути виконані більше ніж один раз і тому утворюють тіло циклу. Чергове виконання чи невиконання цих команд залежить від результату виконання команди перевірки умови «Діжка не повна?» у команді 1. Якщо цей результат істина, то команди тіла циклу виконуються ще раз, якщо ж хиба, то ці команди більше не виконуються.

Звертаємо вашу увагу!Команди тіла циклу саме «можуть бути виконані більше ніж один раз», а не «обов’язково виконуються більше ніж один раз».Адже розміри відра і діжки можуть бути такі, що під час першого ж виливання води з відра в діжку вона наповниться і виконання алгоритму закінчиться.

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

Розглянутий вище цикл називають циклом з передумовою.

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

Зазначимо, що серед команд тіла циклу можуть бути як лінійні фрагменти, так і розгалуження, а також інші цикли.

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

Зауважимо, що більшість алгоритмів містять і лінійні фрагменти, і розгалуження, і цикли.

 

ЦИКЛ З ПЕРЕДУМОВОЮ В SCRATCH

У Scratch можна використати команду повторювати поки

 

 

для організації циклу з передумовою. Але, на відміну

 

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

Блок-схема виконання команди циклу з передумовою в Scratch виглядає так (мал. 3.28):

 

 

Наприклад, виконуючи команду циклу з передумовою

 

 

виконавець виконуватиме команду тіла

 

циклу переміститись на 10 кроків, якщо результат виконання команди перевірки умови значення х< 20 хиба, тобто якщо абсциса положення виконавця на Сцені не менша (більша або дорівнює) ніж 20. І навпаки, якщо результат виконання команди перевірки умови значення х < 20 істина, тобто якщо абсциса положення виконавця на Сцені менша ніж 20, виконавець не виконуватиме команду переміститись на 10 кроків, а виконуватиме команду, наступну за цим циклом.

 

Аналогічно, виконуючи команду циклу з передумовою

 

 

виконавець переміщуватиметься

 

на 10 кроків, якщо він не доторкається до границі Сцени. Як тільки виконавець доторкнеться до границі Сцени, виконання команди переміщення не відбудеться і виконавець зупиниться біля границі.

У Scratch є й інші команди, які можна використати для організації циклу з передумовою, наприклад команда коли натиснуто клавішу. На-

 

приклад, цикл

виконуватиметься так:

 

1. Виконується команда перевірки умови натиснуто клавішу стрілка вправо?.

2. Якщо результат виконання цієї команди істина, виконується команда переміститись на 10 кроків, після чого знову перевіряється вказана умова, а якщо хиба - команда тіла циклу не виконується.

Цим циклом можна організувати рух виконавця за натиснутої клавіші стрілка вправо.

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

Працюємо з комп’ютером


5. Натисніть клавішу пропуск. Що відбулося з виконавцем і чому?

6. Замініть у команді циклу з передумовою клавішу пропуск на клавішу стрілка вгору.

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

8. Виконайте даний алгоритм. Спостерігайте за діями виконавця.

9. Натисніть клавішу стрілка вгору. Що відбулося з виконавцем і чому?

10. Збережіть створений проект у своїй папці у файлі з іменем вправа 3.4.1.

Найважливіше в цьому пункті

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

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

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

Дайте відповіді на запитання

. Що таке цикл в алгоритмі?

. Як виконується стандартний цикл з передумовою?

. Чи можуть команди тіла циклу не виконуватися жодного разу? Поясніть свою відповідь, проілюструйте пояснення прикладами.

. Чи може виконання циклу ніколи не закінчитися? Поясніть свою відповідь, проілюструйте пояснення прикладами.

. Чим відрізняється виконання команди циклу з передумовою повторювати поки в Scratch порівняно зі стандартною командою циклу з передумовою?

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

Виконайте завдання

. Виконайте алгоритми, подані блок-схемами (мал. 3.31):

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

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

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

. Складіть алгоритм у Scratch, щоб виконавець рухався вліво за натиснення клавіші стрілка вліво. Дійшовши до лівої границі Сцени, виконавець повинен з’явитися біля правої границі Сцени і продовжити рух уліво. Збережіть створений проект у своїй папці у файлі з іменем завдання 3.4.5.

. Складіть алгоритм у Scratch, щоб виконавець рухався вниз за натиснення клавіші стрілка вниз. Дійшовши до нижньої границі Сцени, виконавець повинен з’явитися біля верхньої границі Сцени і продовжити рух униз. Збережіть створений проект у своїй папці у файлі з іменем завдання 3.4.6.

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

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

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

1. Запустіть програму Scratch.

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

3. Збережіть створений проект у своїй папці у файлі з іменем практична 5.1.

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

5. Збережіть створений проект у своїй папці у файлі з іменем практична 5.2.

6. Закрийте вікно програми Scratch.

ПІДІБ’ЄМО ПІДСУМКИ РОЗДІЛУ З

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

 

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

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

3. Умовне висловлювання - це висловлювання виду «Якщо ..., то ...». Воно містить два висловлювання. Одне з них міститься після слова якщо (умова), інше - після слова то (висновок).

4. Розгалуження — це фрагмент алгоритму, який містить команду перевірки умови і під час кожного виконання якого деякі його команди будуть виконуватися, причому кожна по одному разу, а деякі - виконуватися не будуть. Це залежить від результату виконання команди перевірки умови.

5. Цикл «Повторити N разів» - це фрагмент алгоритму, який містить послідовність команд (тіло циклу), яка виконуватиметься вказану кількість разів. 34

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

 

7. Команда циклу з передумовою повторювати поки

 

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

 

 

Це матеріал з підручника Інформатика 7 клас Ривкінд

 

Категорія: Інформатика

Автор: admin от 11-02-2017, 09:59, посмотрело: 1610