ІТО-Саратов-2016 - Храмова ЄІ - РЕКУРСИВНІ АЛГОРИТМИ У ЗАВДАННЯХ ЄДІ З ІНФОРМАТИКИ
На сайті ФІПД щорічно публікуються методичні рекомендації для вчителів, підготовлені на основі аналізу типових помилок учасників ЄДІ. У рекомендаціях з інформатики багато уваги приділено поняттю рекурсія. Це пов'язано з тим, що вкрай низький результат виконання завдання з цієї теми. 2015 року – це 25,7%, 2016 року показник виконання цього завдання зріс до 36,3. У Саратовській області цей показник збільшився з 21,64 до 48%.
При цьому КІМ ЄДІ з інформатики завдання 11 «Уміння виконати рекурсивний алгоритм» за рівнем складності відноситься до базового рівня з інтервалом виконання від 60 до 90%. Це завдання вирішується методом формального виконання (трасування) алгоритму, тобто внаслідок репродуктивної діяльності, знайомої учням.
Формування уявлення про рекурсивні виклики процедур і функцій належить до важливих предметних результатів навчання інформатики в середній школі, а саме поняття рекурсії є фундаментальним. Її вивчення в школі необхідне і важливе у плані загальної освіти.
Вчителю щодо цієї теми необхідно звернути увагу, що учні повинні засвоїти механізм здійснення рекурсивного виклику.
Що таке рекурсія?
Рекурсія (від латинського recursio – повернення) – це спосіб організації обчислювального процесу, у якому процедура чи функція під час виконання складових її операторів звертається сама себе.
Рекурсія є досить поширеним явищем, яке зустрічається у галузях науки, а й у повсякденному житті. Наприклад, ефект Дросте – це голландський термін для позначення особливого виду рекурсивного зображення чи словесногооповідання, у якому в об'єкті розміщується зменшений варіант цього об'єкта, у ньому – ще дрібніша копія тощо.
Принцип роботи рекурсії
У мовах рекурсивної програмування називається програма, яка звертається сама до себе. Однак рекурсивна програма не може викликати себе нескінченно. Отже, важлива особливість рекурсивного алгоритму – наявність умови завершення, що дозволяє програмі припинити викликати себе, інакше рекурсія перетвориться на зациклену і програма видасть помилку. Рекурсивні алгоритми реалізуються як підпрограм, що визначаються у програмі як процедури чи функції.
Як приклад розглянемо завдання, аналогічне представленому у проекті демонстраційного варіанту КІМ ЄДІ 2017.
Нижче записано рекурсивний алгоритм F.
Чому дорівнює сума всіх чисел, надрукованих на екрані під час виклику F(1)?
Спочатку необхідно вивчити текст програми та зрозуміти, що виконує ця функція. Функція отримує на вхід одне число n, виводить його на екран, потім за умови, що n Результат виконання
В результаті на екран будуть виведені числа 1, 2, 3, 4, 6, 5, 4. Їхня сума дорівнює 25.
Можна побудувати декартове дерево, що наочно показує принцип роботи рекурсії.
На схемі показані всі виклики рекурсивної функції F і позначені знаком * ті числа, які будуть виведені на екран.
У демонстраційному варіанті 2016 року цю модель завдання було трохи модифіковано, питання формулювалося у вигляді «Який рядок символів буде надруковано?». Завдання такого типу викликають у учнів більшу скруту. Для правильного виконання цього завдання необхідно розуміти, у якій послідовності відбуватиметься виклик рекурсивної функції, тобто знати механізм здійснення рекурсивного виклику.
Розглянемо ще два приклади, що добре відбивають принцип роботи рекурсії.
Рекурсивна процедура у всіх прикладах однакова, змінюється лише розташування оператора write(n). Проаналізуємо, що буде надруковано на екрані під час виклику F(9).
1. Оператор виведення параметра n стоїть на початку рекурсивного алгоритму:
Число n виводиться на екран відразу, як відбувається виклик рекурсивної процедури з параметром n. Програма працює аналогічно до розглянутої вище.
Результат роботи програми:
2. Оператор виведення параметра n стоїть наприкінці рекурсивного алгоритму:
Декартове дерево виглядатиме так само, як і в першому прикладі, проте порядок виведення чисел зміниться. Це з тим, що виведення на екран здійснюється лише по тому, як умова n>=7 стає хибним.
Пояснимо, як працює ця програма. При викликі F(9) відбувається виклик процедури F(6), і так як умова стає хибною, робота процедури завершується, і друкується число6. Далі керування повертається до процедури F(9), яка у свою чергу викликає F(8). Потім F(8) викликає F(5), друкується 5 і відбувається повернення до F(8). Викликається процедура F(7), що викликає F(4). Друкується 4 і відбувається повернення F(7), викликається F(6), друкується 6. Далі друкується 7, так як процедура F(7) закінчила свою роботу, потім 8, останнім буде надруковано 9.
Результат роботи програми:
Ефективним методом організації занять з цієї темі то, можливо розбір завдань біля дошки з поясненням вчителя, та був самостійна робота учнів із тими самими алгоритмами, реалізованими серед програмування. Учні можуть запустити ці алгоритми з різними аргументами та спрогнозувати результати їх виконання, а потім перевірити гіпотезу так, як показано в прикладах вище.
- Лещинер В.Р, Ройтберг М.А. Методичні рекомендації для вчителів, підготовлені на основі аналізу типових помилок учасників ЄДІ 2016 року з інформатики та ІКТ. [Електронний ресурс]/Режим доступу: http://www.fipi.ru/sites/default/files/document/1472532815/informatika.pdf, вільний.
| Вигляд подання доповіді | Усний виступ та публікація |
| Рівень | Середня (повна) загальна освіта |
| Ключові слова | рекурсія, ЄДІ, інформатика |
У статусі «Чернетка» Ви можете робити з тезами будь-які дії.
У статусі «Надіслано до Оргкомітету» тези проходять перевірку в Оргкомітеті. Статус «Чернетка» може бути повернений тезам або є зауваження рецензента, або тези перевищують необхідний обсяг, або на запит учасника.
Статус «Опубліковано» означає, що видано паперову версію тези і тезу змінити не можна. В деякихвкрай рідкісних ситуацій учасник може домовитися з Оргкомітетом про переведення тез у статус «Чернетка».