Види циклів
1. Доти, поки не...
Повернемося до обчислення квадратного кореня (приклад 4.4):
X:=(a+1)/2; Y:=0.5*(X+a/X);
while abs(X-Y)>d do
begin
X:=Y; Y:=0.5*(X+a/X);
end;
Цей алгоритм задає послідовність дій такого вигляду:
X:= (a+1)/2;
Y:= 0.5*(X+a/X);
обчислення умови продовження: true;
X:=Y;
Y:= 0.5*(X+a/X);
обчислення умови продовження: true;
…
X:=Y;
Y:= 0.5*(X+a/X);
обчислення умови продовження: false.
Якщо в цій послідовності замінити найперший оператор на Y:=(a+1)/2; X:=Y, то вона буде циклічною, починаючи з другого оператора, і циклом буде
X:=Y;
Y:= 0.5*(X+a/X);
обчислення умови продовження
Можна було б подумати про оператор
do X:=Y;
Y:=0.5*(X+a/X);
while abs(X-Y)>d;
або в загальному вигляді
do послідовність операторів
while умова.
Такого оператора в мові Паскаль немає, а є схожий за виглядом
repeat
послідовність операторів
until умова
Він називається repeat-оператором, або оператором циклу з пост-умовою ("пост" означає "після"), і дослівно перекладається українською мовою як
повторювати
послідовність операторів
доти, поки не умова.
"Поки не" перетворює умову в умову завершення. Справа в тім, що спочатку виконується послідовність операторів (тіло), потім обчислюється умова, і якщо вона хибна, то знову виконується тіло тощо. Виконання оператора завершується після того, як при обчисленні умови одержано значення true. Таким чином, істинність умови означає завершення, а не продовження виконання всього оператора. Ми б назвали цей оператором циклу з умовою завершення, але такий термін у літературі не зустрічався.
Перепишемо алгоритм із прикладу 4.4 з використанням repeat-оператора. Цикл повинен починатися оператором X:=Y, тому перед циклом треба задати ініціалізацію Y. Умовою завершення повинно стати
not abs(X-Y)>d, або abs(X-Y)<=d,
тобто заперечення умови продовження:
Y:=(a+1)/2;
repeat
X:=Y;
Y:=0.5*(X+a/X);
until abs(X-Y)<=d;
{abs(X-Y)<=d; значення Y – шукане}
Оператору циклу з пост-умовою відповідає блок-схема, зображена на рис.5.1.
2. "Для"
Розглянемо алгоритм обчислення n!=1 2 … n при n>0, 0!=1, припускаючи, що всі змінні в ньому цілі й значення змінної n є невід'ємним:
f:=1;
{! }
k:=1;
while k<=n do
begin f:=f*k; k:=k+1 end
{k=n+1, останнім співмножником у значенні f було n}
Очевидно, що кількість виконань тіла циклу збігається зі значенням змінної n і, якщо n>0, то оператор f:=f*k виконується при k=1, 2, … , n (за n=0 не виконується жодного разу). "Забудемо на хвилинку" про останнє виконання оператора k:=k+1. Тоді дії, задані операторами після коментарю {!}, можна описати словами "для k=1, 2, … , n виконати f:=f*k" або англійською мовою "for k=1, 2, … , n do f:=f*k". А це вже майже оператор мови Паскаль:
for k := 1 to n do f:=f*k
Його назва – for-оператор, або оператор циклу переліком, оскільки в ньому задано перелік значень змінної k, при яких виконується тіло циклу. Ця змінна називається параметром циклу. Загальний вигляд for-оператора:
for ім'я := вираз1 to вираз2 do оператор
Ім'я позначає змінну цілого типу (параметр циклу), а вирази однотипні з нею. У розд. 6 ми дізнаємося, що параметр циклу може бути не лише цілого типу. Частина оператора від слова for до слова do називається заголовком циклу, а оператор – тілом. Виконується for-оператор не так просто, як це може здатися на перший погляд. Опишемо його докладніше.
Спочатку обчислюються значення виразів у заголовку й порівнюються. Ці значення називаються граничними; позначимо їх відповідно lv і hv. Якщо lv>hv, то виконання закінчується. При цьому тіло циклу не виконується жодного разу, а параметр циклу (нехай його ім'я k) не одержує ніякого значення! Якщо ж lv<=hv, то виконується k:=lv, потім тіло циклу. Потім порівнюються k і hv: при k
Коли після чергового збільшення значення k досягає hv, то виконується тіло циклу та після порівняння k і hv усе закінчується, тобто значення параметра циклу більше не збільшується.
Зверніть увагу на такі особливості:
•граничні значення обчислюються один раз. Вирази в заголовку можуть містити імена змінних – їх зміни в тілі циклу ніяк не впливають на граничні значення;
•якщо lv hv, параметр циклу після виконання for-оператора має значення hv, інакше його значення залишається без змін;
•у стандарті мови Паскаль заборонено присвоювання параметрові циклу.У діалекті Турбо Паскаль остання заборона відсутня. Крім того, при порівнянні k і hv насправді обчислюється значення виразу k<>hv. Разом ці особливості дозволяють написати цикл for, тіло якого виконується аж ніяк не при значеннях параметра циклу, указаних у заголовку. Наприклад, для обчислення функції n!!, означеної за непарного n як 1 3 … n і як 2 4 … n за парного, в Турбо Паскаль можна, здавалося б, зробити такий трюк:
ff:=1; if odd(n) then lb:=1 else lb:=2;
{n і lb або обидва парні, або обидва непарні}
for k := lb to n do
begin ff:=ff*k; k:=k+1 end
Але це неправильно! Між двома послідовними виконаннями ff:=ff*k значення k збільшується двічі на 1 (явно і неявно), і, поки k
Отже, краще не ризикувати й не задавати в тілі явні зміни параметра циклу. Нехай він буде чимось на зразок "священної корови" в індусів.
Наведемо "безпечне" розв'язання задачі про n!!. Очевидно, що серед чисел 1, 2, 3, … , n множниками в шуканому добутку повинні стати парні за парного n або, навпаки, непарні за непарного n. Можна перебрати всі ці числа, пропустивши непотрібні, у тому числі й 1:
ff:=1;
for k := 2 to n do
if odd(k)=odd(n) then ff:=ff*k.
Оператор циклу переліком має ще одну форму:
for ім'я := вираз1 downto вираз2 do оператор,
де всі позначення мають той самий зміст, що й у першій формі. Слово downto замість слова to задає не збільшення, а зменшення на 1 значення параметра циклу після виконання його тіла. Крім того, тіло циклу не виконується жодного разу, якщо спочатку значення виразу1 менше значення виразу2. Наприклад, обчислення n!! за допомогою цього оператора задається так:
ff:=n;
for k := n-1 downto 2 do
if odd(k)=odd(n) then ff:=ff*k.
Приклад 5.1. У математиці є чимало знаменитих формул, і одна з них – формула бінома Ньютона: , де коефіцієнти називаються біноміальними. Напишемо функцію C обчислення біноміального коефіцієнта за значеннями n і k. Використовуючи функцію fct обчислення Факторіала, можна написати:
C:=fct(n)/(fct(k)*fct(n-k))
Важко придумати щось гірше. Це все одно, що їхати з Берліна в Париж через джунглі Амазонії, піддаючи себе всіляким небезпекам. По-перше, ми змушуємо комп'ютер обчислювати ті самі значення тричі. По-друге, функція n! зростає дуже швидко за зростання n. Наприклад, 8!=40320, а в деяких системах програмування це вже більше, ніж maxint.
Подивимося уважніше на формулу біноміального коефіцієнта:
.
При використанні будь-якої з рівностей треба обчислити два добутки й знайти їх частку, яка за означенням є цілою. Позначимо їх num і den – скорочення від англійських numerator і denumerator (чисельник і знаменник). За другою з рівностей обчислення очевидні:
num := n; den := 1;
for i := 2 to k do
begin num := num*(n-i+1); den := den*i end;
C := num div den
Все одно погано: наприклад, , але доводиться доходити до 8!=40320 і 7!=5040, щоб потім їх поділити й одержати всього лише 8. Між тим, у самій формулі вже закладено обчислення послідовності значень
d0=1, d1=n/1, d2=n(n-1)/(1 2), ... , dk=n(n-1) ... (n-k+1)/(1 2 ... k).
Її члени задаються рекурентним співвідношенням di=di-1 (n+1-i)/i. Оскільки з кожних m послідовних натуральних чисел одне ділиться на m без остачі, то всі члени цієї послідовності цілі. Тому обчислення dk можна задати так:
d:=1;
for i:=1 to k do d:=d*(n+1-i) 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:=n-k;
d:=1;
for i := 1 to k do d:=d*(n+1-i) div i;
C:=d
end;