ПАСКАЛЬ: ЦИКЛ "ПОКИ" ТА ЙОГО ВИКОРИСТАННЯ

Цикл – це ряд подій, що регулярно повторюються в тому самому порядку.

З Оксфордського словника англійської мови

1. Поки...

Приклад 4.1. Розглянемо дещо штучну задачу: написати цілочислову функцію з ім'ям pow для обчислення степеня an за довільним натуральним a і n 0. Задача має елементарне розв'язання: an=enlna, і в тілі функції достатньо написати pow:=round(exp(n*ln(a))). Проте невід'ємні степені цілих чисел є цілими, тому спробуємо обійтися без нецілих виразів із функціями exp і ln.

За означенням, an є a a ... a, тобто a0=1, ai=ai-1 a для i=1, 2, ... , n. Це підштовхує до спроби обчислення an шляхом багаторазового множення на a. Спочатку шуканий степінь p=1, і треба n разів умножити його на a. Після першого множення p=a, і треба n-1 разів умножити його на a тощо. Перед останнім множенням p=an-1. Таким чином,

спочатку p=1 і треба виконати n множень на a, і поки залишаються "невикористані" множники a, ми множимо p на a, одержуємо новий степінь p і запам'ятовуємо, що "невикористаних" множників стало менше на 1.

Остання фраза, власне, і є алгоритмом обчислення an. Перекладемо його на мову Паскаль.

Нам потрібні змінні p і a для збереження степеня і його основи, а також змінні n і k для збереження показника степеня й кількості "невикористаних" множників. Змінні a і n – параметри нашої функції, тому їх початкові значення тут не важливі. Тепер алгоритм можна уточнити:

p:=1; k:=n;

поки k>0 виконувати {залишилися "невикористані" співмножники}

begin p:=p*a; k:=k-1 end

Якщо перекласти на англійську мову слова поки і виконувати як while і do, то утвориться:

p:=1; k:=n;

while k>0 do{залишилися "невикористані" співмножники}

begin p:=p*a; k:=k-1 end

Але це вже Паскаль! Справа в тім, що вираз вигляду

while умова do оператор

називається while-оператором, або оператором циклу з перед-умовою. Вираз "while умова do" називається заголовком циклу, "оператор" – тілом. Ми б назвали while-оператор циклом з умовою продовження, але цей термін дотепер у літературі не з'являвся.

Опишемо семантику оператора циклу та прокоментуємо всі ці назви. Виконання оператора циклу починається з того, що обчислюється умова, записана в заголовку. Якщо вона істинна, то виконується тіло циклу і знову обчислюється умова. Якщо вона істинна, усе повторюється. Якщо ж при черговому обчисленні умова стає хибною, то тіло циклу не виконується і взагалі виконання оператора циклу на цьому закінчується. Зокрема, якщо при першому обчисленні умова хибна, то тіло циклу не виконується жодного разу.

Отже, обчислення умови й виконання тіла повторюється, тобто має циклічний характер. Можна сказати, що обчислення умови й виконання тіла утворюють цикл, як день і ніч, змінюючи одне одного, утворюють добу. Істинність умови веде до продовження виконання оператора циклу, хибність – до його завершення, тому умова називається умовою продовження. Вона також називається перед-умовою, оскільки з її обчислення починається черговий цикл. Останній цикл неповний – у ньому тільки обчислюється умова (і виявляється хибною).

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

Повернемося до задачі. Послідовність операторів для обчислення an при a=2, n=3 задає процес

p:=1; k:=3;

обчислення умови k>0: true ;

p:=1*2; k:=3-1; {p=2; k=2}

обчислення умови k>0: true;

p:=2*2; k:=2-1; {p=4; k=1}

обчислення умови k>0: true;

p:=4*2; k:=1-1; {p=8; k=0}

обчислення умови k>0: false,

а при a=5, n=0 – процес

p:=1; k:=0;

обчислення умови k>0: false.

У вигляді коментарів тут указано стани пам'яті наприкінці циклів.

Запишемо, нарешті, функцію pow:

function pow(a, n:integer):integer;

var p, k: integer;

begin

p:=1; k:=n;

while k>0 do

begin p:=p*a; k:=k-1 end;

pow:=p

end;



Приклад 4.2. Розглянемо задачу: за цілим A>0 обчислити мінімальне n таке, що n!  A.

За означенням, n!=1 2 … n, тобто 1!=1, 2!=1! 2, 3!=2! 3 тощо, n!=(n-1)! n. Обчислимо 1! та порівняємо з A; якщо 1!Коментар із запереченням умови продовження після оператора циклу може істотно допомогти в розробці циклічних операторів, тому радимо записувати його.

Оформлення алгоритму у вигляді функції з параметром A залишається як вправа.

Досвідчені програмісти в деяких випадках користуються "нескінченним циклом" вигляду while true do оператор. Засоби, якими задається вихід із тіла циклу незалежно від значення умови продовження, ми розглянемо в підрозділах 5.3, 5.4.

Задачі

1.* Проімітувати виконання послідовності операторів:

а) i:=1; x:=1; y:=2;

while x0.

У прикладі 4.2 змінна n послідовно приймала значення, що утворюють арифметичну прогресію з першим членом 1 і різницею 1. Послідовність же значень змінної f не була прогресією, але визначалася першим членом f1=1 і співвідношенням fn=fn-1 n при n>1.

Послідовність, члени якої задовольняють деяке рекурентне співвідношення, також називається рекурентною.

Приклад 4.3. Розглянемо послідовність {f} чисел 1, 1, 2, 3, 5, 8, 13, … , у якій f1=f2=1, а наступні члени задаються рекурентним співвідношенням

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Припустимо, нам відомо рекурентне співвідношення 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

У нашому випадку умова продовження – це просто вираз M2. Шуканим є останнє ненульове значення послідовності. Уточнити алгоритм Евкліда у вигляді функції.

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.8. Послідовність сум {sn}, де sn=1-x2/2!+…+(-1)nx2n/(2n)!, за умови |x|  /4 "достатньо швидко" сходиться до cos(x). Запрограмувати обчислення cos(x) при x [- /4;  /4] з точністю  , тобто за потрібне число приймається перше sn таке, що | sn-sn-1 |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. Умовою продовження перевірок, очевидно, є умова k2 then

begin

d:=0; k:=2;

while k0 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, то умова продовження k2 можна взагалі вилучити:

issimple:= true; k:= 2;

while kКоли цей рахунок доходить до k, ми одержуємо те, що нам треба.

Це і є алгоритм пошуку k-го простого числа. Уточнимо його.

Нехай k>0. Означимо для зберігання натуральних чисел, що перебираються, змінну m. З алгоритму випливає, що нам потрібна ще змінна для збереження кількості простих чисел, які вже зустрілися. Нехай cs – ім'я цього "лічильника простих чисел". Спочатку cs=1, m=2 (у значенні лічильника враховано перше просте число 2). Далі починається цикл:

якщо умова продовження cs1 do

begin

if n mod k = 0 then

begin writeln(k); n:=n div k end

else k:=k+1

end

end



Задачі

9. При яких значеннях n, простих чи складених, останні два поліпшення алгоритму в прикладі 4.6 є істотними?

10. Напишіть два варіанти програми з прикладу 4.7, означивши функцію issimple згідно першого й останнього варіантів алгоритму з прикладу 4.6. Порівняйте час виконання програм за тих самих достатньо великих значень n.

11. Програма simpi із прикладу 4.7 задає перебір усіх натуральних підряд. Його легко скоротити приблизно втричі, якщо не перевіряти числа, явно кратні 2 або 3. Справді, за будь-якого натурального m із шести чисел 6m, 6m+1, 6m+2, 6m+3, 6m+4, 6m+5 достатньо перевірити тільки друге й останнє, а інші чотири кратні 2 або 3 і не можуть бути простими. Написати програму, що задає такий скорочений перебір.

Недоліком програми simpi є також те, що k-е просте число може виявитися більшим, ніж maxint. Доповнити умову продовження її циклу так, щоб при m=maxint подальші збільшення m були неможливі.

12.* Написати програму друкування всіх "близнюків", тобто пар простих чисел вигляду 6m-1 і 6m+1 для m>0, наприклад, 5 і 7, 11 і 13, 17 і 19 (але не 23 і 25). Природно, поки що мова йде про числа, не більші від maxint (у розд. 12 ми опишемо, як подавати та обробляти "великі" числа).

13. Поміняти процедуру simpdivisors із прикладу 4.8 так, щоб дільники друкувалися не стільки разів, скільки вони входять у розклад, а по одному разу, але з указанням після знака "**" їх степеня, якщо він більше 1. Наприклад, 13**2 за n=169, 2**3*3**2 за n=144, 2*5**2 за n=50.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать