Кваліфікаційна робота бакалавра на тему: «РОЗРОБКА НАВЧАЛЬНОГО КОМПЛЕКСУ НА ТЕМУ «РЕКУРСІЯ»

Вступ    2

Розділ І. Теоретична частина    3

1.1. Поняття рекурсії і основні визначення    3

1.2. Форми рекурсивних процедур    8

1.2.1. Виконання дій на рекурсивному спуску    10

1.2.2. Виконання дій на рекурсивному поверненні    11

1.2.3. Виконання дій як на рекурсивному спуску, так і на поверненні    12

1.3. Задача про Ханойські вежі    14

1.4. Швидке сортування    17

1.5. Приклади задач    19

Розділ ІІ. Навчальна презентація    29

Розділ ІІІ. Тестуюча програма    32

Висновки    38

Література    39

 

Вступ

Навчальний комплекс складається з презентації, розробленої в програмному продукті Microsoft PowerPoint та тестуючої програми. Презентація складається з 27 слайдів, перехід між якими здійснюється за допомогою кнопок керування. В презентації містяться поняття рекурсії і основні визначення, а також приклади програм. В кінці презентації є слайд з контрольними запитаннями та варіантами відповідей. В тестуючій програмі подано 8 запитань, кожне з яких має 4 варіанти відповідей.

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

Рекурсивні означення дозволяють за допомогою скінченого висловлювання означити нескінчену множину об’єктів і тому на таких означеннях ґрунтується потужний математичний апарат. Аналогічно, за допомогою скінченої рекурсивної програми можна, не використовуючи конструкцій повторення, описати нескінченні обчислення, і тому рекурсія є потужним інструментом програмування.

 

Розділ І. Теоретична частина

1.1. Поняття рекурсії і основні визначення

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

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

З процедурою прийнято зв’язувати деяку множину локальних об’єктів, змінних, констант, типів і процедур, які визначенні локально в цій процедурі, а поза нею не існують чи не мають сенсу. Кожен раз, коли така процедура рекурсивно викликається, для неї створюється нова множина локальних змінних. Хоча вони мають ті ж імена, що і відповідні елементи множини локальних змінних, створеного при попередньому звернені до цієї ж процедури, їх значення різні. Наступні правила області дії ідентифікаторів дозволяють виключити який – небудь конфлікт при використані імен: ідентифікатори завжди посилаються на множину змінних, створену останньою. Те ж правило відноситься до параметрів процедури.

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

Інформація про стан процедури зберігається в стеку. При занадто великій кількості рекурсивних викликів відбудеться переповнення стеку. Тому при написанні рекурсивної програми, необхідно щоб кількість рекурсивних викликів була обмеженою і не занадто великою.

В рекурсивних підпрограмах можна виділити два процеси: рекурсивне занурення підпрограми у себе, що відбувається доти, доки параметр не досягне граничного значення, та рекурсивне повернення з підпрограми, що відбувається доти, доки параметр не досягне початкового значення.

Розглянемо функцію факторіалу n!. Як правило, її визначають як добуток перших n цілих чисел:

n! = 1 * 2 * 3 * . . . * n

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

Program Factorial;

Var

Fact : Longint;

n, i : Integer;

begin

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

Readln (n);

Fact :=1;

For i :=1 to n do Fact :=Fact * i;

Writeln (‘Факторіал n! = ‘, Fact);

End.

Але існує також інше означення факторіалу, в якому використовується рекурентна формула і яке має такий вигляд:

  1. 0! = 1
  2. для n > 0 n! = n * (n – 1)!

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

  1. F(1) = 1,
  2. F(2) = 1,
  3. для n > 2 F(n) = F(n – 1) + F (n – 2)

виглядає для обчислень краще, ніж пряма формула

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

Використання рекурсії дозволяє легко запрограмувати обчислення по рекурентним формулам. Наприклад програма, що використовує рекурсивну функцію для обчислення факторіала n! має наступний вигляд:

program Factorial;
var
n:Integer;


function Fact (i: Integer): Longint;
begin
if i=1 then Fact:=1
else Fact:= i*Fact(i-1)
end;
begin
Write (Введіть число n: ‘);

Readln (n);

Writeln (‘Факторіал n!= ‘, Fact(n));

end.

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Rozrobka Navch Kompl Rekursija (1.3 MiB, Завантажень: 4)

Сторінка: 1 2 3 4 5 6 7 8 9
завантаження...
WordPress: 23.66MB | MySQL:26 | 0,324sec