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. Ланцюгові дроби


 

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

20264. Теорія Ван-дер-Ваальса (ВдВ) критичних явищ 99.5 KB
  Теорія ВандерВаальса ВдВ критичних явищ. Одне з рівнянь що описує реальні гази – рівняння ВдВ: для 1го моля газу 1 де а і b –сталі пов’язані із силами притягання і відштовхуванням відповідно. Перепишемо 1: При Т1 : ізотерма ВдВ ліва вітка – рідкий стан права – газоподібний.Перехід із рідкого стану в газоподібний і в зворотному напрямку при звичайних умовах відбувається не вздовж ізотерми ВдВ АВСDE а вздовж ізотерми АЕ яка одночасно є і реальною ізотермою.
20265. Просторові кореляційні функції та властивості кореляційних функцій 63 KB
  Тобто якщо для системи відома функція то ми знаємо яке розташування N частинок системи є найбільш ймовірним. Але через математичні складності обчислень потенціальної енергії взаємодії N частинок системи ця задача розв’язана в дуже обмеженому числі випадків. Тому запропонували новий метод: замість функції розподілу густини ймовірностей певних статистичних станів системи Гіббса розглядається набір з N кореляційних функцій різного порядку: унарна кореляційна функція яка характеризує густину ймовірності що одна частинка системи...
20266. Молекулярна структура рідин. Два способи опису молекулярної структури 64 KB
  dV1 dV2 r EMBED Equation.3 EMBED Equation.3 Г Р КР EMBED Equation.3 EMBED Equation.
20267. Поглинання звуку у в’язкопружних середовищах 80 KB
  Реологічне рівняння – це рівняння яке пов’язує тензор напруг з тензором деформацій і тензором швидкості деформацій. Для в’язкопружнього середовища реологічне рівняння: тензор напруг; тензор деформації; тензор швидкості деформації. та тоді наше рівняння буде мати вигляд: Звукова хвиля – це плоска хвиля. У в’язкопружньому середовищі на відміну від пружнього Підставляючи наше реологічне рівняння в рівняння руху отримаємо хвильове рівняння для звукової хвилі : Розв´язуючи це рівняння за умови Отримуємо вирази для швидкості...
20268. Оборудование подсистемы базовой станции (BSS) 523.5 KB
  1: контроллера базовой станции BSC Base Station Controller; базовой станции BTS Base Transceiver Station. Контроллер базовой станции BSC Контроллер базовой станции BSC центральная часть подсистемы базовой станции BSS. Контроллер BSC фирмы Ericsson рис. Контроллер BSC может контролировать радиосеть и рационально выравнивать временные дисбалансы в нагрузке на сеть.
20269. Оборудование подсистемы базовой станции (BSS). Блок приемопередатчика (TRU) 631.5 KB
  Он взаимодействует с другими компонентами через локальную шину Local Bus шину CDU шину синхронизации Timing Bus и Хшину Xbus. Блок объединения и распределения CDU CDU является интерфейсом между блоками TRU и антенной системой. CDU объединяет сигналы от нескольких приемопередатчиков и распределяет принятые сигналы ко всем приемникам. В функции CDU входит: объединение передаваемых сигналов; предусиление и распределение принимаемых сигналов; поддержка контроля антенной системы; фильтрация на радиочастоте; электропитание и контроль...
20270. ПОДСИСТЕМЫ И КОНФИГУРАЦИИ АППАРАТНЫХ СРЕДСТВ АХЕ10 893.5 KB
  Состоит из аппаратных средств модули временных TSM и пространственных SPM коммутаторов и центрального и регионального программного обеспечения; импульсный тактовый генератор Clock Pulse Generating and Timing CLT. Функциональные блоки GSS CLM Clock Module модуль тактового генератора; CLT Clock Pulse Generating and Timing импульсный тактовый генератор; GS Group Switch коммутационное поле; GSM Group Switch Maintenance техническое обслуживание коммутационного поля; NS Network Synchronization сетевая синхронизация; NSC...
20271. ОБОРУДОВАНИЕ GPRS 1.98 MB
  Между тем существуют некоторые технические особенности реализации оборудования GPRS среди которых следует выделить способ интеграции контроллеров пакетов PCU в подсистему базовых станции BSS. В качестве примера первого варианта организации оборудования GPRS может быть рассмотрено оборудование Alcatel в качестве второго Ericsson. ОБОРУДОВАНИЕ GPRS ПРОИЗВОДСТВА ALCATEL На рис.
20272. ОБОРУДОВАНИЕ GPRS. Сервисный узел поддержки услуг GPRS (SGSN) 1.58 MB
  Структурная схема SGSN В структуру SGSN входят: UNIX серверы блок маршрутизации интерфейсные модули интерфейсов на базе ОКС № 7 Gr Gd Gf Gs модули Gb интерфейса. UNIX серверы выполняют основные функции SGSN такие как управление мобильностью управление сессиями тарификация функции протокола GTP и др.Основные функции SGSN разделяются на две плоскости рис.