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

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

ГоловнаІнформатика, Компютерні науки → ПАСКАЛЬ: цикл "поки" та його використання - Реферат

ПАСКАЛЬ: цикл "поки" та його використання - Реферат

перекласти на Паскаль рядки, відзначені (*) і (**):
fa=1; fb=1; m=2;
while mbegin
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
У нашому випадку умова продовження - це просто вираз 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.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 |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 kbegin
if n mod k=0 then issimple:=false;
k:=k+1
end
Друге. Після того, як у циклі змінна 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
Р
Задачі
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.
Loading...

 
 

Цікаве