69133

Підпрограми, їх різновиди та способи використання. Процедури та функції користувача. Стандартні процедури та функції

Лекция

Информатика, кибернетика и программирование

Одним із найпростіших і найважливіших застосувань циклічних структур є генерування рекурентних послідовностей. Ефективність розв’язання деяких математичних задач цілком залежить від вибору рекурентної послідовності та способу її обчислення. До таких задач належать, зокрема...

Украинкский

2014-09-30

83.5 KB

3 чел.

Лекція 10. Тема:Підпрограми,їх різновиди та способи використання. Процедури та функції користувача.Стандартні процедури та функції.

План:

1. Деякі циклічні алгоритми та програми

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

3. Степеневі ряди

4. Ланцюгові дроби

1. Деякі циклічні алгоритми та програми

Одним із найпростіших і найважливіших застосувань циклічних структур є генерування рекурентних послідовностей. Ефективність розв'язання деяких математичних задач цілком залежить від вибору рекурентної послідовності та способу її обчислення. До таких задач належать, зокрема, задачі обчислення значень степеневих рядів і трансцендентних функцій, що розглядаються у розділах 3.3.2 та 3.3.3 відповідно. У розділі 3.3.1 дається означення рекурентної послідовності і розглядається загальний алгоритм її генерування.

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

Під час обчислення факторіала за програмою ехЗ_б багаторазово застосовується формула i! = (i-l)l -і, реалізована оператором factorial:-factorial*i. Наведемо значення лічильника циклу і та відповідні значення змінної factorial.

і

factorial

1

1

2

2! = 1!  *

2 = 2

3

3! = 2!  *

3 = 6

4

4!=3!  *

4 = 24

Отже, змінна factorial послідовно набуває значень 1, 2, 6, 24,....Позначивши члени цієї послідовності через p0, p1, p2, …pn, отримаємо рівність: pi=pi-1*i  де i = 1, 2, ..., n. Така рівність є прикладом рекурентного співвідношення. Дамо означення цього поняття.

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

Найпростішими прикладами рекурентних послідовностей є арифметична та геометрична прогресії, елементи яких пов'язані з попередніми елементами співвідношеннями а„ = дя_( + d та а„ = а„^\ • q, де d та q — деякі сталі величини. Іншим відомим прикладом рекурентної послідовності є послідовність чисел Фібоначчі, яку розглянемо детальніше.

Приклад

Послідовність {fі} чисел 1,1,2,3,5,8,13 де fi =f2= 1, а кожний наступний член дорівнює сумі двох попередніх, називається послідовністю чисел Фібоначчі. Таким чином, усі члени послідовності чисел Фібоначчі, починаючи з третього, задаються рекурентним співвідношенням fn = fn-2 + fn-1. Числа Фібоначчі мають декілька цікавих властивостей. Зокрема, сусідні числа Фібоначчі є взаємно простими; найбільшим спільним дільником двох чисел Фібоначчі є число Фібоначчі; число Фібоначчі парне тоді і тільки тоді, коли його номер кратний трьом. Зауважимо, що числа Фібоначчі використовуються при побудові ефективних алгоритмів розв'язання багатьох обчислювальних задач, таких як пошук екстремуму функцій, упорядкування даних.

Розробимо програму, що генерує послідовність п перших чисел Фібоначчі. Нам знадобиться змінна f і для зберігання значення поточного члена послідовності та змінні f1 і f2 для зберігання значень двох попередніх членів. Значення f і модифікуватиметься оператором fi :=fl+f2, який увійде до складу циклу з лічильником.

Після виконання цього оператора слід переприсвоїти значення змінних fl та f2 так, щоб вони містили нову пару чисел Фібоначчі. Це можна здійснити операторами f1:=f2 та f2:=fі. Порядок виконання останніх двох присвоювань є суттєвим; у разі виконання цих операторів у зворотній послідовності змінні f1 та f2 містили б значення того самого числа Фібоначчі. Результати роботи програми, що генерує послідовність чисел Фібоначчі.

program ехЗ_8; {послідовність чисел Фібоначчі}

var fl.f2.fi:integer:       {два попередніх та поточний член послідовності} i.n:integer:     {лічильник і загальна кількість членів послідовності}

begin

write('Enter the length of Fibonacci sequence: '):
readln(n); {ввести кількість членів}

fl:=l: f2:=l; {ініціалізувати два перших члени}

{якщо послідовність иістить}

if n>0 then write(fl); {принаймні один член}

if n>l then write(‘  '.f2): {принаймні два члени}

for i:=3 to n do {цикл обчислення наступних членів}

begin

fi:=fl+f2; {обчислити поточний член послідовності}

fl:=f2; {сформувати нову пару доданків}

f2:-fi:

write (‘  '.fi); {вивести чергове число Фібоначчі}

end:

end.

У загальному випадку рекурентне співвідношення визначає залежність члена послідовності {Sn} від k попередніх: Sn = F(Sn-k,..., Sn-1). Таке число k називається порядком рекурентного співвідношення. Поширимо реалізовану в програмі ехЗ_8 схему обчислень на рекурентні співвідношення довільного порядку k.

Для обчислення чергового члена послідовності потрібні k попередніх членів, які зберігатимемо у змінних flfk. Одразу зазначимо: значення Sh ...,Sk повинні бути задані у вигляді констант або введені з клавіатури. Тому змінні flfk можуть бути ініціалізовані на початку програми серією присвоювань fl:=S1,..., fk:=Sk, де S1,...,Sk вважатимемо константами. Члени послідовності, індекси яких більші за k, обчислюватимуться та виводитимуться в тілі основного циклу програми,а значення S1,...,Sk слід вивести до початку виконання цього циклу.

Припустимо, що треба отримати и членів послідовності. Член послідовності з індексом і має бути виведений лише в разі істинності умови і < п. Для членів з індексами і, більшими за k, виконання умови і<п гарантуватиметься оператором циклу, а для перших k членів цю умову слід перевіряти в операторах розгалуження. Наведемо один з можливих варіантів серії таких операторів разом із операторами ініціалізації змінних fl,..., fk.

fl:-Sl:  ... fk:-Sk;

if n > 0 then whte(fl);

if n > 1 then writer  \f2):

if n > k-1 then writer  '.fk);

Тепер розглянемо будову циклу, що обчислює члени послідовності з індексами k+l…п. Значення нового члена присвоюватимемо змінній fi: fi:=F(fl fk),

де F(...) — функція або вираз, що реалізує рекурентне співвідношення. Модифікувавши значення fі, слід виконати зсув значень змінних f 1,..., fk: f 1: =f2; f2: =f3;... fk :=fi: (знову звернімо увагу на порядок виконання присвоєнь). Після цього в тілі циклу залишиться лише вивести значення нового члена послідовності. Покажемо схематично, як виглядає основний цикл програми.

for i:=k+l to n do begin

fi:=F(fl fk);

fl:-f2:f2:-f3:...fk:-f1;

write(fi);

end:

3. Степеневі ряди

Розглянемо задачу наближеного обчислення значення функції у = sin x. Цю функцію можна розвинути у степеневий ряд Тейлора

Sin x = x-    n=1, 2, …

Наближене значення суми ряду можна отримати або обмежуючись сумою перших п його членів, або обчислюючи суму з наперед заданою точністю. Формула загального члена даного ряду є достатньо простою, але використовувати її не раціонально, оскільки для кожного члена ряду треба обчислювати степінь і факторіал. Набагато вищої ефективності можна досягти, обчислюючи член ряду за допомогою рекурентного співвідношення. Для знаходження цього співвідношення зауважимо, що чисельник n-го члена ряду дорівнює чисельнику (n-1)-го, помноженому на -х2, а знаменник - знаменнику (n- 1)-го члена, помноженому на величину (2n-2)*(2n-1) для п = 2, 3,.... Позначивши через а,- значення i-го доданка, отримаємо таке рекурентне співвідношення:

a         i=2, 3, …n

Справді, at = х, аг = а1* (-х2) / (2 • 3) = -х3/ З1, а3 = а2* (-х2) / (4 • 5) =x5/ 5! тощо. Отже, стає зрозумілим ефективний спосіб обчислення суми п перших членів ряду. Тепер перейдемо до обчислення суми ряду з наперед заданою точністю. По-перше, зазначимо, що із заданою точністю може бути обчислена сума лише збіжного ряду, а довільний степеневий ряд має певну область збіжності (можливо, порожню), тобто збігається не за всіх, а лише за деяких значень х (ряд, що розглядається нами як приклад, збігається для будь-якого дійсного х). По-друге, простий спосіб перевірки точності часткової суми ряду існує не для всіх рядів. Такий спосіб існує, зокрема, для знакопереміжних рядів, абсолютні величини членів яких, починаючи з деякого номера, утворюють монотонно спадну послідовність. Для таких рядів сума всіх членів, починаючи від (n+1)-го, є меншою за модулем від n-го члена. Ряд Тейлора для функції у = sin x задовольняє щойно розглянуті умови. Отже, для цього ряду

Якщо задана похибка є > 0, то визначити останній доданок можна з умови |an| < є, і тоді часткова сума sn=а1 + а2 +...+ аn відрізнятиметься від значення sin x не більше, ніж на величину є.

Приклад

Обчислимо наближене значення функції у = sin x, використовуючи її розвинення у ряд Тейлора. У змінній eps зберігатимемо значення похибки, а у змінній item -значення поточного члена ряду. Рекурентне співвідношення реалізоване присвоюванням item:-item*(-x*x)/(i*(i+l)), де лічильник і дорівнює подвоєному номеру члена ряду, збільшуючись на 2 на кожній ітерації циклу. Обчислення тривають доти, доки модуль величини item перевищує eps (модуль величини item записується на мові Pascal як abs(item)).

program ехЗ_9;  {обчислення функції sin(x)}

var x.s.iteimreal; {аргумент функції, сума та член ряду}

i:integer; {лічильник}

eps:real; {точність}

begin

writeln (sin(x) calculation'):

writeln('enter function argument x:'): readln(x);

writeln('enter mistake');

readln(eps); {увести похибку розрахунків)

s:-x: {ініціалізувати суму ряду}

item:-x: {ініціалізувати перший член ряду}

1:-2: {ініціалізувати лічильник}

while abs(item)>eps do {доки поточний член не задовольняє точності}
begin {обчислювати поточний член і суму ряду}

item:=item*(-x*x)/(i*(i+1); s:=s+item:

i:=i+2

end

writeln('s='.s:6:7.' sinC.x:3:3.')=’, sin(x):6:7.

1 error-'.abs(s-sin(x)):6:7):

end.

4. Ланцюгові дроби

Розглянуті у попередньому розділі степеневі ряди — один із інструментів обчислення значень математичних функцій, таких як sin л:, cos x, e1, In x, arctg x тощо. Іншим інструментом, що найчастіше використовується у вбудованих підпрограмах, є ланцюгові, або неперервні, дроби (про вбудовані, або стандартні, процедури та функції йтиметься в розділі 4.1.3). Дамо означення. Вираз

B0+ a1______________

    B1+a2________________

        B2+a3______________

                       B3+…

називається ланцюговим дробом. Нескінченний ланцюговий дріб позначається так:

а скінченний ланцюговий дріб із останнім знаменником bп — так:

Скорочений запис цих позначень є таким:

та

Ланцюгові дроби обчислюються з кінця.

Розглянемо послідовність {z,} знаменників ланцюгового дробу:

Zn=bn, zn-1=bn-1+an/zn,   zn-2 =bn-2+an-1/zn-1,

         Z1 =b1+a2/z2 ,                           z0 =b0+a1/z1

Послідовність визначається рекурентним співвідношенням zi = bt + аі+1 для всіх і = n-1,n-2,..., 0 і першим членом zn = bn а значення z0 дорівнює значенню дробу. Тому значення скінченного ланцюгового дробу можна обчислити за тим самим алгоритмом, що і значення членів рекурентної послідовності.

Висновки

Альтернативне розгалуження дає можливість виконавцеві алгоритму вибрати один із двох сценаріїв подальших дій залежно від того, чи виконується деяка умова. В мові Pascal альтернативні розгалуження реалізуються умовним оператором іf ...then...el se.

Одноальтернативне розгалуження дає можливість виконати певні дії в разі істинності деякої умови і не виконувати жодних дій в разі Н хибності. У мові Pascal одноальтернативне розгалуження реалізується скороченою формою умовного оператора: if...then.

Операторний блок, або складений оператор, — це послідовність операторів, що розпочинається ключовим словом begin та завершується ключовим словом end
(слова
begin та end інколи називаються операторними дужками). Блок сприймається як єдине ціле та може знаходитися в будь-якому місці програми, де синтаксисом мови припускається наявність оператора.

Поліваріантне розгалуження є узагальненням альтернативного розгалуження. Цей тип розгалуження дозволяє здійснити вибір однієї з декількох алгоритмічних гілок залежно від значення певного виразу. В мові Pascal таку алгоритмічну конструкцію реалізовано оператором вибору case.

Цикл - це послідовність дій, які повторюються. Оператори циклу задають повторення деяких дій доти, доки певна умова залишається істинною або доки умова не стане істинною. Оператори циклу мають заголовок і тіло. У заголовку записано умову продовження чи завершення циклу, а в тілі - блок операторів, виконання яких повторюється. Змінні, значення яких модифікуються в тілі циклу і впливають на істинність умови його завершення чи продовження,

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

У мові Pascal є три різновиди операторів циклу: оператор циклу з передумовою, оператор циклу з постумовою та оператор циклу з лічильником. Вибір певного оператора циклу для розв'язання тої чи іншої алгоритмічної задачі здійснюється залежно від типу умови завершення чи умови продовження циклу.

Оператор циклу з передумовою while—do застосовують у тому випадку, коли кількість повторень невідома і цикл може не виконатись жодного разу. Умова продовження циклу перевіряється перед першим виконанням його тіла. До початку виконання циклу потрібно ініціалізувати його параметри, а оператор зміни поточних значень параметрів слід включити до тіла циклу.

Оператор циклу з постумовою repeat...unti 1 застосовують тоді, коли кількість
повторень невідома і цикл завжди виконується принаймні один раз.
Умова завершення циклу перевіряється після виконання його тіла. До початку виконання циклу треба ініціалізувати його параметри, а оператор зміни поточних значень параметрів слід включити до тіла циклу.

Оператори циклу з лічильником for...to...do або for...downto...do використовують тоді, коли кількість повторень є відомою до початку виконання циклу.
Лічильник циклу є змінною деякого перелічуваного типу даних. Початкове значення лічильника має бути меншим за його кінцеве значення для оператора for...to...do і більшим — для оператора for...downto...do.

На кожній ітерації циклу for...to...do значення його лічильника збільшується на одиницю, а на кожній ітерації циклу for...downto...do — зменшується на одиницю. Робиться це автоматично.

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

Обчислення математичних функцій sin x, cos x, e*, In x і arctg x у вбудованих підпрограмах реалізується за допомогою ланцюгових дробів. Ланцюгові дроби обчислюють за допомогою рекурентного співвідношення.

Контрольні питання

1. Деякі циклічні алгоритми та програми

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

3. Степеневі ряди

4. Ланцюгові дроби


 

А также другие работы, которые могут Вас заинтересовать

37468. ФИЛОСОФСКИЕ СКАЗКИ ДЛЯ ОБДУМЫВАЮЩИХ ЖИТЬЕ или Веселая книга о свободе и нравственности 683 KB
  Как называется Истинная правда или Учебник для психолога по жизни . Про Клуб Синтон то есть тоже про жизнь и про психологов то есть про отношение к жизни. Она для повседневности для живого и чувствующего человека с утра до вечера его дня и жизни в привычном окружении близких и далеких для работы и праздников болезней и телевизора. Клуб этот мир созданный мною двенадцать лет назад попрежнему занимает в моей душе и жизни большое место: он много требует но и много дает.
37470. Новый этап в развитии физики рентгеновских лучей 54.26 KB
  Первое что бросается в глаза это следующее. фантастическое увеличение потока информации и все возрастающая узкая специализация приводят к тому что большинство книг представляет собой сборники а не монографии в прямом смысле этого слова. Из них 28 это сборники обзоров такого же типа что и рецензируемая книга. Разумеется в том что такая книга будет неровной будет содержать повторения.
37471. Классики мировой философии о политику, государстве и праве 26.46 KB
  Противопоставление Гераклитом аристократического права и государства справедливым законам за которые люди должны биться как за стены родного города. Четыре свойства государства: мудрость мужество рассудительность справедливость. Структура государства. Разработал теорию возникновения и существования государства ради достижения благой жизни.
37472. Психологическая защита в социуме 968 KB
  Ключникова посвящена теме психологической защиты человека живущего в бурном потоке современного социума. В ней описываются психологические механизмы и законы защищенности человека помогающие человеку стать защищенным и успешным мастером жизни. Книга богато иллюстрированная историями из обширной консультативной практики автора содержит многочисленные советы приемы и методы вдумчивое применение которых сделает человека значительно более уверенным и успешным.Автор развивает и конкретизирует подход суть которого состоит в разумном сочетании...
37473. Гісторыя Беларусі (у кантэксце сусветнай гісторыі) 8.25 MB
  Мандрык Гісторыя Беларусі у кантэксце сусветнай гісторыі Віцебск 2008 УДК 947. 4 Беи 73 Г 46 Друкуецца па рашэнні навуковаметадычнага савета Віцебскага філіяла Установы адукацыі Федэрацыі прафсаюзаў Беларусі â€œМіжнародны інстытут працоўных і сацыяльных адносінâ€. Гісторыя Беларусі у кантэксце сусветнай гісторыі. 4 Беи 73 Г 46 Віцебскі філіял Установы адукацыі Федэрацыі прафсаюзаў Беларусі â€œМіжнародны інстытут працоўных і сацыяльных адносінâ€.
37475. Проектирование и конструирование талевого блока газовой скважины 1.12 MB
  5 Диаметр отверстия в стволе ротора мм 700 Расчетная мощность привода ротора кВт 370 Мощность бурового насоса кВт 950 Расчетная мощность на валу буровой лебедки кВт 670 Наибольшая оснастка 5x6 Диаметр каната мм 28 Диаметр шкивов наружный мм 1 шкив 1000; 10 шкивов 900 Максимальная подача бурового насоса л с 50.1 Оснастка талевой системы Порядок прохождения талевого каната через канатные шкивы кронблока и талевого блока имеет существенное значение для распределения нагрузки на ноги вышки и для правильной навивки каната на барабан...