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


 

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

55709. ТРЕБОВАНИЯ К СОВРЕМЕННОМУ УРОКУ 33.5 KB
  Если планируется усвоение учащимися навыков и умений то предусматриваются способы их применения пробное применение знаний в сочетании с объяснением правил самостоятельное их применение...
55710. Інноваційний підхід до викладання географії шляхом застосування проектних технологій 125.5 KB
  Даний проект рекомендований для реалізації на уроках економічної і соціальної географії України і економічної і соціальної географії світу в 9х і 10х класах при вивченні теми €œНаселення€. Він дає змогу втілити ряд найважливіших положень сучасної педагогіки...
55711. Оптимальні шляхи реалізації науково-методичної проблеми школи 134.5 KB
  Характеристика сучасних підходів до реалізації науково-методичної проблеми закладу. Створення колективного досвіду на базі науково-методичної ідеї. Системний підхід до роботи над науково-методичною проблемою. Основні етапи роботи над науково методичною проблемою.
55712. Інтерактивні методи навчання як засіб формування інтересу до пізнання молодших школярів 284.5 KB
  Тому важливого значення на сучасному етапі набуває активізація пізнавальної діяльності учнів як необхідна умова шкільного навчання. Активізація пізнавальної діяльності учнів – необхідна умова шкільного навчання. Він – основа розвитку нахилів учнів а отже і їх професійного спрямування. Я помітила що стійкий пізнавальний інтерес пізнавальна активність учнів початкових класів виявляється в навчальній діяльності.
55713. Зведені таблиці Microsoft Excel (MICROSOFT OFFICE 2010) 610.5 KB
  Мета: Отримання учнями практичних навичок представлення інформації із традиційних списків у більш зручному вигляді.
55714. Використання на уроках географії літературних творів та фотографі 306 KB
  Допомогти розвитку пізнавальної діяльності, активності учнів можуть нестандартні прийоми на уроках. Педагог за допомогою мистецьких творів може акцентувати увагу на подіях, явищах природи, керувати сприйняттям і відтворенням образів.
55715. Розв’язування рівнянь та побудова графіків, що містять цілу та дробову частини числа 712 KB
  Розв’язування рівнянь що містять цілу і дробову частини. У роботі проаналізовано окремі способи розв’язування рівнянь зі змінною під знаком цілої та дробової частин зокрема графічний та аналітичні.
55716. Исследования графов и их изучение 126 KB
  Точки графа называются его вершинами а отрезки соединяющие их ребрами графа. Более того графы являются эквивалентными либо попросту одним и тем же графом если соответствующие вершины одного графа соединены так же как и соответствующие вершины другого то есть соединены...