Сторінка
2

Паскаль: цикл "поки" та його використання

fn=fn-2+fn-1, n>2. Вона називається послідовністю чисел Фібоначчі – за прізвиськом Леонардо Пізанського, який першим її описав. За першими двома її членами можна обчислити третій. Для обчислення четвертого перший член уже не потрібний, тому що f4=f2+f3. Для обчислення п'ятого достатньо пам'ятати лише третій і четвертий тощо. Обчислюючи члени послідовності один за одним, ми дістанемося будь-якого, почавши з перших двох. При цьому щоразу ми використовуємо лише два останніх значення і, обчисливши наступне, "забуваємо" перше з двох використаних. Нехай дано номер n, n>2, і треба обчислити fn. Опишемо ці обчислення. З попередніх міркувань випливає, що потрібні дві змінні для двох сусідніх членів і третя для наступного (назвемо їх fa, fb і fc), а також змінна m для зберігання номера останнього з обчислених членів. Спочатку fa=1, fb=1, m=2, (*) потім обчислимо fc:=fa+fb і збільшимо m на 1. Якщо значення fb і fc зробити відповідно значеннями fa і fb (fa:=fb, fb:=fc), то обчислення четвертого члена можна задати таким самим оператором fc:=fa+fb. Отже, поки m<n, виконуємо:

fc:=fa+fb, m:=m+1, fa:=fb, fb:=fc. (**) Очевидно, що з кожним виконанням fc:=fa+fb, m:=m+1 ми переходимо до наступного члена послідовності і в m запам'ятовуємо його номер. Оскільки значення m щоразу зростає, зрештою виявиться, що m=n, умова m<n стане хибною, і змінних fb і fc матимуть потрібне нам значення fn. Залишилося перекласти на Паскаль рядки, відзначені (*) і (**): fa=1; fb=1; m=2; while m<n do begin fc:=fa+fb; m:=m+1; fa:=fb; fb:=fc end; {m=n, значення змінних fc і fb – шукане} Відзначимо, що присвоювання fa:=fb та fb:=fc ні в якому разі не можна переставляти – можете проімітувати початок виконання цього алгоритму з переставленими присвоюваннями й переконатися, що значеннями змінної fc будуть аж ніяк не числа Фібоначчі. ç У загальному випадку рекурентне співвідношення задає залежність члена рекурентної послідовності sn від k попередніх у вигляді деякого виразу sn=F(sn-k, … , sn-1). Число k називається порядком рекурентного співвідношення. Якщо відомі sn-k, . , sn-1, то вираз F фактично задає обчислення sn. Назвемо це обчислення застосуванням рекурентного співвідношення. Припустимо, нам відомо рекурентне співвідношення sn=F(sn-k, . , sn-1) і перші k членів рекурентної послідовності. Треба за номером p обчислити sp. Знаючи перші k членів, можна застосувати до них співвідношення й обчислити sk+1; аналогічно за s2, . , sk+1 обчислюється sk+2 тощо. Щоразу для обчислення чергового члена потрібні тільки k останніх із попередніх. Отже, для опису цих обчислень потрібні:

• k змінних для k останніх членів (нехай їх імена A, B, … , X),
• змінна для нового члена (нехай її ім'я Y),
• змінна M для номера останнього з обчислених членів.

Треба створити "деталіконструктора", тобто запрограмувати:

• ініціалізацію змінних A, B, … , X першими k значеннями послідовності;
• застосування рекурентного співвідношення, тобто обчислення нового члена й запам'ятовування його в змінній Y;
• присвоювання значень змінних B, … , X, Y відповідно змінним A, B, … , X (назвемо це переприсвоюванням).

Тоді розв'язання задачі має вигляд:

ініціалізація змінних A, B, … , X; M:=k; while умова продовження do begin

присвоїти Y результат застосування рекурентного співвідношення до значень змінних A, B, … , X;

M:=M+1;

A:=B; . ; X:=Y {переприсвоювання} end У нашому випадку умова продовження – це просто вираз M<p. Розв'язанням такого вигляду є алгоритм обчислення числа Фібоначчі за його номером (приклад 4.3). Там k=2 і використано імена fa, fb, fc замість A, . , X, Y. Далі ми наведемо приклади розв'язання задач з іншими умовами продовження й іншим розташуванням "деталей конструктора", хоча в основі алгоритму все рівно буде цикл while. Зауважимо, що якщо порядок рекурентного співвідношення k=1, то для обчислення нового члена може виявитися достатнім однієї змінної. Так було в перших задачах, де, наприклад, при виконанні p:=p*a спочатку за старим значенням змінної p обчислювалося нове й потім їй же присвоювалося. Проте далі ми наведемо приклади, де послідовність задається співвідношенням порядку 1, але в умові продовження обчислень використовуються два останніх члени. Тому там будуть потрібні дві змінні. Використання рекурентних співвідношень дозволяє легко програмувати розв'язання задач, де шукані величини можуть бути виражені як члени рекурентних послідовностей. Треба:

• зрозуміти, що розв'язання задачі можна побудувати на використанні рекурентної послідовності;
• записати відповідне рекурентне співвідношення;
• визначити перші члени послідовності, що обчислюються без застосування співвідношення;
• сформулювати умову, за якої треба продовжувати застосування рекурентного співвідношення.

Після цього згадані вище "деталі конструктора" та порядок їх розташування в алгоритмі стають очевидними. Програма – це абсолютно точний опис дій, які треба виконати. Її неможливо написати, не сформулювавши чітко й точно, що ж саме повинно бути виконано. Рекурентні співвідношення якраз і дають точне вираження необхідних дій та служать надійною основою для написання програми. Насмілимося запевнити читача, що витрати часу на попереднє формулювання рекурентних співвідношень окупаються при написанні програми і дозволяють уникнути багатьох помилок. 2.2. Системи рекурентних співвідношень Є чимало задач, у розв'язанні яких використовуються не одна, а кілька рекурентних послідовностей. Члени послідовності можуть залежати від попередніх членів як "своєї", так і інших послідовностей. Ці залежності записуються у вигляді систем рекурентних співвідношень. Насправді, ми вже бачили зв'язані послідовності: члени послідовності 1!, 2!, 3!, … залежать від їх номерів і попередніх членів. Але послідовність номерів сама рекурентна, оскільки кожний номер на 1 більше попереднього. Задачі 4.* Написати функцію обчислення кількості десяткових цифр натурального числа. 5.* Один із варіантів алгоритму Евкліда обчислення найбільшого спільного дільника чисел a і b (НСД(a,b)) грунтується на обчисленні рекурентної послідовності {p}, де p1=max{a,b}, p2=min{a,b}, pn=pn-2 mod pn-1 при n>2. Шуканим є останнє ненульове значення послідовності. Уточнити алгоритм Евкліда у вигляді функції. 6. Послідовність {xn}, задана співвідношеннями x1=(a+m-1)/2, xi=( (m-1)xi-1 + a/x)/m при i > 1, сходиться до a1/m. Запрограмувати обчислення a1/m при довільному додатному дійсному a з точністю e , тобто за потрібне число приймається перше xn таке, що | xn-xn-1 |<e . 4.7. Послідовність сум {sn}, де sn=1+x+x2/2!+…+xn/n!, за умови 0£ x<1 "достатньо швидко" сходиться до ex. Запрограмувати обчислення ex при xÎ [0;1) із точністю e , тобто за потрібне число приймається перше sn таке, що | sn-sn-1 |<e . Запрограмувати обчислення ex при довільному x, застосовуючи "формули зведення" – рівності ex=e[x]e{x}, ex=1/e-x, де [x] і {x} позначають цілу й дробову частини x. Обчислити e[x] шляхом множення сталої e=2.7182818 на себе [x] разів. 4.8. Послідовність сум {sn}, де sn=1-x2/2!+…+(-1)nx2n/(2n)!, за умови |x|£ p /4 "достатньо швидко" сходиться до cos(x). Запрограмувати обчислення cos(x) при xÎ [-p /4; p /4] з точністю e , тобто за потрібне число приймається перше sn таке, що | sn-sn-1 |<e . Запрограмувати обчислення cos(x) при довільному x, застосовуючи тригонометричні формули зведення.