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

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

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

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

ПАСКАЛЬ: ЦИКЛ "ПОКИ" ТА ЙОГО ВИКОРИСТАННЯЦикл - це ряд подій, що регулярно повторюються в тому самому порядку.
З Оксфордського словника англійської мови
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!спочатку n:=1, f:=1, і
поки fПерекладемо цей алгоритм на Паскаль. Скористаємося while-оператором із умовою продовження fn:=1; f:=1;
while f=A, f=n! , тому значення n - шукане}
Коментар після циклу містить умову f>=A - по суті, заперечення умови продовження fКоментар із запереченням умови продовження після оператора циклу може істотно допомогти в розробці циклічних операторів, тому радимо записувати його.
Оформлення алгоритму у вигляді функції з параметром A залишається як вправа.Р
Досвідчені програмісти в деяких випадках користуються "нескінченним циклом" вигляду while true do оператор. Засоби, якими задається вихід із тіла циклу незалежно від значення умови продовження, ми розглянемо в підрозділах 5.3, 5.4.
Задачі
1.* Проімітувати виконання послідовності операторів:
а) i:=1; x:=1; y:=2;
while xbegin
i:=i+1; x:=x*i; y:=y*2;
writeln(i, ' ', x, ' ', y)
end;
б) i:=1; x:=1; y:=2;
while i0 обчислити найбільше 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. Отже,
поки mfc:=fa+fb, m:=m+1, fa:=fb, fb:=fc. (**)
Очевидно, що з кожним виконанням fc:=fa+fb, m:=m+1 ми переходимо до наступного члена послідовності і в m запам'ятовуємо його номер. Оскільки значення m щоразу зростає, зрештою виявиться, що m=n, умова m
  • <<
  • Перша Попередня 1
    2 Наступна Остання
  • >>
  • Loading...

     
     

    Цікаве