Розділ 14. Алгоритми з повтореннями

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

14.1. Оператори циклу

Оператори циклу призначені для реалізації циклічних алгоритмічних структур. Можливі дві принципово різні ситуації: кількість повторень відома наперед; кількість повторень заздалегідь визначити не можна.

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

У мові Pascal реалізовано три різновиди операторів циклу: цикл із лічильником, цикл з передумовою, цикл з післямовою.

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

Оператор циклу з лічильником

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

<змінна> — ідентифікатор деякої змінної порядкового типу даних, яка називається лічильником;

<початкове значення> — вираз тип, якого збігається з типом лічильника і його значения стає початковим значення лічильника;

<кінцеве значення> — вираз тип, якого збігається з типом лічильника і задає його кінцево значення;

<оператор> — оператор тіла циклу.

Робота цього оператора здійснюється за таким алгоритмом:

1. Обчислюється початкове значення.

2. Це значеїшя присвоюється параметру.

3. Обчислюється кііщеве значення.

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

5. Якщо значення параметра перевищує ( у випадку з використанням слова to) кінцеве значеїшя або менше (у випадку з використанням слова downto) ніж кііщеве значення, то оператор циклу завершує роботз'. В іншому випадку виконується тіло циклу, значення параметра змінюється на наступне (попереднє) і відбувається перехід до пункту 4.

Особливо слід підкреслити, що:

• і початкове, і кінцеве значення обчислюються до виконання оператора циклу й більше не перераховуються;

• ідентифікатор змінної є параметром циклу й згідно зі стандартом не мас змінюватися всередині оператора циклу. Нехтування цим правилом може призводити до непередбачуваних наслідків;

• після завершення циклу значення параметра циклу вважається не визначеним.

Приклад. Вивести таблицю квадратів натз'ральних чисел другого десятка.

for п := 11to 20do writeln(n, n * n: 5);

Приклад. Вивести великі латинські літери на екран у зворотпомз' порядкз'.

for ch := ‘Z’ downto ‘A’ do write(ch: 2);

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

Приклад. Використання складеного оператора в тілі циклу: for і:=1to n do begin s:=s+a; у:=2*х end;

Оператор while...do

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

while <логічиий вираз> do {заголовок циклу}

<оператор>; {тіло циклу}

Оператор тіла циклу виконуватиметься доти, доки істинним буде логічний вираз, який вказаний у заголовку циклу. Якщо в тілі циклу міститься декілька операторів, то вони беруться в операторні дужки begin...end;. Блок-схема оператора while...do зображена на рис. 14.1.

 Рис. 14.1 Блок-схема оператора циклу з передумовою

Приклад. Із клавіатури послідовно вводяться і додаються цілі числа, які не перевшцзчоть 10. Процес потрібно завершити при введенні числа, що більше 10.

Програма, що розв язує цю задачу, наведена нижче.

 

Оператор repeat...until

Цикл із післяумовою реалізується оператором repeat...until, в якому умова завершення циклу перевіряється після кожного виконання операторів тіла циклу. Синтаксис цього оператора такий:

repeat

<оператори> {тіло циклу}

until <логічний вираз> {заголовок циклу}

Оператори тіла циклу repeat... until

 

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

Після останнього оператора в тілі циклу repeat...until символ не записується. Оператори тіла цикл}' з післяумовою можна не брати в операторні дужки, навіть у тому випадку, якщо їх декілька. Блок-схема оператора repeat...until зображено на рис. 14.2.

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

У деяких програмах усередині операторів циклу доцільно використовувати операториbreak іcontinue. Перший із них перериває виконання циклу, а другий перериває виконання операторів тіла циклу і передає керування його заголовку.

Приклад. Розглянемо таку гру. Два гравці домовилися кидати гральні кості по черзі не більше 1000 разів. Виграє той, хто набере більшу суму балів. Однак гравці можуть кидати кості лише доти, доки

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

 

Виконуємо

1. Визначте, що буде виведено в результаті виконання фрагмента програми:

Розробіть програми для розв’язання таких задач:

а) вивести значения кореня від x для парних чисел х    в діапазоні від 2 до 10;

б) визначити суму цілих додатних непарних чисел менше 30.

14.2. Розв’язування обчислювальних задач

14.2.1. Особливості розв’язування обчислювальних задач

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

операцій (у деяких інших задачах, наприклад економічних, навпаки -вводяться і виводяться великі обсяги даїшх, над якими виконується незначна кількість операцій). Друга особливість полягає в тому, що для цих задач використовується досить простий принцип організації даних. І початкові дані, і розв’язки обчислювальних задач зазвичай подаються у десятковій системі числення окремими числами або наборами чисел. У задачах інших типів дані зазвичай мають складну неоднорідну структур^'.

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

Цим терміном позначається міра наближення результату, обчисленого комп'ютером, до точного математичного результат}'. Абсолютно точний розв’язок існує лише для деяких задач опрацювання цілих чисел. Для більшості інших задач розв’язки, отримані комп'ютером, відрізняються від точних унаслідок помилок і похибок. Помилки можуть виникати в постановці задачі, у процесі розробки алгоритм}' та під час програмування. Похибки виникають через наближений характер обчислювальних методів, неточність початкових даїшх, заокруглення значень у процесі виконання арифметичних операцій тощо.

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

Проте для більшості задач методів прямого обчислення або взагалі не існує, або воі-ш характеризуються низькою швидкодією, а тому слід застосовувати методи послідовного наближення, чи ітераційні методи. Вони дають змог}' отримати наближений розв'язок задачі шляхом багаторазового виконання однотипної обчислювальної процедури (тобто певної сукупності операцій). У такому разі початковими даними для кожної наступної процедури с результати виконання попередніх. Для обчислення кожного наступного члена геометричної прогресії використовується значення її попереднього члена. Процес виконання обчислювальної процедури в методі

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

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

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

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

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

 

14.2.2. Циклічні рекурентні алгоритми

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

швидкодію алгоритму. Розглянемо приклади використання рекурентних співвідношень.

Приклад. Потрібно розробити блок-схему алгоритму і програму обчислення п членів арифметичної прогресії з виведенням значення кожного члена.

 

Якби вимагалося обчислити будь-який, але лише один член прогресії, наприклад, i-й, то доцільно було б скористатися відомою формулою: u_i = а + (i-1)d Звичайно, цю ж формулу можна було б використати й для обчислення кожного з п-членів прогресії, проте ефективніше буде використати рекурентну залежність між ними:

Зазначимо, що під час обчислення кожного члена прогресії за формулою u_i = а + (i-1)d необхідно було виконати по одній операції множення, віднімання та додавання. У разі застосування рекурентної схеми потрібно виконати лише одну операцію додавання.

Блок-схема алгоритму обчислення і виведення значень членів арифметичної прогресії зображена на рис. 14.3. Нижче наведена також програма реалізації алгоритму.

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

 

Початок видения

 

Перевіряємо себе

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

2. Які перевалі дає застосування рекурентних співвідношень у циклічних обчисленнях?

3. Як здійснюється обчислення многочлена за схемою Горнера?

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

5. Якими рекурентними співвідношеннями зазначаються послідовності

а) 2, 4, 16. 256. ...

б) 2, ОД 2, 0.5, 2, ...

в) 2,5, 8, 11, 14,...

г) 2, -4, 16, -256, ...?

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

Виконуємо

1. Задана послідовність натуральних чисел: 1, 2. З, .... n. Використовуючи рекурентні співвідношення, напишіть програму обчислення суми та добутку непарних і парних чисел.

3. Створити блок-схему алгоритму обчислення значення виразу:

14.2.3. Циклічні обчислювальні алгоритми з невідомою

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

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

Члени геометричної прогресії пов’язані таким рекурентним співвідношенням:

 

 

Якщо е = 1/15, буде обчислено 6 членів прогресії, і останнім у цьому випадку стане значення 1/8. Якщо ж є = 0,02, то буде обчислено 8 членів. При цьому останній член прогресії дорівнюватиме 1/32.

Блок-схему алгоритму

обчислення членів спадної геометричної прогресії зображено на рис. 14.5. Програма, що розв’язує що задачу, наведена нижче.

Приклад. Із заданою точністю е потрібно обчислити суму:

 

 Рис. 14.6. Блок-схема алгоритму обчислення суми із заданою точністю

 

 

 

Ітерацій ний процес можна завершувати тоді, коли останній член стане меншим від заданої величніш є. Блок-схему алгоритму обчислення суми зображено на рис. 14.6.

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

1+0,5+0,25+0,125+0,0625+...із заданою точністю E.

 

14.2.4. Обчислювальні алгоритми із вкладеними циклами

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

Приклад. Задано дві послідовності додатних чисел: {а}=5, 7, 9, 11, 13 та {Ь} = 3, 4, 5, 6, 7, 8. Потрібно розробити блок-схему алгоритму та програму обчислення площ усіх прямокутників, довжиіш сторін яких можна вибрати з послідовностей {а} і {Ь}.

Опишемо алгоритм. Нехай довжина однієї сторони (позначимо її літерою а) дорівнює 5. Обчислимо площі всіх прямокутників, другі сторони яких мають довжини, що дорівнюють значенням членів послідовності {Ь}. Змінивши довжин}⁷ першої сторони (а=7), повторимо процедуру, і робитимемо так доти, доки а не перевищить 13. Блок-схему алгоритму зображено на рис. 14.7.

Нижче наведена програма, яка розв’язує цю задачу.

 

Рис. 14.7. Блок-схема алгоритму обчислення площ прямокутників

 

Підказка. Остачу від ділення числа а на b можна обчислити за допомогою операції a mod b.

14.3. Розроблення програм для циклічних алгоритмів

Нижче наведені деякі типові програми для циклічних алгоритмів.

1. Дано послідовність чисел 1, 3, 5, 7, 9, 11,...п. Розробити програму обчислення їх добутку.

Використаємо такі змінні: z — поточне значення числа; і — лічильник кількості помножених чисел; р — поточне значення добутку чисел; k — кількість чисел у заданої послідовності.

Кількість чисел у заданій послідовності можна обчислити за формулою k=(n+1)/2. Зміст програми обчислення добутку може бути таким.

2. Дано додатне дійсне число а. Розробити програму визначення мінімального значення п, при якому виконується умова а<2^п.

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

3. Розробити програму визначення суми цілих парних чисел, що більші 30, але менші 90.

Позначимо змінною x поточне значення парного числа, а змінною s — значення суми. Програма обчислення зазначеної суми чисел може бути такою:

 

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

Цю задачу можна розв’язати, наприклад, так. Спочатку виокремлюється крайня права цифра (молодший розряд), потім наступна цифра і т. д. Для виокремлення цифри молодшого розряду число дшиться повністю (цілком) на 10 і множиться на 10. Потім отримане значення віднімається від числа. Цифри, що виокремлюються, підсумовуються і обчислюється їх кількість. Використовуватимемо такі змінні: х — поточна цифра числа; s — сума цифр; k — кількість цифр у числі.

Уведіть, виконайте програму і доведіть, що вона функціонує правильно.

5. Первиїший внесок до банку становить 20000 грн. За кожний рік нараховується 15 % річних. За кожний рік знімається 500 гри. Розробити програму, що визначає суму внеску за перших п років.

Виконайте програму й доведіть, що вона функціонує правильно.

6. Літак па висоті 5000 м має швидкість 900 км/год. Вій починає підйом па висоту 8000 м. Через кожних 500 м його швидкість

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

Використаємо такі змінні: t — поточне значення часу підйому літака; v — поточна швидкість літака; h — поточне значення висоти літака. Програма моделювання цього процесу може мати такий зміст:

Виконайте програму і доведіть, що вона функціонує правильно.

Виконуємо

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

2. На рахунок у банку поклали 3000 гри. За кожний повний рік збереження коштів нараховується 12 % річних. Розробіть програму, що визначає, через скільки років ез'ма вкладу буде не менше 4500 грн.

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

 

 

Завдання

У таблицях 14.1 і 14.2 наведені завдаїшя для виконання практичної роботи. У табл. 14.1 наведені завдання, для розв’язування яких використовується оператор циклу for..to..do. У табл. 14.2 наведені складніші завдання. Для розв’язування цих завдань застосовуються різні типи операторів циклу. Для отриманого варіанта розробити програму розв’язання задачі та контрольний варіант розв’язку задачі. На практичній роботі учень уводить програму і налагоджує її. Необхідно добитися, щоб результат виконання програми збігся з контрольним варіантом.

 

Таблиця 14.1

 

Варіант	Завдання
1	Визначити площі 10 кругів. Радіус першого дорівнює 3 м, а радіус кожного наступного збільшується на 2 м
2	Радіус першого конуса дорівнює 2 м, а висота 10 м. Радіус кожного наступного конуса збільшується на 1 м, а висоти незмінні. Визначити об’єми 10 конусів
3	Визначити об’єми 10 куль. Радіус першої дорівнює 1 м, а кожної наступної збільшується на 2 м
4	Сторона а першого прямокутника дорівнює 4 м, а сторона Ь 7 м. У кожному наступному прямокутнику сторона а збільшується на 1 м, а сторона Ь — незмінна. Визначити площі 10 прямокутників

 

Таблиця 14.2

 

Варіант	Завдання	Початкові дані
1	Задані два парних числа аі і ач. Знайдіть суму всіх непарних чисел, більших аі, але менших ач.	а1=20; а2=60
2	Для дослідження нового автомобіля вирішено першого дня проїхати г км, а кожного наступного дня збільшзиати пробіг на у відсотків порівняно з попереднім днем. Через скільки днів дистанція пробігу досягне £ км?	z=1()0; y=3; s=500
3	Усі циліндри мають радіус основи г, висота першого дорівнює її, а висота кожного наступного збільшується на г. Висота останнього дорівнює Н. Знайдіть об’єм кожного циліндра	r=5; h=3; z=0.2; Н=5
4	3 яблуні зняли т яблук і поклали порівну в п кошиків (т>гі), але залишилося кілька яблук, менше ніж п. Скільки яблук поклали в кожний кошик і скільки залишилося?	m=37; n=7

Нижче наведено зразок оформлення програми для першого варіанта табл. 7.1.

Виконання роботи

1. Завантажити систему Turbo Pascal. Якщо не відкритий порожній файл, відкрити його (F10 → File → Enter → New → Enter).

2. Увести програму. Умисно зробити помилку у слові for, наприклад, увести far.

3. Порівняти введену програму з розробленою. Виправити всі виявлені помилки. Помилку у слові far не виправляти.

4. Зберегти програму в робочому каталозі (F10 → File → Enter → Save as → ім’я файла → Enter).

5. Виконати програму. Якщо в програмі до оператора циклу відсутні помилки, на екран буде видано повідомлення про помилку в операторі for: Error 3: unknown identifier. Виправити помилку та виконати програму.

6. Якщо в програмі е інші синтаксичні помилки, транслятор видаватиме на екран певні повідомлення. Евссвиправлення помилок>-Свиконання програми>.

7. Якщо програма викопана повністю, це означає, що синтаксичні помилки в ній відсутні, однак можуть бути логічні помилки. Викликати результат виконання програми на екран, для чого натиснути клавіші Alt+F5.

8. Порівняти отриманий результат із контрольїшм. Якщо результат правильний, зберегти програму (F10 → File →  Enter → Save → Enter). Перейти до пункту 10.

9. Якщо результат неправильний, знайти логічну помилку. Повторити дії, починаючи з пункту 6.

10. Виконати програм}' покроково, для чого послідовно натиснути клавішу F7. Переконатися, що програма функціонує правильно.

11. Установити режим для виконання програми з одночасним контролем поточних значень двох змінних. Для цього відкрити вікно Watch і ввести ім’я двох змінних. Першу змінну можна ввести так: F10 → Debug → Enter → Add watch → Enter → <ім’я першої змінної> → OK. Додавання другої змінної можна виконати так: Ins → <ім’я другої змінної> → ОК.

12. Виконати програму в покроковому режимі. Проаналізувати значення змінних, які з’являються у вікні Watch, та переконатися, що програма функціонує правильно. Закрити вікно Watch (Alt+F3).

13. Вийти із середовища Turbo Pascal

(F10 → File→ Enter → Exit → Enter).

 

 

Завдання

1. Із давніх часів математики намагалися вивести формулу, за допомогою якої можна обчислювати прості числа. Леопард Ейлер запропонував формулу п² —п + 41, де П — ціле невід’ємне число.

Перевірте справедливість цієї формули для всіх ті від 0 до 50. Чи можна зробити висновок про правильність формули?

2. Дано текстовий файл, у якому спочатку записане прізвище учня, а потім усі його тематичні оцінки з інформатики за семестр, у наступному рядку — прізвище наступного з'чия, оцінки якого, записані рядком нижче і т. д. Учні можуть навчатися в різних класах за різними програмами, тому кількість тематичних оцінок може бути різна.

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

Словничок

 

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

 

Це матеріал з підручника Інформатика 8 клас (поглиблений рівень) Гуржій