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

Перекладемо цей алгоритм на Паскаль. Скористаємося while-оператором із умовою продовження f.

n:=1, f:=1,.

while f.

begin n:=n+1, f:=f*n end,.

{f>=A, f=n!, тому значення n — шукане}.

Коментар після циклу містить умову f>=A — по суті, заперечення умови продовження f.

Коментар із запереченням умови продовження після оператора циклу може істотно допомогти в розробці циклічних операторів, тому радимо записувати його.

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

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

Задачі.

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

а) i:=1, x:=1, y:=2,.

while x.

begin.

i:=i+1, x:=x*i, y:=y*2,.

writeln (i, ««, x, ««, y).

end,.

б) i:=1, x:=1, y:=2,.

while i<=10 do.

begin.

i:=i+1, x:=x*i, y:=y*2,.

writeln (i, ««, x, ««, y).

end,.

2. За цілим A>0 обчислити найбільше n таке, що n?! A.

3.* Написати функцію обчислення n!, де n? 0 (0≠1).

2. Рекурентні послідовності та співвідношення.

2.1. Деталі конструктора.

У прикладі 4.1 змінна p у процесі виконання операторів приймала значення 1, a, a2, a3, …, an. У цій послідовності перший член 1, а кожний наступний дорівнює попередньому, помноженому на a. Позначивши члени послідовності через p0, p1, p2, … pn, маємо рівність: pi=pi-1*a при i=1,2,…, n. Така рівність, що виражає член послідовності через попередні (один або кілька), називається рекурентним співвідношенням.

" Рекурентний" означає «зворотний». Справді, елемент послідовності тут визначається через попередні, і для його обчислення треба повернутися до них. Усім добре відомі рекурентні співвідношення вигляду an=an-1+d або bn=bn-1? q — їм задовольняють члени відповідно арифметичних або геометричних прогресій. Конкретна ж прогресія, тобто послідовність чисел, задається першим членом a1 і різницею d (або знаменником q). Власне, послідовність степенів у прикладі 4.1 p0, p1, p2, … — геометрична прогресія: вона визначається першим членом p0=1 і рекурентним співвідношенням pi=pi-1*a при будь-якому i>0.

У прикладі 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.

fc:=fa+fb, m:=m+1, fa:=fb, fb:=fc. (**).

Очевидно, що з кожним виконанням fc:=fa+fb, m:=m+1 ми переходимо до наступного члена послідовності і в m запам" ятовуємо його номер. Оскільки значення m щоразу зростає, зрештою виявиться, що m=n, умова m.

fa=1, fb=1, m=2,.

while m.

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.

Розв" язанням такого вигляду є алгоритм обчислення числа Фібоначчі за його номером (приклад 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 з точністю? , тобто за потрібне число приймається перше 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.7 182 818 на себе [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.

issimple:=true,.

if n>2 then.

begin.

d:=0, k:=2,.

while k.

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

issimple:= true, k:= 2,.

while k.

begin.

if n mod k=0 then issimple:=false,.

k:=k+1.

end.

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

Було б природно записати вираз (k.

simp:= true, tsn:= trunc (sqrt (n))+1, k:= 2,.

while (k.

begin.

if n mod k=0 then simp:=false,.

k:=k+1.

end,.

issimple:=simp.

Оформлення функції з заголовком.

function issimple (n:integer):boolean.

лишаємо для вправи. Відзначимо ще раз, що тіло функції треба записувати так, що при виконанні її виклику виконувався хоча б один оператор присвоювання з її ім" ям у лівій частині.?

З цього прикладу напрошується простий висновок: після того, як алгоритм розв" язання задачі написаний, майже ніколи не пізно і не завадить подумати про те, як його поліпшити.

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

Приклад 4.7. Прості числа 2, 3, 5, 7, 11, 13, … розташовані в натуральному ряду дуже загадковим чином. Нехай треба обчислити просте число за його номером у цій послідовності. Є формула, що задає просте число за його номером k, але обчислення за нею не простіші, ніж «лобові» :

Йти натуральним рядом і рахувати, скільки простих чисел зустрілося.

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

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

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

якщо умова продовження cs.

Ось переклад останніх фраз на Паскаль у вигляді програми з функцією issimple із попереднього прикладу:

program simpi (input, output),.

var k, m, cs: integer,.

function issimple (n:integer):boolean,.

…

end, {issimple}.

begin.

writeln («задайте номер (>0):»),.

readln (k),.

cs:=1, m:=2,.

while cs.

begin.

m:=m+1,.

if issimple (m) then cs:=cs+1.

end,.

{cs=k, значення m — шукане}.

writeln (k, «-е просте: «, m).

end.

Приклад 4.8. Як відомо, кожне натуральне число, більше 1, однозначно розкладається в добуток простих співмножників, наприклад, 13=13, 105=3? 5? 7, 72=2? 2? 2? 3? 3 тощо. Щоб побудувати розклад довільного числа, або його факторизацію, знайдемо його найменший дільник (очевидно, що він простій), запишемо його і поділимо на нього число. Подальші співмножники розкладу утворюються так само доти, поки в результаті ділень не утвориться 1. Наприклад, 36=2? 18 (виписали 2), 18=2? 9 (2), 9=3? 3 (3), 3=3? 1 (3).

Очевидно, що найменший дільник частки від ділення не може бути менше, ніж найменший дільник діленого. Тому після чергового ділення пошуки такого найменшого дільника можна починати не з 2, а з останнього дільника.

Алгоритм друкування розкладу n оформимо у вигляді процедури simpdivisors із параметром n («divisor» означає «дільник»). Можливі дільники будуть значеннями змінної k.

Спочатку k=2. Потім, поки n>1, перевіряється подільність n на k. Якщо ділиться, то виписується значення k і виконується ділення, інакше k збільшується, тому що менших дільників уже бути не може.

Наведене описання обчислень уточнюється в такому вигляді:

procedure simpdivisors (n:integer),.

var k: integer,.

begin.

k:=2,.

while n>1 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.