WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Цикл "поки" та його використання - Реферат

Цикл "поки" та його використання - Реферат

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, але в умові продовження обчислень використовуються два останніх члени. Тому там будуть потрібні дві змінні.
Приклад 4. Античні греки вміли приблизно обчислювати за допомогою послідовності чисел, що сходиться до нього. За алгоритмом Герона така послідовність утворюється застосуванням рекурентного співвідношення , починаючи з будь-якого додатного x1, наприклад, із x1=(a+1)/2. Однією з властивостей послідовності є те, що 1.
Умови продовження обчислень можуть бути різними, наприклад, >d або >d для деякого d>0. Розглянемо друге з них. Оскільки в ньому вказано два сусідніх члени, потрібні дві змінні для їх збереження, причому обидві повинні мати різні значення вже перед першою перевіркою умови продовження. Після того, як вона виявляється істинною, для обчислення нового члена передостанній член уже не потрібний, тому що рекурентне співвідношення має порядок 1. Тому в тілі циклу треба спочатку вказати переприсвоювання, а потім обчислення нового члена. Номера членів послідовності нас не цікавили, тому алгоритм має вигляд:
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;
{ abs(X-Y)<=d, значення Y вважається шуканим, адже |Y-a| | |. Тому, якщо додати всі члени від першого до останнього з таких an, що |an|>d за деякого d>0, то одержана сума відрізняється від sinx не більш, ніж на d.
Отже, треба обчислити sn= , де n невідомо, а відомо лише, що |an|>d, |an+1| d. Очевидно, sn=sn-1+an за будь-якого n>1, а s1=a1=x. Ці рівності виражають залежність значення суми від попередньої суми і відповідного доданка, тобто послідовність значень сум рекурентна. Помітимо, що при d0.
Знайдемо рекурентне співвідношення для послідовності доданків , виразивши an через an-1. Для цього у виразі для an побудуємо вираз, яким задається an-1:
=
= .
Отже, при n>1, a1=x. Запишемо одержані рекурентні співвідношення в систему:
Побудуємо за нею алгоритм обчислення. Оскільки порядок обох співвідношень 1, достатньо двох змінних, S і A, для збереження членів послідовностей. Спочатку A:=x; S:=0. Далі перед кожним обчисленням S:=S+A треба спочатку перевірити, що A>d. Після додавання A до S обчислюється новий доданок (значення A), і все повторюється. Таким чином, цикл складений діями в такому порядку:
перевірка умови A>d,
додавання S:=S+A,
обчислення нового значення A.
Нехай змінна I зберігає номер останнього обчисленого доданка; спочатку I=1. Оскільки при обчисленні нового доданка використовується його номер, то цей номер треба попередньо збільшити. Тепер алгоритм очевидний:
S:=0; A:=x; I:=1;
while A>d do
begin
S:=S+A; I:=I+1;
A:=A*(-x*x)/((2*I-2)*(2*I-1));
end
{A2 просте, якщо не ділиться без остачі на жодне з чисел 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 k0then 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 kbegin
if n mod k=0 then issimple:=false;
k:=k+1
end
Внесемо істотніші поліпшення. Перше. Якщо n=k1k2, де k1 і k2 обидва більше 1 і менше n, то одне з цих чисел обов'язково не більше, ніж . Тому для того, щоб дізнатися, чи є простим число n, достатньо перевірити його подільність на числа від 1 до [ ], де [x] позначає цілу частину x. Тоді умова продовження перевірок виражається як kЩоб не обчислювати trunc(sqrt(n))+1 при кожному виконанні циклу, означимо допоміжну змінну tsn і присвоїмо їй trunc(sqrt(n))+1.
Друге. Після того, як у циклі змінна issimple одержала значення false, подальші перевірки не потрібні, тому що вже ясно, що n не просте. Тому до умови продовження слід додати, що issimple має значення "істина". А перевірка цієї умови задається таким виразом: issimple.
Було б природно записати вираз (ksimp:= true; tsn:= trunc(sqrt(n))+1; k:= 2;
while (k0. Означимо для зберігання натуральних чисел, що перебираються, змінну m. З алгоритму випливає, що нам потрібна ще змінна для збереження кількості простих чисел, які вже зустрілися. Нехай cs - ім'я цього "лічильника простих чисел". Спочатку cs=1, m=2 (у значенні лічильника враховано перше просте число 2). Далі починається цикл:
якщо умова продовження cs0):');
readln(k);
cs:=1; m:=2;
while cs1, перевіряється подільність 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
Loading...

 
 

Цікаве