(Основи інформатики) Chastina_III

5! = 1 х 2 х 3 х 4 х 5 і крок за кроком описати свої дії. Скоріш за все, ви отримаєте такий алгоритм:

1.Обчислюємо 2! = 1 х 2 = 2.

2.Обчислюємо 3! = 2! х 3 = 6.

3.Обчислюємо 4! = 3! х 4 = 24.

4.Обчислюємо 5! = 4! х 5 = 120.

Ви багато разів застосовували одну й ту саму обчислювальну процедуру: брали результат попереднього кроку обчислень і множили його на чергове число — інакше кажучи, використовували формулу k! = (k-1)! х k.

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

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

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

Зауважте, що рекурентна формула k! = (k-1)! х к в ньому набула вигляду f ← f і х к, де f — поточне значення факторіала, а k — номер кроку. Річ у тім, що комп’ютер може оперувати тільки зі змінними, а позначення на кшталт (k-1)!

він «не розуміє». Вираз f ← f і х k можна прочитати так: «новим значенням факторіала / вважати попереднє значення, помножене на k». Зверніть також увагу на допоміжну змінну k, значенням якої є номер кроку, і тому вона має збільшуватися на одиницю кожної ітерації циклу. Це забезпечується завдяки

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

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

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

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

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

•Загальний вигляд інструкції присвоєння такий: ім’я змінної ←

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

вказаного справа від значка «←», а потім це значення надається змінній, ім’я

якої вказане зліва від значка «←».

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

Базові структури алгоритмів — це певний набір блоків і стандартних способів їх з'єднання для виконання типових послідовностей дій.

До основних структурам ставляться наступні:

лінійні

що розгалужуються

циклічні

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

нижче:

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

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

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

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

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

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

що розгалужується, наведені нижче:

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

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

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

•блок перевірки умови

•блок, називаний тілом циклу Існують три типи циклів:

•Цикл з передумовою.

•Цикл з постумовою.

•Цикл із параметром (різновид циклу з передумовою)

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

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

зветься циклом з постумовою.

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

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

Стандартні блок-схеми циклічних алгоритмів наведені нижче:

Хід роботи.

Вихідні дані до роботи.

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

1.Увести два ненульові числа. Знайти їхню суму, різницю, добуток

ічастка. Вивести отримані значення.

2.Знайти периметр і площу прямокутного трикутника. Увести довжини його катетів a і b. Вивести отримані значення.

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

4.Знайти довжину окружності й площа кругу заданого радіуса R. У

якості значення π використовувати 3.14. Вивести отримані значення.

5.Знайти площу кільця, внутрішній радіус якого рівний R1, а

зовнішній радіус рівний R2 (R1 < R2). У якості значення π використовувати

3.14.Увести радіуси R1 і R2. Вивести отримане значення.

6.Увести довжину окружності. Знайти площу кола, обмеженого цієї окружністю. У якості значення π використовувати 3.14. Вивести отримане значення.

7.Увести площу кола. Знайти довжину окружності, що обмежує це коло. У якості значення π використовувати 3.14. Вивести отримане значення.

8.Дані дійсні числа x, y, z. Вивести на печатку мінімальне й максимальне із чисел x, y, z.

9.Дані дійсні числа x, y, z. Подвоїти ці числа, якщо x>y>z, і

замінити їхніми абсолютними значеннями, якщо умови не виконуються.

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

за такими даними.

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

2.Знайти номер першого мінімального елемента А, що вводиться із клавіатури послідовності чисел. Умова закінчення введення – уведення числа

0.

3.Знайти номер першого мінімального елемента з 10 чисел, що вводяться із клавіатури.

4.Знайти номер першого максимального елемента А, що вводиться із клавіатури послідовності чисел. Умова закінчення введення – уведення числа 0.

5.Дана послідовність: 1/1,1/2,1/3...1/n . Побудувати блок-схему з використанням циклу з постумовою, що виводить значення й номер члена послідовності, меншого 0,5. Тест: n=3, p(n)=0,3333.

6.Дано два цілих числа A і B (A < B). Вивести всі цілі числа,

розташовані між даними числами (включаючи самі ці числа), у порядку їх

зростання.

7.Дано не ціле число A і ціле число N (> 0). Вивести всі цілі ступені числа A від 1 до N.

8.Дано не ціле число A і ціле число N (N > 0). Вивести A у ступені

N:AN =A•A•...•A (числа A перемножуються N раз).

9.Розробити блок-схем, що обчислює факторіал уведеного числа.

Додаткові завдання.

Розробити блок-схеми алгоритмів відомих казок («Про Червону

шапочку», «Гидке каченя», «Подорож Нільса з дикими гусами» –

лінійний алгоритм; «У лукоморья дуб зелёный», «Фрагмент казок з каменем на роздоріжжі…», – розгалужений алгоритм; «Коза дереза»,

«Ріпка», - «Про рибака і рибку» – циклічний алгоритм.

КОНТРОЛЬНІ ЗАПИТАННЯ

1.З яких етапів складається рішення задачі на ЕОМ?

2.Що таке алгоритм та яким чином можна його описати?

3.Що таке схема алгоритмів?

4.З яких блоків може складатися блок-схема алгоритму?

5.Яким чином читається алгоритм? Чи обов'язкова наявність стрілочок

уграфічній схемі алгоритму?

6.Які властивості повинен мати алгоритм?

7.Які існують правила розробки алгоритмів?

8.Які різновидності структур алгоритмів ви знаєте. Наведіть приклади.

9.Які циклі називаються арифметичними? Наведіть приклади.

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

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

12.Про який алгоритм можна сказати, що він має складену структуру?

13.Що таке масив? Які види масивів ви знаєте?

14.Надайте приклад однета двовимірного масивів.

15.Який опис алгоритмів рішення завдань ви знаєте? Що таке алгоритмічна мова?

ЛАБОРАТОРНА РОБОТА №2

Тема: Алгоритмічна мова ЛОГО.

Мета роботи: Знайомство з алгоритмічною мовою ЛОГО, розробка блок-схем алгоритмів (прикладних програм) за допомогою мови ЛОГО.

Завдання:

1.Ознайомитися з алгоритмічною мовою ЛОГО;

2.Навчитися розробляти блок-схеми (прикладні програми) за допомогою мови ЛОГО;

3.Навчитися втілювати розроблені алгоритми за допомогою програмної оболонки Game Logo.

Звіт з лабораторної роботи повинний включати тему, мету, завдання

(теоретична частина), результати виконання роботи (індивідуальні завдання),

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

Теоретичні відомості.

Спочатку програміст дає черепашці прості накази, наприклад УПЕРЕД

100, що означає "пересунутися вперед на 100 кроків", або ЛІВОРУЧ 60,

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

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

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

Кроки черепашки дуже маленькі – дорівнюють відстані між двома сусідніми крапками на екрані, тому дія команди "УПЕРЕД 1" можна й не помітити як вона рухається.

Виконуючи команди ЛІВОРУЧ або ПРАВОРУЧ, черепашка повертається на заданий кут ( при цьому вона вважає, що кут заданий у градусах). При повороті черепашка залишається на місці, не зміщаючись ні в