Паскаль. Прикладне програмне забезпечення


Види циклів

1. Доти, поки не...

Повернемося до обчислення квадратного кореня приклад 4.4:

X:=a+1/2; Y:=0.5X+a/X;

While absXYd Do

Begin

X:=Y; Y:=0.5X+a/X;

End;

Цей алгоритм задає послідовність дій такого вигляду:

X:= a+1/2;

Y:= 0.5X+a/X;

Обчислення умови продовження: True;

X:=Y;

Y:= 0.5X+a/X;

Обчислення умови продовження: True;

X:=Y;

Y:= 0.5X+a/X;

Обчислення умови продовження: False.

Якщо в цій послідовності замінити найперший оператор на Y:=a+1/2; X:=Y, то вона буде циклічною, починаючи з другого оператора, і циклом буде

X:=Y;

Y:= 0.5X+a/X;

Обчислення умови продовження

Можна було б подумати про оператор

Do X:=Y;

Y:=0.5X+a/X;

While absXYd;

Або в загальному вигляді

Do Послідовність Операторів

While Умова.

Такого оператора в мові Паскаль немає, а є схожий за виглядом

Repeat

Послідовність Операторів

Until Умова

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

Повторювати

Послідовність Операторів

Доти, поки не Умова.

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

Перепишемо алгоритм із прикладу 4.4 з використанням repeatоператора. Цикл повинен починатися оператором X:=Y, тому перед циклом треба задати ініціалізацію Y. Умовою завершення повинно стати

Not absXYd, або absXY=d,

Тобто Заперечення умови продовження:

Y:=a+1/2;

Repeat

X:=Y;

Y:=0.5X+a/X;

Until absXY=d;

{absXY=d; значення Y – шукане}

Оператору циклу з постумовою відповідає блоксхема, зображена на рис.5.1.

2. Для

Розглянемо алгоритм обчислення N!=1 2 N при N0, 0!=1, припускаючи, що всі змінні в ньому цілі й значення змінної n є невід'ємним:

F:=1;

{! }

K:=1;

While k=n Do

Begin f:=fk; k:=k+1 End

{k=n+1, останнім співмножником у значенні f було n}

Очевидно, що кількість виконань тіла циклу збігається зі значенням змінної N і, якщо N0, то оператор f:=fk виконується при K=1, 2, , N за N=0 не виконується жодного разу. Забудемо на хвилинку про останнє виконання оператора k:=k+1. Тоді дії, задані операторами після коментарю {!}, можна описати словами Для k=1, 2, , n виконати f:=fk або англійською мовою For k=1, 2, , n do f:=fk. А це вже майже оператор мови Паскаль:

For k:= 1 To n Do f:=fk

Його назва – Forоператор, або Оператор Циклу Переліком, оскільки в ньому задано перелік значень змінної k, при яких виконується тіло циклу. Ця змінна називається Параметром Циклу. Загальний вигляд forоператора:

For Ім'я := Вираз1 To Вираз2 Do Оператор

Ім'я позначає змінну цілого типу параметр циклу, а вирази однотипні з нею. У розд. 6 ми дізнаємося, що параметр циклу може бути не лише цілого типу. Частина оператора від слова For до слова Do називається заголовком циклу, а Оператор – тілом. Виконується forоператор не так просто, як це може здатися на перший погляд. Опишемо його докладніше.

Спочатку обчислюються значення виразів у заголовку й порівнюються. Ці значення називаються граничними; позначимо їх відповідно Lv і Hv. Якщо Lv Hv, то виконання закінчується. При цьому тіло циклу не виконується жодного разу, а параметр циклу нехай його ім'я K не одержує ніякого значення! Якщо ж Lv= Hv, то виконується K:= Lv, потім тіло циклу. Потім порівнюються K і Hv: при K Hv значення K збільшується на 1. Це збільшення називається Неявним, тому що явно ніяк не позначено в операторі. Потім знову виконується тіло циклу і збільшується значення параметра тощо.

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

Зверніть увагу на такі особливості:

· граничні значення обчислюються один раз. Вирази в заголовку можуть містити імена змінних – Їх зміни в тілі циклу ніяк не впливають на граничні значення;

    якщо Lv hv, параметр циклу після виконання Forоператора має значення Hv, інакше його значення залишається без змін; у стандарті мови Паскаль Заборонено присвоювання параметрові циклу.

У діалекті Турбо Паскаль остання заборона відсутня. Крім того, при порівнянні K і Hv насправді обчислюється значення виразу K Hv. Разом ці особливості дозволяють написати цикл For, тіло якого виконується аж ніяк не при значеннях параметра циклу, указаних у заголовку. Наприклад, для обчислення функції N!!, означеної за непарного N як 1 3 N і як 2 4 N за парного, в Турбо Паскаль можна, здавалося б, зробити такий трюк:

Ff:=1; If oddn Then lb:=1 Else lb:=2;

{n і lb або обидва парні, або обидва непарні}

For k:= lb To n Do

Begin ff:=ffk; k:=k+1 End

Але це неправильно! Між двома послідовними виконаннями ff:=ffk значення K збільшується двічі на 1 явно і неявно, і, поки K N, значення ff обчислюється правильно. Проте при K= N відбувається множення на N і явне збільшення K. Його значенням стає N+1. Воно порівнюється з N, N+1 N, тому K Збільшується неявно, і повторення тіла циклу продовжуються! Зрештою при черговому обчисленні ffk одержується значення, більше maxint. Комп'ютер такого не розуміє, і програма аварійно завершується.

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

Наведемо безпечне розв'язання задачі про N!!. Очевидно, що серед чисел 1, 2, 3, , N множниками в шуканому добутку повинні стати парні за парного N або, навпаки, непарні за непарного N. Можна перебрати всі ці числа, пропустивши непотрібні, у тому числі й 1:

Ff:=1;

For k:= 2 To n Do

If oddk=oddn Then ff:=ffk.

Оператор циклу переліком має ще одну форму:

For Ім'я := Вираз1 Downto Вираз2 Do Оператор,

Де всі позначення мають той самий зміст, що й у першій формі. Слово Downto замість слова To задає не збільшення, а зменшення на 1 значення параметра циклу після виконання його тіла. Крім того, тіло циклу не виконується жодного разу, якщо спочатку значення Виразу1 менше значення Виразу2. Наприклад, обчислення N!! за допомогою цього оператора задається так:

Ff:=n;

For k:= n1 Downto 2 Do

If oddk=oddn Then ff:=ffk.

Приклад 5.1. У математиці є чимало знаменитих формул, і одна з них – формула Бінома Ньютона:, де коефіцієнти Називаються Біноміальними. Напишемо функцію C обчислення біноміального коефіцієнта за значеннями N і K. Використовуючи функцію fct обчислення Факторіала, можна написати:

C:=fctn/fctkfctnk

Важко придумати щось гірше. Це все одно, що їхати з Берліна в Париж через джунглі Амазонії, піддаючи себе всіляким небезпекам. Поперше, ми змушуємо комп'ютер обчислювати ті самі значення тричі. Подруге, функція N! зростає дуже швидко за зростання N. Наприклад, 8!=40320, а в деяких системах програмування це вже більше, ніж maxint.

Подивимося уважніше на формулу біноміального коефіцієнта:

.

При використанні будьякої з рівностей треба обчислити два добутки й знайти їх частку, яка за означенням є цілою. Позначимо їх num і den – скорочення від англійських numerator і denumerator чисельник і знаменник. За другою з рівностей обчислення очевидні:

Num:= n; den:= 1;

For i:= 2 To k Do

Begin num:= numni+1; den:= deni End;

C:= num Div den

Все одно погано: наприклад,, але доводиться доходити до 8!=40320 і 7!=5040, щоб потім їх поділити й одержати всього лише 8. Між тим, у самій формулі Вже закладено обчислення послідовності значень

D0=1, D1= N/1, D2= N N1/1 2,..., DK= N N1... Nk+1/1 2... K.

Її члени задаються рекурентним співвідношенням Di= Di1 N+1 I/ I. Оскільки з кожних M послідовних натуральних чисел одне ділиться на M без остачі, то всі члени цієї послідовності цілі. Тому обчислення Dk можна задати так:

D:=1;

For i:=1 To k Do d:=dn+1i Div i

І нарешті, якщо K N/2, то останній цикл також задає зайві обчислення. Наприклад, при N=8, K=7 тіло циклу виконується 7 разів, хоча значення 8 утворюється вже після першого виконання. Скористаємося тим, що, і напишемо остаточний варіант:

Function C n, k: integer: integer;

Var d: integer;

Begin

If k n Div 2 Then k:=nk;

D:=1;

For i:= 1 To k Do d:=dn+1i Div i;

C:=d

End;