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

Умовний оператор

1. Дано ціле число. Якщо воно є додатнім, то додати до нього 1; в іншому разі не змінювати його. Вивести отримане число.

2. Дано ціле число. Якщо воно є додатнім, то додати до нього 1; в іншому випадку відняти 2. Вивести отримане число.

3. Дано ціле число. Якщо воно є додатнім, то додати до нього 1; якщо від’ємним, то відняти від нього 2; якщо нульовим, то замінити його на 10. Вивести отримане число.

4. Дано три цілих числа. Знайти кількість додатних чисел в початковому наборі.

5. Дано три цілих числа. Знайти кількість додатніх та від’ємних чисел в початковому наборі.

6. Дано два числа. Вивести більше з них.

7. Дано два числа. Вивести порядковий номер меншого з них.

8. Дано два числа. Вивести спочатку більше, а потім менше з них.

9. Дано дві змінні цілого типу: А і В. Якщо їх значення не є рівними, то присвоїти кожній зміннй суму цих значень, а якщо рівні, то присвоїти змінним нульові значення. Вивести нові значення змінних А і В.

10. Дано дві змінні цілого типу: А і В. Якщо їх значення не рівні, то присвоїти кожній змінній більше з цих значень, а якщо рівні, то присвоїти змінним нульові значення. Вивести нові значення змінних А і В.

11. Дано три числа. Знайти найменше з них.

12. Дано три числа. Знайти середнє з них (тобто число, розташоване між найменшим та найбільшим).

13. Дано три числа. Вивести спочатку найменше, а потім найбільше з даних чисел.

14. Дано три числа. Знайти суму двох найбільших з них.

15. Дано три змінні дійсного типу: А, В, С. Якщо їх значення упорядковані за зростанням, то подвоїти їх; в іншому випадку заменити значення кожної змінної на протилежне. Вивести нові значення змінних А, В, С.

16. Дано три змінні дійсного типу: А, В, С. Якщо їх значення упорядковані за зростанням або спаданням, то подвоїти їх; в іншому випадку замінити значення кожної змінної на протилежне. Вивести нові значення змінних А, В, С.

17. На числовій осі розташовані три точки: А, В, С. Визначити, яка з двох останніх точок (В або С) розташована ближче до А, і вивести цю точку та її відстань від точки А.

18. Дані цілочисельні координати точки на площині. Якщо точка співпадає з початком координат, то вивести 0. Якщо точка не співпадає з початком координат, але лежить на осі ОХ або ОУ, то вивести відповідно 1 або 2. Якщо точка не лежить на координатних осях, то вивести 3.

19. Дано координати точки, яка не лежить на координатних осях ОХ і ОУ. Визначити номер координатної чверті, в якій знаходиться дана точка.

 20. Дано координати двох точок, які не співпадають з початком координат. З'ясувати, чи можуть дані точки та початок координат бути вершинами трикутника.

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

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

алгоритму.

Існують 3 основні (базові) алгоритмічні структури, або три типи алгоритмів:

• Лінійний;
• Розгалужений;
• Циклічний (повторення).

Технології побудови алгоритму

Для розв'язування задач за допомогою комп'ютера існують різні технології програмування, наприклад, низхідне програмування (“зверху донизу”), висхідне (“знизу вгору”), пакетне, об'єктно-орієнтоване тощо і відповідно різні прийоми розробки алгоритму

Структурний підхід до побудови алгоритму є одним із методів розробки алгоритму, який:

ПЕРЕДБАЧАЄ:

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

ЗАБЕЗПЕЧУЄ:

• Легкість читання алгоритму
• Простоту перевірки правильності виконання алгоритму
• Зручність його модифікації

МЕТОД ПОКРОКОВОЇ ДЕТАЛІЗАЦІЇ – ЦЕ МЕТОД ПРОЕКТУВАННЯ АЛГОРИТМІВ «ЗВЕРХУ-ДОНИЗУ». Для реалізації цього алгоритму потрібно виконати такі дії:

• Розбити складну задачу на кілька простих
• Якщо задачі чергового рівня стають досить простими для незалежного розв’язання – закінчити процес деталізації
• Скласти для кожної простої задачі свій допоміжний алгоритм
• Скомпонувати результати проектування простих задач в єдиний алгоритм
• Проаналізувати роботу алгоритму.

Базова структура галуження

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

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

Повне галуження — це галуження, в якому визначені різні дії в разі виконання, і в разі невиконання заданої умови.

Неповне галуження — це розгалуження, в якому дії визначені тільки у разі виконання (або у разі невиконання) заданої умови.

Розвилка також називається, «якщо-то-інакше»,

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

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

Аргументи та результати.

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

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

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

Задачі «Виконання дій залежно від умов»

Вооlеап1°. Дано ціле число А. Перевірити істинність висловлення: "Число А є додатнім".

Вооlеап2°. Дано ціле число А. Перевірити істинність висловлення: "Число А є непарним".

Вооlеап3°. Дано ціле число А. Перевірити істинність висловлення: "Число А є парним".

Вооlеап4°. Дано два цілих числа: А, В. Перевірити істинність висловлення: "Вірні нерівності А>2 і В<3".

Вооlеап5°. Дано два цілих числа: А, В. Перевірити істинність висловлення: "Вірні нерівності  А>0 або В<-2".

Вооlеап6°. Дано три цілих числа: А, В, С. Перевірити істинність висловлення: "Справедлива подвійна нерівність А<В<З".

Вооlеап8°. Дано два цілих числа: А, В. Перевірити істинність висловлення: "Кожне  із чисел А и В непарне".

Вооlеап9°. Дано два цілих числа: А, В. Перевірити істинність висловлення: "Хоча б одне із чисел А и В непарне".

Вооlеап10°. Дано два цілих числа: А, В. Перевірити істинність висловлення: "Лише одне із чисел А и В непарне".

Вооlеап11°. Дано два цілих числа: А, В. Перевірити істинність висловлення: "Числа А и В мають однакову парність".

Вооlеап12°. Дано три цілих числа: А, В, С. Перевірити істинність висловлення: "Кожне із чисел А, В, С додатнє".

Вооlеап13°. Дано три цілих числа: А, В, С. Перевірити істинність висловлення: "Хоча б одне із чисел А, В, С додатнє".

Вооlеап14°. Дано три цілих числа: А, В, С. Перевірити істинність висловлення: "Лише одне із чисел А, В, С додатнє".

Вооlеап15°. Дано три цілих числа: А, В, С. Перевірити істинність висловлення: "Лише два із чисел А, В, С є додатніми".

Алгоритми та їх властивості.

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

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

Так для приготування яєчні потрібно виконати послідовність команд:

1.     Поставити сковороду на плиту.

2.     Покласти на сковороду шматочок вершкового масла.

3.     Увімкнути конфорку.

4.     Чекати, поки масло на сковороді розтане.

5.     Розбити два яйця і вилити їх вміст на сковороду.

6.     Посолити.

7.     Чекати, поки загусне білок.

8.     Вимкнути конфорку. 

А для того, щоб визначити вид трикутника за його кутами, якщо відомі його три сторони, потрібно виконати таку послідовність команд:

1.     Визначити сторону трикутника, яка не менша кожної з двох інших.

2.     Обчислити косинус кута трикутника, що лежить проти сторони, визначеної як результат виконання команди 1.

3.     Якщо визначений косинус кута від’ємний, то повідомити, що даний трикутник тупокутний, якщо ні, то якщо визначений косинус кута дорівнює нулю, то повідомити, що даний трикутник прямокутний, якщо ні, то повідомити, що даний трикутник гострокутний.

Такі послідовності команд (вказівок) називають алгоритмами.

Запам’ятайте!

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

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

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

1.     Порівняти довжини сторін трикутника і вибрати з них не меншу.

2.     Обчислити косинус кута трикутника за відомими трьома сторонами.

3.     Порівняти число з нулем (більше нуля, менше нуля або дорівнює нулю).

4.     Вивести повідомлення. 

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

Цікаві факти з історії!

Слово алгоритм походить від імені видатного вченого середньовічного Сходу Мухаммеда ібн Муси аль-Хорезмі (783 — 850) (рис. 2.3), який в своїх наукових працях з математики, астрономії та географії описав і використовував індійську позиційну систему числення, а також сформулював у загальному вигляді правила виконання чотирьох основних арифметичних дій: додавання, віднімання, множення і ділення. Європейські вчені ознайомились з його працями завдяки їхнім перекладам на латину. При перекладі ім’я автора було подано як Algorithmus. Звідси й пішло слово алгоритм. А розроблені ним правила виконання арифметичних дій вважають першими алгоритмами

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

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

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

Визначеність (або детермінованість (лат. determinans – визначальний)) алгоритму означає, що для  заданого набору значень початкових (вхідних) даних алгоритм однозначно визначає порядок дій виконавця і результат цих дій. Алгоритм не повинен містити команди, які можуть сприйматися виконавцем неоднозначно, наприклад, «Узяти дві-три ложки цукру», «Трохи підігріти молоко», «Вимкнути світло через кілька хвилин», «Поділити число x на одне з двох даних чисел a або b» тощо. Крім того, в алгоритмах недопустимі ситуації, коли після виконання чергової команди виконавцю неясно, яку команду він повинен виконувати наступною.

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

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

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

1.     Взяти число 2.

2.     Помножити взяте число на 10.

3.     Додати до одержаного числа 5.

4.     Якщо одержане число додатне, то виконати команду 3, якщо ні, то припинити виконання алгоритму.

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

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

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

Однак, крім масових алгоритмів, складаються і застосовуються алгоритми, які не є масовими. Таким, наприклад, є алгоритм розв’язування конкретного квадратного рівняння, наприклад, 2х²+5х+2=0 або алгоритм приготування конкретного салату (наприклад, грецького) на конкретну кількість осіб.

Поехали...!!!