Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Астрономия->Реферат
Києво-Могилянська академія веде свою історію від 1615 року, коли за заповітом знатної київської шляхтянки Галшки Гулевичівни був заснований Братський ...полностью>>
Астрономия->Реферат
Термін “політика” виник ще в античній Греції. Він походить від давньогрецького слова polis (лат.), що означає місто-держава (в античній Греції). З наз...полностью>>
Астрономия->Реферат
Політично-активна молодь західної України сподівається на зміну політичних лідерів, що ринуться завоювати схильність молоді західної України, але зара...полностью>>
Астрономия->Реферат
9 листопада 1989 р. тисячі людей прорвалися через найвиразніший символ “холодної війни” у Європі – Берлінську стіну. Мало хто з учасників цієї знаменн...полностью>>

Главная > Задача >Астрономия

Сохрани ссылку в одной из сетей:

Реферат на тему:

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

1. Поки...

Приклад 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;

Приклад 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, то обчислимо 2!=2 1! і знову порівняємо тощо. Зрештою після чергового збільшення n виявиться, що n! A, і отримане значення n – шукане. Наприклад, при A=5 треба дійти до n=3, при A=120 – до n=5. Нам потрібна змінна n для запам'ятовування чисел 1, 2, 3 тощо, та змінна f – для значень 1!, 2!, 3! тощо. Отже,

спочатку n:=1, f:=1, і

поки f .

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

n:=1; f:=1;

while f do {значення n менше шуканого}

begin n:=n+1; f:=f*n end;

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

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

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

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

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

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.

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

Приклад 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<n стане хибною, і змінних fb і fc матимуть потрібне нам значення fn. Залишилося перекласти на Паскаль рядки, відзначені (*) і (**):

fa=1; fb=1; m=2;

while mdo

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 {переприсвоювання}




Похожие страницы:

  1. Маркетинг та його специфіка в банківській сфері

    Реферат >> Астрономия
    ... дають ніяких переваг, поки сумарний потік готівки ... івських послуг та його сегментація Джерела та аналіз досл ... йного банку Бостонська матриця та її використання для визначення стратегії ... продаж: класична крива з повторним циклом (кредити) “гребешкова” крива ...
  2. Капітал підприємства та його ефективне використання

    Лекция >> Экономическая теория
    ... однаковими частинами на кожний день циклу. Норматив оборотних коштів у витратах майбутн ... , якої вистачить для роботи аж поки замовлений матеріал надійде ... і подібні обмеження щодо строків його викорис­тання та інші фактори. Метод нарахування амортизац ...
  3. Циклічні коливання і кризи в економіці

    Реферат >> Экономика
    ... під час кризи триває доти, поки не буде встановлена ринкова рівновага ... фаз економічного циклу, деяке вирівнювання його трендової кривої та більш швидке ... ій (1880-1930 pp.) засновувався на використанні у промис­ловості електроенергії, розвитку важкого ...
  4. Дослідження конкурентоспроможності підприємства та його продукції

    Курсовая работа >> Маркетинг
    ... використання різних методів дослідження конкурентів та ринкових можливостей підприємства, визначення його ... можлива лише до того моменту, поки фірма не вичерпує резерви ... ями: 1.Залежно від стратегії життєвого циклу товарів фірми: маркетингові стратегії ...
  5. Науково-технічний прогрес та його значення в економіці і суспільстві

    Курсовая работа >> Экономика
    ... і процеси, і комплексну, автоматизуючу весь цикл робіт. У тому випадку, коли автоматизований ... дстані, можна (хоча в невеликих поки кількостях) накопичувати. Вона утворює ... обладнання та його налагодження становить 72298,13 тис. грн.; використання додаткових ...

Хочу больше похожих работ...

Generated in 0.0026760101318359