Реферат на тему:

Види циклів

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: при khv. Разом ці
особливості дозволяють написати цикл 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 (явно і неявно), і, поки kn,
тому k збільшується неявно, і повторення тіла циклу продовжуються!
Зрештою при черговому обчисленні ff*k одержується значення, більше
maxint. Комп’ютер такого «не розуміє», і програма аварійно завершується.

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

Наведемо «безпечне» розв’язання задачі про 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.

називаються біноміальними. Напишемо функцію 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

вже закладено обчислення послідовності значень

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

, і напишемо остаточний варіант:

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;

?

Похожие записи