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

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 з точністю ? , тобто за потрібне число приймається перше xn таке, що | xn-xn-1 |<? .

4.7. Послідовність сум {sn}, де sn=1+x+x2/2!+…+xn/n!, за умови 0? x<1 "достатньо швидко" сходиться до ex. Запрограмувати обчислення ex при x? [0;1) із точністю ? , тобто за потрібне число приймається перше sn таке, що | sn-sn-1 |<? .

Запрограмувати обчислення 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|? ? /4 "достатньо швидко" сходиться до cos(x). Запрограмувати обчислення cos(x) при x? [-? /4; ? /4] з точністю ? , тобто за потрібне число приймається перше sn таке, що | sn-sn-1 |<? .

Запрограмувати обчислення cos(x) при довільному x, застосовуючи тригонометричні формули зведення.

3. Числа прості й не тільки

Приклад 6. Напишемо функцію визначення, чи є натуральне значення її параметра, більше 1, простим числом.

Як відомо, число n є простим, якщо його додатними дільниками є лише 1 і n. Число 2 просте, а n>2 просте, якщо не ділиться без остачі на жодне з чисел 2, 3, … , n-1. Якщо ж воно ділиться хоча б на одне з них, то є не простим, а складеним. Отже, n – просте тоді й тільки тоді, коли (n=2) або (n>2 і n не ділиться на жодне з чисел 2, 3, … , n-1). Очевидно також, що n – складене, якщо n>2 і ділиться хоча б на одне з чисел 2, 3, … , n-1.

Таким чином, при n>2 треба перевірити подільність n на кожне з чисел k=2, 3, … , n-1.

Результат перевірок можна запам'ятати у вигляді кількості d дільників серед цих чисел. До початку перевірок d=0, тобто жодний дільник ще не знайдений, і з кожним знайденим дільником d збільшується на 1. Тоді умова d=0 є ознакою того, що число просте. Оформимо сказане у вигляді алгоритму:

if n>2 then

begin

d:=0;

для всіх k=2, 3, … , n-1 перевірити, чи ділиться n на k:

якщо ділиться, то d:=d+1

if d>0 then n – складене

else n – просте

end

else n – просте

Уточнимо цей алгоритм. Нехай issimple, тобто "є_простим" – ім'я функції, яку ми пишемо. Природно означити тип значень, що повертаються з неї, як булів. Тоді "n – просте" і "n – складене" уточнюються як issimple:=true і issimple:=false. На початку обчислень вважаємо, що число просте, тому присвоюємо issimple:=true. Тоді достатньо оператора розгалуження з умовою n>2 без else-гілки. Так само достатньо і скороченого оператора розгалуження з умовою d>0.

Фраза "для всіх k=2, 3, … , n-1 перевірити, чи ділиться n на k" задає повторення тих самих дій: перевірка подільності n на k та підготування до наступної перевірки, тобто збільшення k на 1. Спочатку k=2. Умовою продовження перевірок, очевидно, є умова k<n.

issimple:=true;

if n>2 then

begin

d:=0; k:=2;

while k<n do

begin

if n mod k = 0 then d:=d+1;

k:=k+1

end;

if d>0 then issimple:=false

end

Цей алгоритм можна істотно поліпшити. Почнемо з дрібниць. За оператором "if d>0 then …" змінній issimple фактично присвоюється значення виразу not (d>0). Простіше написати: issimple:=not(d>0). Насправді змінна d взагалі не потрібна. Дійсно, значенням issimple буде false, якщо хоча б один раз виконується оператор d:=d+1. Замість нього напишемо issimple:=false. Крім того, якщо n=2, то умова продовження k<n хибна при початковому значенні k, тому перевірку умови n>2 можна взагалі вилучити:

issimple:= true; k:= 2;

while k<n do {при n=2 тіло циклу не виконується жодного разу й значенням issimple залишається true}

begin

if n mod k=0 then issimple:=false;

k:=k+1

end

Друге. Після того, як у циклі змінна issimple одержала значення false, подальші перевірки не потрібні, тому що вже ясно, що n не просте. Тому до умови продовження слід додати, що issimple має значення "істина". А перевірка цієї умови задається таким виразом: issimple.

Було б природно записати вираз (k<tsn) and issimple як умову продовження. Проте