ЕТАПИ СТВОРЕННЯ FLASH-ЛЕКЦІЙ НА ТЕМУ «ПАСКАЛЬ», Черга, Рекурсивні процедури та функції -

Перша лекція, яка була зроблена за Паскалем, була на тему «Черга» (рис. 27).

Малюнок 27 - Flash-лекція

У ній я спробував пояснити навчальний матеріал на тему «Черга», а також усередині лекції зробив перевірочні завдання для більш повного розуміння.

Лекція складається з трьох уроків:

Розповідається про ходи коня.

Тут я проілюстрував різні ходи коня, якщо він стоїть у положенні d4.

Розбір завдання про перебіг коня.

Дано позначення двох полів шахової дошки (наприклад, A5 та C2). Знайти мінімальну кількість ходів, які потрібні шаховому коневі для переходу з першого поля на друге.

Ідея рішення: черга можливих ходів коня.

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

Більш строгий алгоритм рішення:

Поміщаємо у чергу вихідне поле коня

Поки що (не знайшли потрібне число)

Вибираємо із черги перший елемент - клітину X,Y

Якщо це елемент НЕ шуканий

то Клітини, досяжні з X,Y за хід коня

якщо не кінцеві

і ще не помічені

поміщаємо в чергу і помічаємо

Далі представлена головна частина програми, що вирішує це завдання:

Found := (Sx=Ex) and (Sy=Ey);

while (not Found) do

У цій частині лекції я спробував показати, як працює алгоритм на тему чергу. (Малюнок 28)

Малюнок 28 - Останній урок flash-лекції

Рекурсивні процедури та функції

Було поставлено завдання зробити лекцію на тему: «Рекурсивні процедури та функції». Під час роботи лекція розділилася на три частини:

1) рекурсивне обчислення НОД.

2) Сума M із N чисел.

3) Розбір завдання про Ханойську вежу.

1) Рекурсивне обчислення НОД

У першій частині лекції треба було показати програму рекурсивного обчислення найбільшого загального дільника двох чисел a та b. (Малюнок 29)

Малюнок 29 - Перша частина лекції

Наступний матеріал я спробував проілюструвати у лекції:

функція NOD (a, b: longint): longint;

then NOD := NOD (a-b,b)

if a 12, то ЗНОВУ викликається функція NOD, але з параметрами (18-12,12) тобто з параметрами (6,12).

Зверніть увагу, що функція NOD, не завершивши своєї роботи, САМА викликає СЕБЕ, але вже зі зменшеним значенням одного з параметрів – (6,12) замість (18,12). Такі функції називаються РЕКУРСИВНИМИ. Необхідною умовою коректної роботи рекурсивних функцій є також умова НЕРЕКУРСИВНОГО (тобто без виклику функцією самої себе) обчислення результату, за певних аргументів виклику. Наприклад, функції NOD(a,b) такою умовою є умова a=b.

У нашому прикладі функція NOD викличе себе спочатку з параметрами (6,12), потім 6,6 - це і буде останнім викликом з відповіддю 6. Після чого ця відповідь буде послідовно передаватися функціям, що викликали аж до головної програми.

Програму обчислення найбільшого загального дільника чисел a та b можна написати і нерекурсивно – наприклад, так:

if a>b then a:=a-b else b:=b-a;

2) Сума M із N чисел

У цій частині лекції я показавскільки способів можна скласти суму M з N чисел. (Рисунок 30) Нехай нам потрібно написати програму, яка вводить числа M, N і послідовність з N чисел a[i] і підраховує кількість способів, яким з чисел a[i] можна скласти задану суму M.

Малюнок 30 -Складання суми M з N чисел

3) Розбір завдання про Ханойську вежу

В одній із стародавніх легенд говориться таке:

У храмі Бенареса знаходиться бронзова плита з трьома алмазними стрижнями. На один із стрижнів бог при створенні світу нанизав 64 диски різного діаметра з чистого золота так, що найбільший диск лежить на бронзовій плиті, а інші утворюють піраміду, що звужується догори. Брами Працюючи день і ніч, жерці переносять диски з одного стрижня на інший, дотримуючись законів Брами:

Диски можна переміщати з одного стрижня на інший лише по одному;

Не можна класти більший диск на менший.

Коли всі 64 диски будуть перенесені з одного стрижня на інший, і вежа, і храми, і жерці-браміни перетворяться на порох і настане кінець світу."

Програма рекурсивного розв'язання задачі:

Малюнок 31 - Рекурсивне вирішення задачі про Ханойську вежу