ІНФОРМАТИКА для 9 класу


Writeln; sum(x, y); writeln(‘y=‘,y); end.

Перевіряємо себе

 

Коли доцільно використовувати масиви як формальні параметри? image

Який вид підпрограм доцільно вибрати у разі використання масивів як формальних параметрів? Чому? image

Як можна передати у підпрограму двовимірний масив? image

 

Виконуємо

Напишіть програму, в якій здійснюється обчислення середнього арифме — тичного елементів одновимірного масиву. image

Напишіть підпрограму пошуку мінімального та максимального елементів масиву. image

Напишіть підпрограму сортування елементів масиву. image

 

10.3. Поняття рекурсії; рекурсивні алгоритми

У точних науках (математиці, фізиці, астрономії) часто трапляються такі розрахунки, коли наступне значення величини обчислюється через попереднє.

image Рекурсією називається така ситуація, коли підпрограма (процедура або функція) викликає сама себе.

Типова конструкція рекурсивної процедури має мати такий вигляд:

Procedure Rec (і:integer);

Begin

<Дії на початку рекурсії> If <Перевірка умови> Then Rec(і+1);

<Дії на виході з рекурсії>

End;

Function Rec (і:integer): тип функції;

Begin

<Дії на початку рекурсії> If <Перевірка умови> Then Rec:=Rec(і+1)*i;

<Дії на виході з рекурсії>

End;

Головне при написанні рекурсії – усвідомити, як правильно задати умову, що заглиблюватиме нас у рекурсію або, навпаки, виводитиме з неї.

Розглянемо приклад рекурсивного виклику на обчисленні степеня числа хn, де х – будь-яке дійсне число, а n – ціле, додатне число. Очевидно, що

X n = x n–1 ∙ x

X n–1 = x n–2 ∙ x

Якщо побудувати блок-схему цього алгоритму, доведеться для обчис — лення значення xn викликати функцію обчислення степеня x(n-1) і помно — жити це значення на величину х (див. рисунок).

Читать  Формалізація та алгоритмізація обчислювальних процесів

 

 

 

 

 

 

 

Блок-схема підпрограми step (x, n) піднесення x до степеня n:

Тобто приходимо до такого явища, як виклик підпрограми всередині підпрограми.

Постає питання, коли і як припинити цей процес. У цьому випадку зупинкою для обчислень буде обчислення x0, позаяк відомо, що нульо — вий степінь будь-якого числа дорівнює 1. Тобто рекурсивна функція для обчислення степеня числа матиме такий вигляд:

Приклад 10.3.1. Підпрограма step (x, n) піднесення x до степеня n:

Function Step(x:real; n:integer):double: Begin

If n = 0 then Step:=1 else Step:=Step(x, n-1)*x; End;

Проаналізуємо роботу цієї функції на прикладі пошуку значення 23. За першим викликом функції значення змінних дорівнюватиме відповідно:

X = 2; n = 3.

Оскільки значення n не дорівнює 0, спрацює гілка else, тобто почне виконуватись такий оператор:

Step:=Step(x, n-1)*x; де x дорівнюватиме 2, n – теж 2.

Цей оператор містить виклик функції step, тому виконання підпро-

Грами перерветься і виконається виклик тієї ж самої функції step, але з параметрами x=2 та n=1. Під час виконання повторного виклику функції ситуація повториться, тому що n покищо не дорівнює 0, і лише на четвер — тому виклику функції step параметр n досягне нульового значення, після чого спрацює гілка then, яка присвоїть значення функції 1.

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

Читать  ПЕРЕДДИПЛОМНА ПРАКТИКА – Адміністрування програмного комплексу Денвер (Denwer)

Приклад 10.3.2. Основна програма піднесення до степеня:

//текст підпрограми з прикладу 10.3.1

Var x:real; n:integer; begin

Write(‘Введіть число ‘); readln (x);

Write(‘Введіть показник степеня – ціле число ‘); readln (n);

Writeln(x, ‘ в степені ‘,n,’=‘, step(x, n)); end.

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

Зміст і потужність рекурсивного визначення, а також його головне призначення полягає в тому, що за допомогою скінченного виразу визнача — ється нескінченна множина об’єктів. Аналогічно за допомогою скінченного рекурсивного алгоритму можна визначити нескінченний процес, причому алгоритм не матиме повторень фрагментів тексту.

[Всего голосов: 6    Средний: 3.5/5]