close

Вход

Забыли?

вход по аккаунту

Чаркин Юрий Николаевич. Программно-методическое обеспечение темы «Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi» в профильном курсе информатики

код для вставки
2
АННОТАЦИЯ
ВКР бакалавра на тему «Программно-методическое обеспечение темы
«Организация рекурсивных алгоритмов в языках программирования Pascal и
Delphi» в профильном курсе информатики» содержит
страниц текста - 180,
рисунков - 182, таблиц – 17, использованных источников – 27, приложений – 10.
Знакомство учащихся даже с простейшими рекурсивными алгоритмами
вызывает ряд трудностей в
усвоении. Они обусловлены прежде всего
сложностями структурно-логического характера в действиях, составляющих
конструктивную основу таких алгоритмов. Естественно, подобные сложности и
малый ресурс учебного времени не позволяют в процессе обучения специально
уделять внимание вопросам разработки рекурсивных алгоритмов при решении
задач. Все это приводит к тому, что процент выполнения таких заданий в ЕГЭ
довольно низок (в среднем 36-40%).
Все вышесказанное позволяет сделать вывод, что назрела настоятельная
необходимость модификации традиционного курса информатики в школе путем
насыщения его наиболее перспективными и методически оправданными
универсальными методами решения широкого класса практических задач, и в
первую очередь, рекурсией как одной из перспективных технологических схем
проблемного обучения.
Цель. Разработать программно-методическое обеспечение темы «Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi» в профильном курсе информатики в школе.
Объект
исследования.
Процесс
преподавания
темы
«Организация
рекурсивных алгоритмов в языках программирования Pascal и Delphi».
Предмет
исследования.
Методическая
система
обучению
темы
«Организация рекурсивных алгоритмов в языках программирования Pascal и
Delphi» в профильном курсе информатики в школе.
Задачи:
1. Изучить
и
проанализировать
методическую
литературу
по
теме
3
исследования.
2. Раскрыть особенности профильных курсов по информатике на базовом и
углубленном уровнях обучения.
3. Рассмотреть теоретические основы преподавания темы «Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi ».
4. Проанализировать
программно-методическое
обеспечение
темы
«Организация рекурсивных алгоритмов в языках программирования Pascal и
Delphi» в профильном курсе информатики в школе.
5. Разработать конспекты для профильного курса по информатике на тему
«Организация рекурсивных алгоритмов в языках программирования Pascal и
Delphi».
6. Разработать
электронный
учебник
«Организация
рекурсивных
алгоритмов в языках программирования Pascal и Delphi».
Методы исследования. Изучение методической литературы, анализ, синтез.
Результаты работы. Разработаны конспекты для профильного курса по
информатике на тему «Организация рекурсивных алгоритмов в языках
программирования
Pascal
и
Delphi»,
разработан
электронный
учебник
«Организация рекурсивных алгоритмов в языках программирования Pascal и
Delphi».
Работа имеет теоретическое и практическое значение, т.к. разработанное
программно-методическое обеспечение по теме «Организация рекурсивных
алгоритмов в языках программирования Pascal и Delphi» может применяться для
организации и планирования уроков информатики.
4
СОДЕРЖАНИЕ
ВВЕДЕНИЕ……………………………………………………………………………..6
ГЛАВА 1. ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ ИЗУЧЕНИЯ РЕКУРСИВНЫХ
АЛГОРИТМОВ В ПРОФИЛЬНОМ КУРСЕ ИНФОРМАТИКИ..............................10
1.1.
Цели и задачи профильных курсов на старшей ступени образования...........10
1.2.
Цели и задачи профильных курсов по информатике на базовом и углублен-
ном уровнях образования…………………………………………………………..…14
1.3.
Теоретические основы преподавания темы «Организация рекурсивных ал-
горитмов в языках программирования Pascal и Delphi»………………………...….24
1.3.1. Понятие и сущность рекурсии…………………………………………..…….24
1.3.2. Основные формы рекурсивных алгоритмов……………………………….....29
1.3.3. Стековая организация рекурсии ………………………………………………35
1.3.4. Итерация и рекурсия. Сравнение подходов ……………………….………....39
ГЛАВА 2. МЕТОДИКА ИЗУЧЕНИЯ ТЕМЫ «ОРГАНИЗАЦИЯ РЕКУРСИВНЫХ
АЛГОРИТМОВ В ЯЗЫКАХ ПРОГРАММИРОВАНИЯ PASCAL И DELPHI» В
ПРОФИЛЬНОМ КУРСЕ ИНФОРМАТИКИ ………………………………………..45
2.1.
Цели и задачи изучения темы «Организация рекурсивных алгоритмов язы-
ках программирования Pascal и Delphi»……………………………………………..45
2.2.
Требования к результатам обучения …………………………………………45
2.3.
Место изучения темы в структуре образовательного процесса ……………48
2.4.
Методические рекомендации к проведению занятий ……………………….56
ЗАКЛЮЧЕНИЕ ……………………………………………………………………….87
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ ……………….………………...…..89
ПРИЛОЖЕНИЕ 1. Конспект урока на тему «Рекурсивные методы программирования. Рекурсивные подпрограммы»………………………………………………...92
ПРИЛОЖЕНИЕ 2. Конспект урока на тему «Задача о Ханойской башне»……..105
ПРИЛОЖЕНИЕ 3. Конспект урока на тему «Алгоритм быстрой сортировки»....114
ПРИЛОЖЕНИЕ 4. Конспект урока на тему «Лабораторная работа. Рекурсивные
методы программирования»………………………………….……………………..121
5
ПРИЛОЖЕНИЕ 5. Конспект урока на тему «Контрольная работа «Рекурсивные
методы программирования»………………………………………………………...127
ПРИЛОЖЕНИЕ 6. Конспект урока на тему «Организация рекурсивных алгоритмов в среде ООП Delphi»…………………………………………………………....132
ПРИЛОЖЕНИЕ 7. Конспект урока на тему «Задача на поиск пути»……….…...147
ПРИЛОЖЕНИЕ 8. Конспект урока на тему «Рекурсивные алгоритмы в заданиях к
ЕГЭ»…………………………………………………………………………………..161
ПРИЛОЖЕНИЕ 9. Конспект урока на тему «Кривая Гильберта» (материал для самостоятельного изучения)……………………………………..………………..…..170
ПРИЛОЖЕНИЕ 10. Электронный учебник «Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi…………………………...….….177
……………………………………………………………………….……………………
……………………………………………………….………………………….………
…………………………………………………………………….………………………
…………………………………………………….………………………………………
…………………………………….………………………………………………………
…………………….………………………………………………………………………
…….…………………………………………………………………………….…….
6
ВВЕДЕНИЕ
Одним из приоритетных направлений развития современной школы, требующее особого внимания - это создание условий для реализации личностноориентированной парадигмы образования, для дифференциации и индивидуализации процесса обучения, в том числе на основе углубленного обучения. Это в
полной мере касается и такого учебного предмета, как информатика.
В соответствии с ФГОС СОО[2] в старших классах средней школы предусматривается реализация обучения по пяти профилям: //////////////////
•естественнонаучному, //////////////////////////////////////////////////////////////////////////////////////////////////////////
•гуманитарному, //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
•социально-экономическому, //////////////////////////////////////////////////////////////////////////////////////////////////////////
•технологическому,//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
•универсальному
Учебный план предусматривает изучение учебных предметов по выбору из
обязательных предметных областей, дополнительных учебных предметов, курсов
по выбору и общих для включения во все учебные планы учебных предметов, в
том числе на углубленном уровне. Таким образом, предмет «Информатика», входящий в предметную область «Математика и информатика», может быть включен
в программу обучения на базовом и углубленном уровнях.[27]
Одними
из
базовых
понятий
в
информатике
являются
алгоритм
и алгоритмизация, а линия «Алгоритмизация и программирование» - одной из
фундаментальных составляющих школьного курса информатики.
Следует отметить, что алгоритмическая компетентность, являясь составной
частью интеллектуальной компетентности будущих выпускников школы, подразумевает:
 Знание основных приемов и методов решения практических задач;
 Основное владение всей структурой процесса решения практических за-
дач;
 Умение обосновать логические операции;
7
 Умение осуществлять анализ условия задачи и на основе приведенного
анализа решать типовые задачи;
 Умение проводить систематизацию и анализ существенных и второсте-
пенных свойств изучаемого объекта;
 Способность сравнивать результаты и делать выводы из приведённого
сравнения, для оптимизации разработанного алгоритма решения задачи;
 Умение проводить обобщения, применять свои знания, полученные при
решении одной задачи на класс других задач и в нестандартных ситуациях.
 Умение использовать и создавать вспомогательные алгоритмы для реше-
ния поставленных задач.
Изучение рекурсии является неотъемлемой частью содержательной линии
«Алгоритмизация и программирование».
Требованиями к усвоению данной темы являются:
 Знание основных форм рекурсивных алгоритмов
 Умение анализировать рекурсивные алгоритмы проводить их трассиров-
ку;
 Умение определять актуальность применения рекурсии к предложенной
задаче.
Следует отметить, что знакомство учащихся даже с простейшими рекурсивными алгоритмами вызовет ряд трудностей в усвоении. Они обусловлены прежде
всего сложностями структурно-логического характера в действиях, составляющих
конструктивную основу таких алгоритмов. Естественно, подобные сложности и
малый ресурс учебного времени не позволяют в процессе обучения специально
уделять внимание вопросам разработки рекурсивных алгоритмов при решении задач. Все это приводит к тому, что процент выполнения таких заданий в ЕГЭ довольно низок (в среднем 36-40%).
Все вышесказанное позволяет сделать вывод, что назрела настоятельная
необходимость модификации традиционного курса информатики в школе путем
насыщения его наиболее перспективными и методически оправданными универ-
8
сальными методами решения широкого класса практических задач и, в первую
очередь, рекурсией как одной из перспективных технологических схем проблемного обучения. Это и определяет актуальность выбранной темы исследования.///
Цель: разработать программно-методическое обеспечение темы «Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi» в профильном курсе информатики в школе.///////////////////////////////////////////////////////////////
Объект исследования: процесс преподавания темы «Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi».
Предмет исследования: методическая система обучению темы «Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi» в профильном курсе информатики в школе. ///////////////////////////////////////////////////////////////////
Задачи: ////////////////////////////////////////////////////////////////////////////////////////////////////////
1. Изучить и проанализировать методическую литературу по теме исследования.
2. Раскрыть особенности профильных курсов по информатике на базовом и
углубленном уровнях обучения.
3. Рассмотреть теоретические основы преподавания темы «Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi »./
4. Проанализировать программно-методическое обеспечение темы «Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi» в
профильном курсе информатики в школе. //////////////////////////////////////////////////////////////
5. Разработать конспекты для профильного курса по информатике на тему
«Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi». ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
6. Разработать электронный учебник «Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi». //////////////////////////////////////////////////
Методы исследования: изучение методической литературы, анализ,
синтез.
9
Структура ВКР:
Выпускная квалификационная работа состоит из введения содержания двух
глав, заключения. Также в состав входят 10 приложений.
Во введении раскрыта актуальность выбора темы.
В первой главе «Теоретическое обоснование изучения рекурсивных
алгоритмов в профильном курсе информатики» рассмотрены: цели и задачи
профильных курсов на старшей ступени образования, цели и задачи профильных
курсов по информатике на базовом
теоретические
основы
преподавания
и углубленном уровнях образования,
темы
«Организация
рекурсивных
алгоритмов в языках программирования Pascal и Delphi».
Во второй главе «Методика изучения темы «Организация рекурсивных
алгоритмов в языках программирования Pascal и Delphi»» в профильном курсе
информатики» указаны цели и задачи изучения темы «Организация рекурсивных
алгоритмов в языках программирования Pascal и Delphi»», требования к
результатам обучения, место изучения темы в структуре образовательного
процесса, методические рекомендации к проведению занятий.
В заключении описываются результаты выполнения ВКР.
10
приложений
отражают
обеспечение по теме исследования.
разработанное
программно-методическое
10
ГЛАВА 1. ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ ИЗУЧЕНИЯ РЕКУРСИВНЫХ АЛГОРИТМОВ В ПРОФИЛЬНОМ КУРСЕ ИНФОРМАТИКИ
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
1.1.
Цели и задачи профильных курсов на старшей ступени общего
образования//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Задачи системы образования в современных условиях определены Законом
РФ «Об образовании» и Государственной программой развития образования РФ
на 2011-2020 годы. Главная задача - наполнение образования новым качеством и
содержанием.[24] //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
В таких условиях меняются цели и ценности образования. Его главной целью становится обеспечение качественного образования для каждого учащегося в
соответствии с его интересами и склонностями. Развитие и воспитание обучающихся, формирование их активной позиции в образовательном процессе, не исключительно обеспечение учащихся суммой знаний, но и формирование современного мышления школьников, их познавательных и созидательных способностей — это главные ценности обновленного образования.[24] ////////////////////////////////////////////////
Таким образом, одно из приоритетных направлений развития современной
школы, требующее особого внимания, - это создание условий для реализации
личностно-ориентированной парадигмы образования, для дифференциации и индивидуализации процесса обучения, в том числе на основе углубленного обучения. Это в полной мере касается и такого учебного предмета, как информатика.
Динамичное развитие информационного общества указывает на необходимость в создании новых программ, которые позволяют обучающимся осваивать
новые информационные технологии и глубже осваивать возможности профессиональной деятельности. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Эта проблема решается с введением в среднюю общеобразовательную школу профильных курсов как новой формы учебной работы, которая нацелена на
углубление знаний и развитие разносторонних интересов и способностей учащихся. [23] /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Выбор профильной специализации должен определяться: //////////////////////////////
11
• социальным заказом общества школе на предпрофессиональную подготовку учащихся; //////////////////////////////////////////////////////////////////////////////////////////////////////////ioiuoiuoiuouiououiououi
• методологической ролью информатики и информационных технологий в
формировании учащихся необходимых общекультурных и общеучебных навыков;
• учетом тенденций развития базовой науки информатики и возрастанием ее
влияния на развитие современных науки, техники, технологий.////////////////////////////
Определение того или иного направления для углубленного изучения информатики может определяться различными причинами: профилем школы (класса), видом аппаратного и программного обеспечения, интересами учителя и учеников, наличием методической поддержки и др. Но в основу выбора должны быть
приняты, прежде всего, цели и задачи школьного курса информатики и информационных технологий в целом, а также ее углубленного (профильного) преподавания.[23] ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
В общем профильные курсы в 10—11-х классах согласно нормативным и
информационным документам, «должны выполнять следующие основные функции: /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
•
дополнять содержание профильного общеобразовательного учебного
предмета (в качестве его «надстройки»); //////////////////////////////////////////////////////////////////////////////////////////////////////////
•
удовлетворять познавательные интересы учащихся вне рамок выбран-
ного профиля; ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
•
способствовать формированию умений и способов практической дея-
тельности; /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
•
предоставлять возможность приобретать знания и умения, востребо-
ванные на рынке труда».[24] ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
В соответствии с функциями профильных курсов в рамках профильного
обучения выделяются следующие группы://////////////////////////////////////////////////////////////////////////////////////////////////////////
1. Курсы, выступающие в роли «надстройки». Такие дополненные профильные курсы, углубляют и расширяют знания и умения учащихся по предметам
учебного плана. Такие курсы направлены: //////////////////////////////////////////////////////////////////////////////////////////////////////////
12
•
углублять в целом все разделы содержания учебного предмета по вы-
бранному профилю; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
•
углублять отдельные разделы и темы учебной программы в рамках
обучения; //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
•
раскрывать содержание тем, не входящих в учебную программу про-
фильного обучения; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
•
носить прикладной характер и способствовать переносу теоретиче-
ских знаний в деятельностную сферу; //////////////////////////////////////////////////////////////////////////////////////////////////////////
•
изучать методы познания, расширять кругозор и формировать миро-
воззрение учащихся; //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
•
содержать сведения по истории того или иного предмета и персона-
лии.[24] ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
2. Курсы межпредметного характера, ориентированные на интеграцию знаний учащихся о человеке, обществе, природе. Эти курсы призваны, во-первых,
компенсировать недостаточность знаний учащихся в определенных областях, взаимосвязанных с выбранным профилем, что позволяет заинтересованным учащимся получить дополнительную подготовку и удовлетворить свои познавательные
потребности. Во-вторых, способствовать синтезу знаний по ряду предметов и
способах их применения в различных профессиональных областях. ////////////////////////////////////
3. Курсы, содержание которых выходит за рамки программы, но которые
способствуют выпускникам в самоопределении на рынке труда, в удовлетворении
познавательных интересов учащихся и помогают в решении жизненных вопросов.
В процессе реализации профильного обучение, были выявлены типичные
затруднения педагогов такие как: //////////////////////////////////////////////////////////////////////////////////////////////////////////
- незнание нормативно-правовой базы, непонимание целей и задач профильного обучения; //////////////////////////////////////////////////////////////////////////////////////////////////////////…………………………..
- непонимание отличий в целях, задачах, средствах реализации предпрофильной подготовки и профильного обучения; /////////////////////////////////////////////////////////////////////////////////////
13
-
неполное
знание
содержания
профильного
образования,
учебно-
дидактического и методического его обеспечения; /////////////////////////////////////////////////////////////////////////////////////
- невладение проектировочными умениями, учителя затрудняются спроектировать прикладной профильный курс, поставить адекватные цели к указанным
курсам, разработать его содержание; //////////////////////////////////////////////////////////////////////////////////////////////////////////
- недостаточность психологических знаний, что не позволяет грамотно организовать процессы самоопределения, самореализации и самоактуализации ученика, профильную и профессиональную ориентацию; ////////////////////////////////////////////////////////////////////////////
- невладение передовыми педагогическими технологиями на уровне использования в образовательном процессе; //////////////////////////////////////////////////////////////////////////////////////////////////////////
- отсутствие достаточного арсенала методов активного обучения, включающий обозначенные на уровне базисного учебного плана метод проектов, исследовательскую деятельность, учебные практики.[24] //////////////////////////////////////////////////////////////////////////
Трудности внедрения профильного обучения не обошли и самих учащихся,
а особенно с позиции психологического сопровождения учебного процесса.
Приступая к обучению на профильном уровне, учащиеся погружаются в новые для них условия: изменившиеся объемы работы и характер мыслительных
действий, новые формы работы, новая система занятий. Совокупность данных
факторов вызывает у многих подростков эмоциональный дискомфорт, и как следствие, состояние внутренней настороженности, напряженности, которые затрудняют принятие верных решений. Длительное психологическое напряжение, может привести к невнимательности, недисциплинированности, отставанию в учебе,
безответственности, быстром утомлении и отсутствию желания идти в школу. Все
перечисленные последствия дезадаптации усложняют процесс обучения, и продуктивная работа на уроке становится проблематичной.[24]
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
14
1.2.
Цели и задачи профильных курсов по информатике на базовом и
углубленном уровнях образования//////////////////////////////////////////////////////////////////////////////////////////////////////////
В соответствии с ФГОС среднего общего образования [1], учебный план
профиля обучения и (или) индивидуальный учебный план должны содержать 9
(10) учебных предметов и предусматривать изучение не менее одного учебного
предмета из каждой предметной области, определенной стандартом. Количество
учебных занятий на одного обучающегося в неделю не более 37 часов./////////////////
К сожалению, учебный предмет «Информатика», входящий в состав предметной области «Математика и информатика» не включен в набор обязательных
образовательных курсов. Это разрешено объяснить двумя причинами. Во – первых, в новом учебном плане школы существенно увеличивается объем изучения
информатики в основной школе. Это позволит учащимся уже на этой ступени
школы в значительной мере получить необходимый объем содержания образования по этому предмету, обеспечивающий им формирование функциональной грамотности, социализацию и решение других задач общего образования. Во – вторых, специфика информатики как науки сферы деятельности человека заключается в том, что она обеспечивает своими методами, средствами, технологиями другие области знания, познавательной и практической деятельности человека. Поэтому нет смысла изучать на старшей ступени школы базовый (инвариантный для
всех профилей) курс информатики. Более целесообразно профильное изучение,
ориентированное на запросы конкретного профиля. Вместе с тем ФГОС не отвергает возможность изучения информатики на базовом, минимальном уровне, и ее
вхождение в содержание того или иного профиля.[27]///////////////////////////////////////////
Во ФГОС СОО указано, что учебный план предусматривает изучение учебных предметов по выбору из обязательных предметных областей, дополнительных учебных предметов, курсов по выбору и общих для включения во все учебные планы учебных предметов, в том числе на углубленном уровне. Таким образом, предмет «Информатика», входящий в предметную область «Математика и
15
информатика», может быть включен в программу обучения на базовом и углубленном уровнях.[27] /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Изучение предметов (курсов) по выбору обучающихся на старшей ступени
образования нацелено на удовлетворение индивидуальных запросов, таких как:
•развитие личности обучающихся, их познавательных интересов, интеллектуальной и ценностно-смысловой сферы; ///////////////////////////////////////////////////////////////////////////////////
•развитие навыков самообразования; /////////////////////////////////////////////////////////////////////////////////////////////
•углубление, расширение и систематизация знаний в выбранной области
научного знания или вида учебной деятельности/////////////////////////////////////////////////////////////////////////
Кроме того, предусматривается изучение курсов по выбору (элективных
курсов) в рамках внеурочной деятельности, такая деятельность становится обязательным компонентом основной образовательной программы старшей ступени
образования.////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
В соответствии с ФГОС СОО в старших классах средней школы предусматривается реализация обучения по пяти профилям: ////////////////////////////////////////////////////////////////////////////////
•естественнонаучному, //////////////////////////////////////////////////////////////////////////////////////////////////////////
•гуманитарному, //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
•социально-экономическому, //////////////////////////////////////////////////////////////////////////////////////////////////////////
•технологическому,//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
•универсальному. /////////////////////////////////////////////////////////////////////////////////////////////////////////////
Напомним, профильное обучение – средство дифференциации обучения,
когда за счет целенаправленных изменений в структуре, содержании и организации образовательного процесса создаются условия для эффективной реализации
индивидуализации обучения, более полно учитываются интересы, склонности и
способности учащихся, открываются новые возможности для образования старшеклассников в соответствии с их профессиональными устремлениями и намерениями в отношении дальнейшего образования и выбора жизненного пути.[27]
Заметим, что дифференциация обучения может осуществляться в двух основных формах: уровневой и профильной. Уровневую дифференциацию разре-
16
шено определить как организацию обучения, при которой школьники имеют возможность и право усваивать содержание обучения на различных уровнях. Примером уровневой дифференциации может служить углубленное изучение отдельных
предметов. Профильная дифференциация заключается в направленной специализации содержания образования с учетом интересов, склонностей, способностей
школьников, их последующих профессиональных намерений. В настоящее время
в силу объективных причин стандартом предусмотрена уровневая дифференциация. При этом профильность обучения достигается на счет возможности изучения
различных курсов на базовом или углубленном уровнях. /////////////////////////////////////////////////////////////////
Содержание каждого профиля обучения формируется путем сочетания различных учебных предметов, содержание которых в свою очередь определяется
образовательными стандартами и неизменно для любого профиля обучения. При
этом учебный план профиля обучения (кроме универсального) должен содержать
не менее трех (четырех) учебных предметов на углубленном уровне из соответствующей профилю обучения предметной области и (или) смежной с ней предметной области [27]. //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Отметим некоторые особенности изучения информатики в старших классах
в условиях профилизации обучения. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Информатика в естественнонаучном профиле представлена на базовом
уровне. На ее изучение отводится 70 часов на два года обучения (1 час в неделю).
Для естественнонаучного профиля характерен акцент на углубленное изучение
предметов из предметных областей «Математика и информатика» и «Естественные науки». Межпредметные связи курса информатики с курсами химии, биологии, физики могут быть направлены на изучение структурных и классификационных моделей, на изучение информационных процессов в живой и неживой природе, на построение компьютерных моделей химических, биологических, физических объектов и процессов. /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Рекомендуется дополнить профиль следующими элективными курсами :
«Биоинформатика», «Исследование биологических моделей с использованием си-
17
стем объектно-ориентированного программирования и электронных таблиц»,
«Управляемые и самоуправляемые системы», «Анимация как моделирование динамических систем», «Моделирование информационных процессов в биологических системах», «Средства обработки табличной информации», «Средства обработки графической информации», «Создание и использование баз данных», «Основы моделирования и интерпретации химических моделей», «Проектирование
баз данных в медицине», «Методы математической обработки экспериментальных данных (разработка программ для различных областей научных исследований)».[27] ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Информатика в социально-экономическом профиле представлена на базовом уровне и на ее изучение отводится 70 часов на два года обучения (1 час в неделю). Особенностями курса информатики в данном профиле является формирование навыков работы с программами, позволяющими решать задачи связанные с
обработкой информации в социальной сфере, в сфере экономики, управления и
др. Возможность увеличения количества часов информатики может быть достигнута введением в учебный план курсов по выбору, таких как «Технологии обработки экономической информации в табличном процессоре Excel», «Методы и
средства компьютерной обработки статистических данных», «Информационные
технологии в бизнесе» «Социальные последствия информатизации», «Исследование
информационных
моделей
с
использованием
систем
объектно-
ориентированного программирования и электронных таблиц» «Информационный
бизнес», «Коммуникационные технологии в коммерции», «Использование информационных технологий в управлении».[27] ////////////////////////////////////////////////////////////////////////////////////////////
Информатика в технологическом профиле представлена на углубленном
уровне. Для данного профиля характерным является углубленное изучение предметов из предметных областей «Математика и информатика» и «Естественные
науки». На изучение информатики предлагается 280 часов за два года обучения
[27]. В проекте учебного плана предлагается выделить 1 час в неделю на элективный курс «Компьютерная графика». //////////////////////////////////////////////////////////////////////////////////////////////////////////
18
Основными задачами курса информатики в данном профиле является систематизация, расширение и углубление знаний, полученных в курсе информатики основной школы, а также формирование умений и навыков, необходимых для
дальнейшей профессиональной деятельности в сфере производства, инженерии и
информационно-коммуникационных услуг. Можно также предложить учащимся
элективные курсы ««Основы микроэлектроники», «Архитектура компьютера»,
«Технические средства информатики», «Техническое обслуживание компьютера», «Искусственный интеллект», «Модели управления производством» «Использование информационных технологий в управлении», «Основы кибернетики»,
«Инженерная графика», «Робототехника». //////////////////////////////////////////////////////////////////////////////////////////////////////////
Информатика в гуманитарном профиле не входит в перечень обязательных
предметов в примерном учебном плане [27]. Для данного профиля характерным
является углубленное изучение предметов из предметных областей «Филология»
и «Общественные науки», что предполагает ориентацию данного профиля на такие сферы деятельности, как педагогика, психология, общественные отношения,
геополитика, лингвистика и др. В данном случае информатика может выступать
как предмет формирующий общекультурные качества человека, помогающие ему
успешно развиваться в информационном обществе. Таким образом, изучение информатики в данном профиле в большей мере носит прикладной характер. Межпредметные связи информатики с профильными предметами разрешено реализовать через исторические, творческие, профориентационные проекты. Поэтому на
наш взгляд было бы целесообразно включить информатику в учебный план данного профиля. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
В качестве внеурочной деятельности разрешено рекомендовать следующие
элективные курсы «Информационная культура и сетевой этикет», «Корпоративные автоматизированные библиотечно-информационные системы», «Информационно-поисковые системы», «Информационная безопасность»,
«Поисковые си-
стемы сети Интернет», «Гипертекстовые технологии», «Основы машинного перевода иноязычных текстов», «Средства обработки текстовой информации», «Изда-
19
тельские системы», «Технология работы с библиотечными и сетевыми ресурсами», «Приемы и методы компьютерной верстки», «Электронные энциклопедии:
создание и использование», «Основы информационной безопасности», «Информационно-правовые системы», «Принципы построения мировоззренческих моделей», «Когнитивная информатика», «Когнитивная психология и программирование», «Использование компьютера в психологическом тестировании», «Моделирование в истории и интерпретация моделей», «Технология работы с библиотечными и сетевыми ресурсами», «Геоинформационные системы», «Инструментальные средства геоинформационных систем», «Инструментальные средства создания карт». //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Универсальный профиль ориентирован на учащихся, которые еще не определились с будущей профессией. Этот профиль позволяет учащимся выбрать
один из трех вариантов изучения информатики: /////////////////////////////////////////////////////////////////////////////////
•информатика изучается на базовом уровне 70 часов в год;////////////////////
•информатика не входит в перечень обязательных предметов, но предусмотрен элективный курс;/////////////////////////////////// /////////////////////////////////////////////////////////////////////
•информатика
изучается
во
внеурочной
деятельности
факультатив-
но.[27]//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
В качестве внеурочной деятельности в данном профиле разрешено рекомендовать следующие элективные курсы по информатике «Технология создания
сайтов», «Методы математической обработки экспериментальных данных (разработка программ для различных областей научных исследований)», «Обеспечение
информационной безопасности на персональном компьютере при работе в сети»,
«Искусственный интеллект», «Компьютерные сети и телекоммуникации», «Базы
данных»; «Проектирование информационных систем», «Подготовка изображений
(иллюстраций) с помощью средств цифрового моделирования художественных
материалов (CorelPainter)»,«Цифровой видеомонтаж с помощью AdobePremiere»,
«Использование трёхмерной графики для подготовки анимационных фильмов»,
«Основы презентационной графики». //////////////////////////////////////////////////////////////////////////////////////////////////////////
20
Таким образом, выбирая тот или иной профиль обучения, учащиеся получают возможность не исключительно выстроить индивидуальную траекторию
обучения, но и удовлетворить свои познавательные интересы как в будущей профессиональной области так и сфере информатики и информационных технологий.[27] ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Анализ УМК 10-11 классы Поляков К.Ю. и др. для 10-11 класс/////////////
В авторский УМК завершенной предметной линии для 10-11 классов входят: ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
• учебник «Информатика. 10 класс. Углубленный уровень»;/////////////////////////
• учебник «Информатика. 11 класс. Углубленный уровень»;//////////////////////////
• компьютерный практикум в электронном виде с комплектом электронных
учебных
средств,
размещенный
на
сайте
авторского
коллектива:
http://kpolyakov.narod.ru/school/ probook.htm: //////////////////////////////////////////////////////////////////////////////////////////////
• материалы для подготовки к итоговой аттестации по информатике в форме
ЕГЭ, размещенные на сайте http:// kpolyakov.narod.ru/school/ege.htm: ///////////////////////////
• методическое пособие для учителя; //////////////////////////////////////////////////////////////////////////////////////////////////////////
• комплект Федеральных цифровых информационно-образовательных ресурсов
(далее
ФЦИОР),
помещенный
в
коллекцию
ФЦИОР
(http://www.fcior.edu.ru): ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
• сетевая методическая служба авторского коллектива для педагогов на сайте издательства http://metodist.lbz.ru/ authors/informatika/7/. //////////////////////////////////////////////////////////
Учебники «Информатика. 10 класс» и «Информатика. 11 класс» разработаны в соответствии с требованиями ФГОС и с учетом вхождения курса «Информатика» в 10 и 11 классах в состав учебного плана в объеме 276 часов (полный
углубленный курс) или 138 часов (сокращенный курс).[25]///////////////////////////////////
Целевая аудитория данного курса — школьники старших классов, которые
планируют связать свою будущую профессиональную деятельность с информационными технологиями. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
21
Информатика рассматривается авторами как наука об автоматической обработке данных с помощью компьютерных вычислительных систем. Такой подход
сближает курс информатики с дисциплиной, называемой за рубежом computer
science. //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Углубленный курс является одним из вариантов развития курса информатики, который изучается в основной школе (7-9 классы). Поэтому, согласно принципу спирали, материал некоторых разделов программы является развитием и
продолжением соответствующих разделов курса основной школы. Отличие
углубленного курса от базового состоит в том, что более глубоко рассматриваются принципы хранения, передачи и автоматической обработки данных; ставится
задача выйти на уровень понимания происходящих процессов, а не исключительно поверхностного знакомства с ними.[25] //////////////////////////////////////////////////////////////////////////////////////////////////////////
Учебники, составляющие ядро УМК, содержат все необходимые фундаментальные сведения, относящиеся к школьному курсу информатики, и в этом смысле являются цельными и достаточными для углубленной подготовки по информатике в старшей школе, независимо от уровня подготовки учащихся, закончивших
основную школу. Учитель может перераспределять часы, отведенные на изучение
отдельных разделов учебного курса, в зависимости от фактического уровня подготовки учащихся.[25] /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Одна из важных задач — обеспечить возможность подготовки учащихся к
сдаче ЕГЭ по информатике. Авторы сделали все возможное, чтобы в ходе обучения рассмотреть максимальное количество типов задач, включаемых в контрольно-измерительные материалы ЕГЭ. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Углубленный курс рекомендуется для изучения в классах технологического
и естественно-научного профилей. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Принципиальное положение, из которого исходили авторы при работе над
УМК «Информатика» для 10-11 классов углубленного уровня, состоит в следующем: углубленный курс информатики ориентирован на углубленную подготовку
22
выпускников школы, мотивированных на дальнейшее обучение в системе ВПО на
ИТ-ориентированных специальностях (и направлениях).///////////////////////////////////////
Помимо сказанного выше, линия профессиональной ориентации в учебниках для 10-11 классов проявляется в том, что в различных главах представлены
различные области применения и использования ИТ-технологий. Тема профессиональной ориентации является сквозной по всему учебнику. ///////////////////////////////////////////////////////
Изучение рекурсии в данном курсе осуществляется в 10 классе./////////////////
На изучение темы отводится 3(2+1) часа. ////////////////////////////////////////////////////////////////////////////////////
В процессе изучения темы учащиеся знакомятся с понятием рекурсии, стека. Даются разобранные примеры рекурсивных алгоритмов. /////////////////////////////////////////////////
Недостатком является то, что в учебнике не разобраны основные формы рекурсии. Так же не раскрыто понятие прямой и косвенной рекурсии.////////////////////
Анализ УМК для старшей школы 10- 11 классы авторы: Семакин И. Г.,
Шеина Т. Ю., Шестакова Л. В. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Основной принцип, которым руководствовались авторы при разработке
учебного курса для преподавания информатики на углубленном уровне, заключается в соблюдении соответствия требованиям ФГОС. Удовлетворение всем требованиям ФГОС обеспечивает полный набор компонентов УМК: ///////////////////////////////////////////
• учебник «Информатика» углубленного уровня для 10 класса (авторы: Семакин И. Г., Шеина Т. Ю., Шестакова Л. В.); //////////////////////////////////////////////////////////////////////////////////////////
• учебник «Информатика» углубленного уровня для 11 класса (авторы: Семакин И. Г., Хеннер Е. К., Шестакова Л. В.); ///////////////////////////////////////////////////////////////////////////////////////////
• практикум для 10-11 класса углубленного уровня (авторы: Семакин И. Г.,
Шеина Т. Ю., Хеннер Е. К., Шестакова Л. В.); /////////////////////////////////////////////////////////////////////////////////////////
• методическое пособие; ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
• электронное приложение к УМК. //////////////////////////////////////////////////////////////////////////////////////////////////////////
В разделе II.9 ФГОС сказано: «Предметные результаты освоения основной
образовательной программы среднего (полного) общего образования для учебных
предметов на углубленном уровне ориентированы преимущественно на подготов-
23
ку к последующему профессиональному образованию, развитие индивидуальных
способностей обучающихся путем более глубокого, чем это предусматривается
базовым курсом, освоением основ наук, систематических знаний и способов действий, присущих данному учебному предмету».[26] ////////////////////////////////////////////////////////////////////////////
В соответствии с этим, авторы настоящего курса при работе над УМК исходили из следующей установки: углубленный курс информатики является средством предвузовской подготовки выпускников школы, мотивированных на дальнейшее обучение в системе ВПО на IT-ориентированных специальностях (и
направлениях). В связи с этим, авторами курса был проанализирован реестр вузовских специальностей и выделен в нем блок, относящийся к подготовке специалистов и бакалавров в области информатики и ИКТ. Для данных специальностей
были исследованы Государственные образовательные стандарты и в них выделены инвариантные составляющие. Результаты этого исследования были использованы для реализации следующего принципа при разработке УМК: оставаясь в
рамках требований ФГОС, содержание углубленного курса информатики в то же
время реализует пропедевтику инвариантной составляющей содержания подготовки IT- специалистов в системе ВПО.[26] ///////////////////////////////////////////////////////////////////////////////////////////////
Помимо сказанного выше, линия профессиональной ориентации в учебниках для 10-11 классов проявляется в том, что в различных главах рассказывается о
профессиях в области информатики и ИКТ. Тема профессиональной ориентации
начинается с введения к учебнику 10 класса. В последующих главах имеются
подразделы, озаглавленные: «О профессиях». Дается краткая характеристика всех
основных специальностей, перечисленных в документе под названием «Профессиональные стандарты в области информационных технологий», разработанном
Ассоциацией предприятий компьютерных и информационных технологий (АП
КИТ). /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Изучение рекурсии в данном курсе осуществляется в 11 классе.////////////////////
На изучение темы отводится 4(3+1) часа.////////////////////////////////////////////////////////////////////////////////////////////
24
В процессе изучения темы учащиеся знакомятся с понятием рекурсии, частично рекурсивной функции. Даются разобранные примеры рекурсивных алгоритмов. Происходит сравнение рекурсии и итерации с точки зрения эффективности.[26] ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Недостатком является то, что в учебнике не разобраны основные формы рекурсии. Понятие прямой и косвенной рекурсии также не нашли отражение в данном учебном пособии. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Таким образом, в рассматриваемых учебно-методических комплексах
наблюдаются схожие недостатки: недостаточное раскрытие понятия «рекурсия»,
относительно небольшие временные рамки, отводимые на изучение данной темы.///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
1.3. Теоретические основы преподавания темы «Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi»
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
1.3.1. Понятие рекурсии///////////////////////////////////////////////////////////////////////////////////////////////////////////////
Рекурсия (от латинского recursio – возвращение) – это такой способ организации вычислений, при котором процедура или функция в ходе выполнения обращается сама к себе. Иными словами, рекурсия является методом определения
функций (процедур), при котором определяемая функция применена в теле своего
же собственного определения. Понятие рекурсии используется не исключительно
в программировании, но и в математике. Интуитивно, рекурсия – это определение
через себя; это сведение общего случая к аналогичным частным случаям.///////////
Понятие рекурсии достаточно просто для понимания и не связано со знанием какого-либо определенного формализма или специальной нотации. В общем
случае на рекурсию следует смотреть как на введение в определение объекта
ссылку на сам объект или, более определенно, как на прием сведения решения некоторой задачи к решению “более простой” задачи такого же класса. В программировании это выражается в построении программ (процедур и функций), которые при выполнении обращаются сами к себе непосредственно или через цепочку
25
других программ. Кажущаяся при этих самовызовах или последовательных циклических вызовах видимость порочного круга (circulus vitiosus – лат.) не более
чем иллюзия. Во многих конкретных случаях простыми рассуждениями путем отслеживания значений одной или нескольких управляющих величин удается провести доказательство завершимости вычислений за конечное число шагов. ////////
Сам процесс программной реализации рекурсивных алгоритмов обладает
специфическими особенностями, а именно – необходимостью организации специальной структуры данных и обслуживания рекурсивных вызовов. При этом, организация структуры данных лежит на плечах программиста, в то время как механизм обслуживания рекурсивных вызовов обеспечивается языком программирования, точнее, компилятором этого языка, и поддерживается машинными командами компьютера.[5] ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Поскольку рекурсивный алгоритм задает во времени последовательность
обращений к одному и тому же фрагменту программного кода, то применяемая
структура данных должна обеспечить сохранность тех ячеек и массивов, которые
будут задействованы алгоритмом после возврата из рекурсивного вызова. В рамках возможностей современных языков процедурного (императивного) программирования могут быть использованы разнообразные варианты, из которых остановимся на трех основных.[5] ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
1. Глобальная структура данных. //////////////////////////////////////////////////////////////////////////////////////////////////////////
В этом случае пользователь создает глобальную структуру, содержащую
помимо описания ячеек и массивов для одного вызова, копии этих описаний для
всей цепочки рекурсивных вызовов, Такая структура может представлять собой,
например, многомерный массив данных, один из индексов которого соответствует
уровню вложенности вызова, Эта структура формируется в вызывающей программе, и рекурсивной функции передается ее адрес, а слой структуры, используемый на данном рекурсивном вызове, определяется его глубиной.
2. Локальная структура данных.
26
При этом способе организации данных в теле рекурсивной функции или
процедуры описывается необходимая структура данных, и создание копии этой
структуры на рекурсивном вызове обеспечивается средствами языка программирования и компилятора. Отметим, что такой подход приводит, особенно при
наличии массивов, к большим затратам памяти в области программного стека,
размер которого, вообще говоря, ограничен. Этот способ приводит к тому, что
общая структура данных, соответствующая текущей глубине рекурсии, последовательности рекурсивных вызовов, будет создаваться механизмом обслуживания
рекурсивного вызова непосредственно во время выполнения программного кода.[5] ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
3. Динамическая структура данных. /////////////////////////////////////////////////////////////////////////////////////////////
Третий подход к созданию необходимой структуры для программной реализации рекурсивного алгоритма состоит в том, что пользователь средствами языка
программирования обращается к операционной системе для выделения необходимого в данный момент ресурса памяти. Этот подход, обладая определенной
гибкостью, требует от пользователя аккуратного обращения с динамически выделяемой памятью, своевременного ее освобождения и организации правильной передачи аргументов при рекурсивных вызовах и правильного возвращения полученных результатов при рекурсивных возвратах. Отметим еще одну особенность
этого подхода — в зависимости от текущего состояния фрагментации области динамической памяти, обслуживаемой средствами операционной системы, временные затраты на динамическое выделение памяти могут существенно влиять на
общее время выполнения программной реализации. Очевидно, что в этом случае
также затруднено теоретическое прогнозирование временных характеристик программ. /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Применительно к рекурсивным алгоритмам «универсальными» и достаточно распространенными методами являются метод рекуррентных соотношений,
метод декомпозиции и метод динамического программирования[5]. Однако в
каждом конкретном случае их применение не является автоматическим. Для каж-
27
дого метода существуют некоторые границы его применимости, и чем более
«универсально» сформулирован сам метод, тем интеллектуально сложнее разработка реального алгоритма на его основе. Рассмотрим некоторые из методов.
1. Метод рекуррентных соотношений. ///////////////////////////////////////////////////////////////////////////////////////
Идея метода рекуррентных соотношений чрезвычайно проста — мы, используя некоторые рассуждения, получаем рекуррентное соотношение, обеспечивающее решение нашей задачи, и на основе этого рекуррентного соотношения
разрабатываем рекурсивный алгоритм. Отметим, что фраза «используя некоторые
рассуждения» совершенно не определяет конкретный метод получения рекуррентного соотношения для определенной задачи. Мы можем лишь уточнить, что
эти рассуждения должны отражать наше рекурсивное понимание структуры задачи, т.е. следовать схеме понижения аргумента или размерности. Решение для некоторой размерности задачи или для некоторого аргумента функции должно быть
сформулировано на основе ее сведения к задачам меньшей размерности или
функциям с меньшим значением аргумента. Условие останова рекурсии позволяет
решить задачу при некоторых малых размерностях или вычислить функцию при
начальных значениях аргумента. [13] //////////////////////////////////////////////////////////////////////////////////////////////////////////
2. Метод декомпозиции. //////////////////////////////////////////////////////////////////////////////////////////////////////////////
Чтобы перенести сотню кирпичей с одного места на другое, мы, скорее всего, будем переносить за один раз несколько кирпичей, а не всю сотню сразу. Таким образом, вместо того, чтобы решать задачу сразу, мы несколько раз решаем
более простую задачу с понижением размерности — собственно говоря, эта идея
и лежит в основе метода декомпозиции. Другое название этого метода — метод
«разделяй и властвуй». Общая схема метода может быть описана как последовательность следующих шагов.[5] //////////////////////////////////////////////////////////////////////////////////////////////////////////
Шаг разделения задачи. На этом шаге выбирается способ разделения задачи
на некоторое количество подзадач меньшей размерности. ////////////////////////////////////////////////////////////////
Шаг решения полученных подзадач. Это рекурсивный шаг — мы рассматриваем каждую подзадачу как задачу определенной размерности., и разделяем ее
28
на собственные подзадачи, выполняя снова шаг 1 (рекурсия) до тех пор, пока не
получим такую размерность, при которой решение может быть найдено непосредственно. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Шаг останова рекурсии. На этом шаге выполняется непосредственное решение полученных подзадач для малых размерностей. //////////////////////////////////////////////////////////////////////////
Шаг объединения решений. На этом шаге полученные решения подзадач
меньшей размерности при возврате в точку рекурсивного вызова объединяются в
решение задачи текущей размерности.[5] //////////////////////////////////////////////////////////////////////////////////////////////////////////
Эти
основные
шаги
метода
декомпозиции
требу-
ют некоторых комментариев. Во-первых, идея метода ничего не говорит о том,
как эти шаги должны быть реализованы в конкретной задаче. Адаптация метода к
конкретной задаче требует, как правило, серьезных размышлений. Во-вторых,
условием применения метода является свойство аддитивности решений, полученных для подзадач меньшей размерности. Строго говоря, нам необходимо доказать, что, объединяя решения, мы получим правильный ответ, в особенности это
касается задач оптимизации в постановке поиска глобального оптимума. Классическим примером является задача коммивояжера — простое объединение двух
оптимальных путей для графов половинной размерности вообще не является решением исходной задачи. В-третьих, для одной и той же задачи могут быть предложены различные идеи ее разделения, и здесь необходимо оценить, к каким
сложностям приводит каждая из этих идей на этапе объединения решений, который, как правило, является наиболее сложным.[5] /////////////////////////////////////////////////////////////////////////////////////
Основное преимущество метода декомпозиции состоит в том, что он позволяет получить алгоритмы с хорошими асимптотическими оценками трудоемкости. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
3. Метод динамического программирования. ////////////////////////////////////////////////////////////////////
Метод динамического программирования был предложен и обоснован Р.
Беллманом в начале 1960-х годов [5]. Первоначально метод создавался в целях
существенного сокращения перебора для решения целого ряда задач экономиче-
29
ского характера, формулируемых в терминах задач целочисленного программирования. Однако Р. Беллман и Р. Дрейфус в [5] показали, что он применим к достаточно широкому кругу задач, в том числе к задачам вариационного исчисления, поиску нулей функций и т. д. В общем виде метод ориентирован на поиск
оптимума целевой функции или функционала в некоторой ограниченной области
многомерного пространства. Предложенный Р. Беллманом метод не является универсальным, и условия его применения требуют, чтобы целевой функционал
представлял собой аддитивную функцию. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Нисходящее
динамическое программирование (top – down dynamic
pгogгamming). Оно позволяет выполнять рекурсивные функции при том же количестве итераций, что и восходящее динамическое программирование. Технология
требует введения в рекурсивную программу неких средств, обеспечивающих сохранение каждого вычисленного значения и проверку сохраненных значений во
избежание их повторного вычисления.[13] //////////////////////////////////////////////////////////////////////////////////////////////////////////
Таким образом, современные информационные технологии содержат достаточно средств, чтобы сделать теоретически эффективные рекурсивные алгоритмы, также эффективными и широко используемыми на практике. ///////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
1.3.2. Основные формы рекурсивных алгоритмов////////////////////////////////////////////////////////
Как было сказано выше, подпрограммы могут обращаться сами к себе. И
такое обращение называется рекурсией. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Для того чтобы обращение не было бесконечным, в тексте подпрограммы
должно быть условие, по достижению которого дальнейшее обращение к подпрограмме не происходит. //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
В ряде случаев рекурсивную подпрограмму разрешено построить непосредственно из формального математического описания задачи.
30
Факториал
Function Fact(n:byte):longint;
begin
n! = n * (n-1)!, при n>0
if n=0
1,
n=0//////////////////////////////////////////////////////////////////////////////
then Fact:=1
else Fact:=n*Fact(n-1)
end;
Числа Фибоначчи
Function F(n:byte):longint;
begin/////////////////////////////////////////////////
Фn = Фn-1 + Фn-2, при n>1/////////////
Ф0 = 1, Ф1 = 1
if n <= 1 /////////////////////////////////////////
then F:=1//////////////////////////////////////
else F:= F(n-1)+F(n-2)
end;
В общем случае любая рекурсивная процедура включает в некоторое множество операторов и один или несколько операторов рекурсивного вызова.
Как было показано, безусловные рекурсивные процедуры приводят к бесконечным процессам, и на эту проблему нужно обратить особое внимание, так как
практическое использование процедур с бесконечным самовызовом невозможно.
Такая невозможность вытекает из того, что для каждой копии рекурсивной процедуры необходимо выделить дополнительную область памяти, а бесконечной
памяти не существует. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Следовательно, главное требование к рекурсивным процедурам заключается
в том, что вызов рекурсивной процедуры должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным. ////////////////////////////////////////////////////////////////////////////////
Если условие истинно, то рекурсивный спуск продолжается. Когда оно становится ложным, то спуск заканчивается и начинается поочередный рекурсивный
возврат из всех вызванных на данный момент копий рекурсивной процедуры.
Структура рекурсивной процедуры может принимать три разных формы:
31
1.
Форма с выполнением действий до рекурсивного вызова (с вы-
полнением действий на рекурсивном спуске):
procedure Rec;
begin
S; {операторы}
If <условие> then Rec;
end;
Рекурсивный спуск на примере нахождения факториала натурального числа. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Для реализации универсального алгоритма вычисления факториала, работающего на спуске, в рекурсивную функцию требуется дополнительно ввести два
параметра: Mult – для выполнения до рекурсивного вызова (т.е. на спуске) операции умножения накапливаемого значения факториала на очередной множитель; m
-для обеспечения независимости рекурсивной функции от имени конкретной глобальной переменной, т. е. для повышения универсальности функции.////////////////////
Program FDOWN; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Var n:integer; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Function Fact_Dn(Mult:longint;I,m:integer):logint; //////////////////////////////////////////////////////////////////////////
begin //////////////////////////////////////////////////////////////////////////////////////////////////////////
Mult:=Mult*i; {Накопление факториала стоит до }
{оператора рекурсивного вызова, } //////////////////////////////////////////////////////////////////////////////////////////////////////////
{отсюда следует, вычисление на спуск.} /////////////////////////////////////////////////////////////////////////////////////////////
if i=m then Fact_Dn:=Mult
else Fact_Dn:=Fact+Dn(Mult,i+1,m); //////////////////////////////////////////////////////////////////////////////////////////////////////////
end; ////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////
Begin ////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////
write(‘ввести число n:’); //////////////////////////////////////////////////////////////////////////////////////////////////////////
readln(n);
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
32
writeln(‘факториал n!=’,Fact_Dn(1,1,n)); /////////////////////////////////////////////////////////////////////////////////////////////
End. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Текущий уровень рекурсии Рекурсивный спуск Рекурсивный возврат
Ввод (n=5)
Fact_Dn (1,1,5)
i := 1
Mult := 1*1
Fact_Dn (1,2,5)
i := 2
Mult := 1*2
Fact_Dn (2,3,5)
i := 3
Mult := 2*3
Fact_Dn (6,4,5)
i := 4
Mult := 6*4
Fact_Dn (24,5,5)
i := 5
Mult := 24*5
i = 120
2.
Форма с выполнением действий после рекурсивного вызова (с
выполнением действий на рекурсивном возврате): /////////////////////////////////////////////////////////////////////
///
////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////////////////////
procedure Rec; //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
begin ////////////////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////
if <условие> then Rec; //////////////////////////////////////////////////////////////////////////////////////////////////////////
S; {операторы} ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
end; ////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////
Рекурсивный возврат на примере нахождения факториала натурального
числа. /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
rogram FactorialUp; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Var n: integer; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Function Fact_Up(I: integer):logint; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Var Mult: longint; //////////////////////////////////////////////////////////////////////////////////////////////////////////
begin //////////////////////////////////////////////////////////////////////////////////////////////////////////
if i=1 then Mult:=1 //////////////////////////////////////////////////////////////////////////////////////////////////////////
else Mult:= Fact_Up (i-1); //////////////////////////////////////////////////////////////////////////////////////////////////////////
Fact_Up:= Mult*i; //////////////////////////////////////////////////////////////////////////////////////////////////////////
33
end; ////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////
Begin ////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////
write(‘ввести число n:’); //////////////////////////////////////////////////////////////////////////////////////////////////////////
readln(n); ////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////
writeln(‘факториал n!=’,Fact_Up(n)); //////////////////////////////////////////////////////////////////////////////////////////////////////////
End.
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Можно провести следующую аналогию. Представим себе, что мы проходим
анфиладу комнат, выполняя предписанные нам действия, распахиваем двери во
все новые и новые комнаты, в каждой из которых оставляем записку себе на память. Пройдя комнаты до конца, мы возвращаемся, выполняя указания, записанные на оставленных нами записках, и плотно закрывая за собой двери. Заметим,
что указания выполняются в порядке, обратном тому, в котором они оставлялись.
Текущий уровень рекурсии Рекурсивный спуск Рекурсивный возврат
Ввод (n=5)
Fact_Up(5)
i := 5
Mult := Fact_Up(4) Fact_Up := 24*5
i := 4
Mult := Fact_Up(3) Fact_Up := 6*4
i := 3
Mult := Fact_Up(2) Fact_Up := 2*3
i := 2
Mult := Fact_Up(1) Fact_Up := 1*2
i := 1
Mult := 1
3.
Вывод n:= 120
Fact_Up := 1*1
Форма с выполнением действий как до, так и после рекурсивного
вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате): ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
procedure Rec;
procedure Rec;
begin
begin
S1;
if <условие> then
if <условие> then Rec;
begin
34
S2;
S1;
end;
Rec;
S2;
end;
end;
Пример: Вывести на печать символы введенной строки в обратном порядке.
Procedure Reverse; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Var ch :Char; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Begin //////////////////////////////////////////////////////////////////////////////////////////////////////////
If Not EoLn Then //////////////////////////////////////////////////////////////////////////////////////////////////////////
Begin Read(ch); Reverse; Write(ch); //////////////////////////////////////////////////////////////////////////////////////////////////////////
End; //////////////////////////////////////////////////////////////////////////////////////////////////////////
End; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Все формы рекурсивных процедур находят применение на практике. Мно-
гие задачи безразличны к тому, какая используется форма рекурсивной процедуры. Однако есть классы задач, при решении которых программисту требуется сознательно управлять ходом работы рекурсивных процедур и функций. Поэтому
глубокое понимание рекурсивного механизма, и умение управлять им по собственному желанию, является необходимым качеством квалифицированного программиста. ////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////
Рекурсивный вызов может быть косвенным. В этом случае подпрограмма
обращается к себе опосредованно, путем вызова другой подпрограммы, в которой содержится обращение к первой. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Согласно правилам языка Паскаль каждый идентификатор перед употреблением должен быть описан. Поэтому в случае взаимного обращения подпрограмм друг к другу необходимо использовать опережающее описание. /////////////////
Опережающее описание заключается в том, что объявляется исключительно
заголовок подпрограммы, а ее тело заменяется зарезервированным словом
35
forward. Следовательно, далее разрешено использовать обращение к подпрограмме, так как известны ее формальные параметры. //////////////////////////////////////////////////////////////////////////////////////
Тело подпрограммы начинается заголовком без указания ранее приведенного списка формальных параметров (и типа результата в случае функции).
Пример косвенной рекурсии: //////////////////////////////////////////////////////////////////////////////////////////////////////////
procedure B( j:integer); forward; procedure A( i:integer); begin
.
.
.
.
.
.
.
.
/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////
B(i); / //////////////////////////////////////////////////////////////////////////////////////////////////////////
. . . . . . . . ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////
end; { конец A}
procedure B ; //////////////////////////////////////////////////////////////////////////////////////////////////////////
begin ////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////
........
A(j); //////////////////////////////////////////////////////////////////////////////////////////////////////////
........
end; { конец B } //////////////////////////////////////////////////////////////////////////////////////////////////////////
Опережающее описание нужно использовать всегда, когда вызывающая
подпрограмма (в приведенном примере процедура A) описана текстуально раньше, чем вызываемая ( процедура B ). //////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
1.3.3. Стековая организация рекурсии
Как правило, с процедурой связывают множество локальных объектов, т.е.
множество переменных, констант, типов и процедур, определённых исключительно в этой процедуре и вне ее не существуют или не имеют смысла.
Стек контекстов
..................
........
36
..................
i+1-й контекст
Состояние РОН
Локальные переменные процедуры
i-й контекст
Адрес возврата
Параметры процедуры
..................
i-1-й контекст
................
........
При новой рекурсивной активации такой процедуры порождается новое
множество локальных взаимосвязанных переменных в специальной области памяти, называемой стеком. Пускай переменные имеют те же самые имена, что и
соответствующие элементы этого множества предыдущего «поколения» этой
процедуры, их значения отличны от последних, любые конфликты по именам
разрешаются по правилу: идентификатор всегда относится к самому последнему
порожденному множеству переменных. Исходя их этого, пользоваться значением
переменной a i-го уровня рекурсии разрешено находясь исключительно на этом iм уровне. Это же правило справедливо и для параметров процедуры. Например,
если процедура Р имеет параметр а и вызывает саму себя, то параметр а этой
вновь вызванной процедуры будет являться совершенно иным параметром; при
возвращении в первую процедуру Р значение первого параметра а будет сохранено. ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
Итак, в момент вызова процедуры в памяти создается ее контекст: выделяется место под все ее параметры, локальные переменные и константы. Уничтожается этот контекст исключительно после того, как будет достигнут оператор End,
закрывающий процедуру, либо в ее тексте встретится оператор Exit, насильственно прерывающий ее выполнение. Таким образом на внутреннем уровне организован стек контекстов подпрограмм. //////////////////////////////////////////////////////////////////////////////////////////////////////////
37
Не следует понимать буквально, что при каждом рекурсивном вызове в памяти создается полная копия процедуры – запоминаются исключительно текущие
значения ее локальных объектов и параметров, сам код процедуры, конечно, в
памяти существует в единственном экземпляре. Понятием полной копии рекурсивной процедуры пользуются лишь для упрощения анализа механизма рекурсии
и облегчения первоначального его восприятия. ////////////////////////////////////////////////////////////////////////////////////////
Пример. Вычислить сумму элементов в массиве а[1..n] целых чисел.
Function Sum ( i :Integer ): Integer; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Begin
////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////
If i>n Then Sum:=0 //////////////////////////////////////////////////////////////////////////////////////////////////////////
Else Sum:=a[i] + Sum ( i + 1); //////////////////////////////////////////////////////////////////////////////////////////////////////////
End; ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////
Как видно из рис.2.1 вначале рекурсивные вызовы порождают «копии» процедуры (точнее функции), в каждой из которой активизируется незавершенная
операция сложения a[i]+... При достижении уровня n+1 начинается возврат и
накопление суммы, начиная с конечногоэлемента массива. Завершается процесс
возвратом в головную программу с окончательным результатом. Подобно операторам цикла, рекурсивные процедуры могут приводить к не заканчивающимся
вычислениям, и поэтому на эту проблему следует особо обратить внимание.
Очевидно, для того чтобы работа когда-либо завершилась, необходимо,
чтобы рекурсивное обращение к Р управлялось некоторым условием В, которое в
какой-то момент перестанет выполняться. Если не ограничивать число рекурсивных вызовов, может быстро возникнуть переполнение стека, особенно если у
процедур много параметров и локальных переменных. Поэтому следует избегать
38
рекурсии там, где существует очевидное итеративное решение, как например, при
вычислении факториала. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Итеративное решение может оказаться предпочтительным не исключительно по расходу памяти, но и по объему вычислительных затрат. Продемонстрируем
это утверждение на примере вычисления чисел Фибоначчи. Вычисление n-го элемента с помощью описанной функции Fib(n) приводит к ее рекурсивным активациям. Как часто это происходит? Каждое обращение с n>1 приводит к двум обращениям, т.е. общее число вызовов растет экспоненциально (рис.2.2).///////////////
Ясно, что такая программа практического интереса не представляет. Однако, числа Фибоначчи разрешено вычислять и по итеративной схеме, где с помощью вспомогательных переменных. //////////////////////////////////////////////////////////////////////////////////////////////////////////
x = F( i ) и y = F( i – 1 ) удается избежать повторных вычислений одной и
той же величины: ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
i:=1; a:=1; b:=0; //////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
While i < n Do
Begin
F := a; a := a+b; b := F; Inc( i );
End;
Write(F);
39
Рассмотренные примеры показывают, что применение рекурсивных определений само по себе не приводит к хорошим решениям задач. Так, задачи вычисления факториала и чисел Фибоначчи допускают более эффективные и достаточно простые итеративные решения. В примерах видно, что рекурсия в них моделирует простой цикл, тратя время на вычисления, связанные с управлением рекурсивными вызовами и память на динамическое хранение данных. ///////////////////////////////////////////
Итак, урок таков: следует избегать рекурсий там, где есть очевидное итерационное решение. Однако это не означает, что от рекурсий следует избавляться
любой ценой. Существует много хороших примеров применения рекурсии, что
мы и продемонстрируем в последующих разделах. То, что существуют реализации рекурсивных процедур на фактически нерекурсивных машинах, доказывает,
что для практических целей любую рекурсивную программу разрешено трансформировать в чисто итеративную. Однако это требует явной работы со стеком
для рекурсий, причем эти действия часто настолько затуманивают суть программы, что ее бывает трудно понять. Вывод: алгоритмы, рекурсивные по своей природе, а не итеративные, нужно формулировать как рекурсивные процедуры.
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
1.3.4. Итерация и рекурсия. Сравнение подходов
Итерация и рекурсия основаны на управляющих структурах: итерация использует структуру повторения, рекурсия использует структуру ветвления.
Итерация, и рекурсия подразумевают повторение: итерация использует
структуру повторения явным образом, рекурсия – посредством повторных вызовов подпрограммы. ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////
Итерация, и рекурсия может происходить бесконечно: итерация попадает
бесконечный цикл, если условие продолжения цикла никогда не становится ложным; рекурсия продолжается бесконечно, если шаг рекурсии не редуцирует задачу таким образом, что задача сходится к нерекурсивному случаю. //////////////////////////////////////
Любая проблема, которая может быть решена рекурсивно, может быть так
же решена и итеративно ( не рекурсивно). //////////////////////////////////////////////////////////////////////////////////////////////////////////
40
Рекурсивный подход предпочтительнее итеративного в тех случаях, когда
рекурсия более естественно отражает математическую сторону задачи и приводит
к программе, которая проще для понимания.
Другой причиной для выбора рекурсивного решения является то, что итеративное решение может не быть очевидным. /////////////////////////////////////////////////////////////////////////////////
Как итерация, так и рекурсия приближаются к завершению постепенно.
Итерация с её проверкой повторения продолжает выполнять тело цикла, пока
условие продолжения цикла не будет нарушено. Рекурсия продолжает производить более простые варианты первоначальной задачи, пока не будет достигнут
нерекурсивный случай. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Рассмотрим пример рекурсивной функции, вычисляющей значение n-го
члена ряда Фибоначчи: //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
function fib(n: integer): integer; begin
if n <= 2 then fib := 1 //////////////////////////////////////////////////////////////////////////////////////////////////////////
else fib := fib(n-1) + fib(n-2); end; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Функция fib содержит два рекурсивных вызова, а в общем случае рекурсивных вызовов в теле подпрограммы может быть сколь-ко угодно. Как видно из
программного кода, эта рекурсивная функция, как и функция вычисления факториала, практически ко-пирует рекуррентные соотношения, определяющие n-й
член ряда. Таким образом, рекурсия оказывается более компактным способом реализации рекуррентных соотношений, нежели итерация. Существуют задачи, в
частности обработка динамических структур данных, для которых рекурсия –
наиболее естественный способ решения. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Но насколько эффективен этот способ? Итеративный алгоритм вычисления
чисел Фибоначчи имел линейную временную сложность и константную емкостную сложность. Чтобы оценить временную сложность рекурсивного алгоритма
необходимо рассчитать общее число операций, выполняемых в результате всех
рекурсивных вызовов. Вызов подпрограммы будем считать одной операцией. Для
n=1 или n=2 выполняются одна проверка условия выхода /////////////////////////////////////////////////////////
41
1)
возврат значения (две операции), а для остальных случаев после про-
верки условия выполняются два вычитания, два рекурсивных вызова, сложение и
присваивание (семь операций). К этому числу ещё необходимо добавить число
операций, выполняемых в результате двух рекурсивных вызовов. Тогда:
для n = 3 имеем ∑(3) = 7 + ∑(2) + ∑(1) = 7+2+2 = 11 операций; для n = 4
имеем ∑(4) = 7 + ∑(3) + ∑(2) = 7+11+2 = 20 операций; для n = 5 имеем ∑(5) = 7 +
∑(4) + ∑(3) = 7+20+10 = 37 операции;
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
Обобщая, получаем ∑(n) = 7 + ∑(n–1) + ∑(n–2), где ∑(2) = 2, ∑(1) = 2.
Итак, получено рекуррентное соотношение, напоминающее со-отношение
для n-го члена ряда Фибоначчи, что для выбранного способа реализации вполне
ожидаемо. Таким образом, сложность рекурсивного алгоритма пропорциональна
fib(n). Для получения аналитического вида функций fib(n) и ∑(n) необходимо
вспомнить удивительное свойство чисел Фибоначчи: ///////////////////////////////////////////////////////////////////////
Тогда для больших n
Таким образом, функция fib(n) оказывается прямо пропорциональна 1,618n.
То же самое справедливо и для ∑(n). Рассмотрим графики функций fib(n), ∑(n) и
1,618n,
представленные
на
рис.
6:
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
42
Видно, что графики fib(n) и sigma(n) повторяют форму графика 1,618n, а сами функции связаны соотношениями //////////////////////////////////////////////////////////////////////////////////////////////////////////
fib(n) = 0,4475*1,618n
Таким образом, сложность рекурсивного алгоритма оценивается как
O(1,618n). Можно заметить, что функция fib(n) возрастает бы-стрее n2 и в точке n
= 12 перегоняет её. Столь низкая производи-тельность рекурсивной функции
fib(n) объясняется тем, что вычис-ления многократно повторяются. Визуально рекурсивные вызовы разрешено представить в виде дерева, где число повторных
вычисле-ний растёт при углублении рекурсии (рис. 7).
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///// ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
43
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
Преимущества рекурсии заключаются в следующих аспектах://///////////////////
1) часто это наиболее легкий метод написания алгоритма для задач, которые
разрешено решить с помощью рекурсии (число фибоначчи, факториал);////////////////
2) рекурсивно реализованные алгоритмы, при правильных на то основаниях,
имеют лаконичную запись и менее трудоёмки при последующей отладке и модификации, они сокращают временные затраты на разработку, отладку и модификацию программных средств;целый ряд структур данных и многие объекты современных языков программирования рекурсивны по самой своей сути (фрактальные
объекты, иерархия классов в объектно – ориентированном программировании,
древовидные регулярные структуры данных) и программы для работы с такими
структурами выглядят намного более естественно в рекурсивной реализации;
3) рекурсия делает код более читабельным (позволяет читать код с любого места, не просматривая его весь, отслеживая все изменения переменной), что облегчает отладку; ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
44
4) рекурсия защищает от ошибок типа: «действия выполнены в неверном порядке», «использована неинициализированная переменная» и других аналогичных.[13] ////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////
Недостатки рекурсии заключаются в следующем: //////////////////////////////////////////////////////////////////
1) велика возможность войти в бесконечный цикл; ////////////////////////////////////////////////////////////////////////
2) при использовании некоторых формул слишком большие затраты памяти
компьютера (к примеру, при вычислении числа Фибоначчи или факториалов,
необходимо запоминать все значения чисел и вычислять одни и те же значения по
многу раз); ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////
3) в случае если вызываемых функций будет очень много, может произойти
переполнение стека; //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
4) следует избегать использования рекурсии в случаях, когда требуется высокая эффективность, так как они требуют времени и дополнительных затрат памяти и обладают худшей временной эффективностью.[13] //////////////////////////////////////////////////////////////
Обслуживание рекурсивных вызовов влечет определенные накладные расходы, но при этом рекурсивные алгоритмы, разработанные методом декомпозиции, имеют лучшие асимптотические оценки. Это означает, что, начиная с некоторой длины входа, достаточно часто соответствующей области практического
использования, программная реализация рекурсивного алгоритма будет иметь
лучшие временные показатели. //////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////////////////////// /
45
ГЛАВА 2. МЕТОДИКА ИЗУЧЕНИЯ ТЕМЫ «ОРГАНИЗАЦИЯ РЕКУРСИВНЫХ АЛГОРИТМОВ В ЯЗЫКАХ ПРОГРАММИРОВАНИЯ PASCAL И DELPHI» В ПРОФИЛЬНОМ КУРСЕ ИНФОРМАТИКИ
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
2.1. Цель и задачи изучения темы "Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi» в профильном курсе
информатики
Цель: ////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////
Освоение учащимися теоретических знаний и практических навыков в области алгоритмизации и программирования(ООП), взаимосвязанных с построением рекурсивных алгоритмов на языках программирования Pascal, Delphi; подготовка к успешной сдаче «ЕГЭ»; изучение выпускником данной темы в рамках
профильного курса, как предоставление возможности выбора будущей профессии. ////////////////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////////////////
Задачами изучения темы в профильном курсе информатике являются:
1. Изучение теоретических и практических основ организации рекурсивных
алгоритмов. ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////
2. Овладение умениями и навыками по разработке и реализации рекурсивных алгоритмов на языках программирования Pascal, Delphi.//////////////////////////////////
3. Разбор заданий с использованием рекурсивных алгоритмов, входящих в
ЕГЭ, подготовка к его сдаче. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
3.2.
Требования к результатам обучения /////////////////////////////////////////////////////////////////////////////
В результате изучения темы «Организация рекурсивных алгоритмов в
языках программирования Pascal и Delphi» на профильном уровне ученик
должен //////////////////////////////////////////////////////////////////////////////////////////////////////////
знать: ////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////

основные конструкции языка программирования; ////////////////////////////////////////////////////////////////////////

свойства алгоритмов и основные алгоритмические конструкции;
46

понятия: рекурсия, рекуррентная формула, рекуррентная последователь-
ность; ////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////////////

виды «Рекурсии»;

алгоритмы быстрой сортировки;

описание рекурсивных алгоритмов программе.
уметь: ////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////

реализовать разработанный алгоритм на ЯП; ////////////////////////////////////////////////////////////

отличать рекурсивные алгоритмы от итерационных; /////////////////////////////////////////////////////////

проводить трассировку построенного алгоритма;

определять актуальность применения рекурсивных алгоритмов;

выполнять требования техники безопасности, гигиены, эргономики и ресур-
сосбережения при работе со средствами информатизации; обеспечение надежного
функционирования средств ИКТ.[2]
владеть: ////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////

умениями работы в программной среде ЯП;

понятийным аппаратом темы «Организация рекурсивных алгоритмов;

умениями и навыками по разработке и реализации рекурсивных алгоритмов
на ЯП. ////////////////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////////////
Личностные, метапредметные и предметные результаты
освоения темы «Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi»
Личностные результаты:
- Сформированность мировоззрения, соответствующего современному
уровню развития науки и общественной практики. ///////////////////////////////////////////////////////////////////////////////
- Сформированность навыков сотрудничества со сверстниками, детьми
младшего возраста, взрослыми в образовательной, общественно полезной, учебно-исследовательской, проектной и других видах деятельности.////////////////////////////
47
- Бережное, ответственное и компетентное отношение к физическому и психологическому здоровью как собственному, так и других людей, умение оказывать первую помощь.[2] ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- Готовность и способность к образованию, в том числе самообразованию,
на протяжении всей жизни; сознательное отношение к непрерывному образованию как условию успешной профессиональной и общественной деятельности;
осознанный выбор будущей профессии и возможностей реализации собственных
жизненных планов. //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Метапредметные результаты: ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- Умение самостоятельно определять цели и составлять планы; самостоятельно осуществлять, контролировать и корректировать учебную и внеучебную
(включая внешкольную) деятельность; использовать все возможные ресурсы для
достижения целей; выбирать успешные стратегии в различных ситуациях.[2]
- Умение продуктивно общаться и взаимодействовать в процессе совместной деятельности, учитывать позиции другого, эффективно разрешать конфликты. ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
-
Готовность
и
способность
к
самостоятельной
информационно-
познавательной деятельности, включая умение ориентироваться в различных источниках информации, критически оценивать и интерпретировать информацию,
получаемую из различных источников. //////////////////////////////////////////////////////////////////////////////////////////////////////////
- Владение навыками познавательной рефлексии как осознания совершаемых действий и мыслительных процессов, их результатов и оснований, границ
своего знания и незнания, новых познавательных задач и средств их достижения.
Предметные результаты, которые ориентированы на обеспечение, преимущественно, общеобразовательной и общекультурной подготовки://////////////////
- Знание основных понятий: рекурсия, рекурсивный алгоритм, рекуррентная
формула, стек, глубина рекурсии, прямая рекурсия, косвенная рекурсия.
-Знание основных форм рекурсивных алгоритмов: форма с выполнением
действий до рекурсивного вызова (с выполнением действий на рекурсивном спус-
48
ке), форма с выполнением действий после рекурсивного вызова (с выполнением
действий на рекурсивном возврате), форма с выполнением действий как до, так и
после рекурсивного вызова (с выполнением действий как на рекурсивном спуске,
так и на рекурсивном возврате); умение их различать и применять в разработке
программ на ЯП. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- Знание основных конструкций языка программирования необходимых для
построения рекурсивных алгоритмов. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- Умение анализировать рекурсивные алгоритмы проводить их трассировку. //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- Умение определять актуальность применения рекурсии к предложенной
задаче. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- Умение разрабатывать рекурсивные алгоритмы на примере: алгоритма
быстрой сортировки, Задачи о Ханойской башне, задачи на поиск пути и др.
- Сформированность базовых навыков и умений по построению рекурсивных алгоритмов.[2] ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
2.3. Место изучения темы в структуре образовательного процесса.
Изучение темы «Организация рекурсивных алгоритмов» входит в профильный курс информатики. Данная тема изучается в 11 классе. На изучение материалов темы отводится 8 часов.[1] //////////////////////////////////////////////////////////////////////////////////////////////////////////
Содержание темы «Организация рекурсивных алгоритмов в языках
программирования Pascal и Delphi»
(7+1 часов)
1. Рекурсивные методы программирования. Рекурсивные подпрограммы.
2. Задача о Ханойской башне. Числа Фибоначчи.
3. Алгоритм быстрой сортировки.
4. Организация рекурсивных алгоритмов в среде ООП Delphi.
5. Задача на поиск пути в ООП Delphi.
6. Рекурсивные алгоритмы в заданиях к ЕГЭ.
49
7. Контрольная работа: «Рекурсивные методы программирования».
8. Лабораторная работа: «Рекурсивные методы программирования».
Практические работы: «Проект факториала и проект программы поиска
файлов», «Проект поиска пути».
* Кривая Гильберта. (Материал для самостоятельного изучения)
50
Тематическое планирование
с определением основных видов учебной деятельности
Рекурсивные методы программи- Аналитическая деятельность:
Организация рекурсивных алго-
ритмов в языках программирования рования. Рекурсивные подпрограммы.
Фибоначчи.
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
Организация рекурсивных алгоритмов в
среде ООП Delphi.
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
phi.
рекурсии,
 сопоставлять
различные формы
Урок - практикум: «Рекурсивные рекурсивных алгоритмов;
методы программирования».
 реализовывать
рекурсивные
Контрольная работа: «Рекурсив- алгоритмы программными средствами
ные
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
примеры
Рекурсивные алгоритмы в задани- Практическая деятельность:
ях к ЕГЭ
 осуществлять
разработку
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
 приводить
рекурсии актуальность ее применения.
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
рекурсивные
рекурсивных алгоритмов;
Задача на поиск пути в ООП Del-
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
 анализировать
Алгоритм быстрой сортировки. алгоритмы;
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
признаки и
Задача о Ханойской башне. Числа свойства рекурсии;
Pascal и Delphi
(7+1 часов)
 выявлять черты,
методы
программирования». ЯП.
//////////////////////////////////////////////////////////////////////////////////////////////////////////
51
Календарно-тематическое планирование
Требования к результатам обучения
№ п/п
1.
Дата
Тема урока
Тип урока
Рекурсивные
методы
программирования.
Рекурсивные подпрограммы.
Урок изучения нового
материала
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
Формы и
методы
работы
Лекция,
демонстрация
УУД
Личностные
результаты
Предметные результаты
Регулятивные: целеполагание
– формулировать и удерживать
учебную задачу; планирование
–
выбирать
действия
в соответствии с поставленной
задачей
и
условиями
ее
реализации.
Познавательные:
общеучебные – использовать
общие
приемы
решения
поставленных
задач;
Коммуникативные:
инициативное сотрудничество
– ставить вопросы, обращаться
за помощью.
Умение продуктивно общаться и
взаимодействовать в процессе совместной деятельности, учитывать
позиции другого, эффективно разрешать конфликты.
Готовность и способность к самостоятельной
информационнопознавательной
деятельности,
включая умение ориентироваться в
различных источниках информации,
критически оценивать и интерпретировать информацию, получаемую
из
различных
источников.
Знание основных понятий:
рекурсия, рекурсивный алгоритм, рекуррентная формула, стек, глубина рекурсии, прямая рекурсия, косвенная рекурсия.
Знание основных форм рекурсивных
алгоритмов.
Умение анализировать рекурсивные алгоритмы проводить их трассировку. Знание основных конструкций
языка
программирования
необходимых для построения рекурсивных алгоритмов.
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
52
2.
3.
Задача о Ханойской
башне. Числа Фибоначчи.
Комбинированный
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
Алгоритм быстрой сортировки.
Комбинированный
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
Лекция,
демонстрация
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
Лекция,
демонстрация
Регулятивные:
оценка
–
устанавливать
соответствие
полученного
результата
поставленной
цели.
Познавательные:
информационные – искать и
выделять
необходимую
информацию из различных
источников.
Коммуникативные: управление коммуникацией – адекватно
использовать речь для планирования и регуляции своей деятельности
//////////////////////////////////////////////////////////////
////////////////////////////////////////////
//////////////////////////////////////////////////////////////
////////////////////////////////////////////
//////////////////////////////////////////////////////////////
////////////////////////////////////////////
//////////////////////////////////////////////////////////////
////////////////////////////////////////////
//////////////////////////////////////////////////////////////
////////////////////////////////////////////
Регулятивные: целеполагание
–
преобразовывать
практическую
задачу
в образовательную; контроль и
самоконтроль – использовать
установленные
правила
в
контроле способа решения
задачи.
Познавательные:
общеучебные
–
выбирать
наиболее
эффективные
решения поставленной задачи.
Коммуникативные: взаимодействие – формулировать собственное мнение и позицию.
Готовность и способность к самостоятельной
информационнопознавательной
деятельности,
включая умение ориентироваться в
различных источниках информации,
критически оценивать и интерпретировать информацию, получаемую
из различных источников.
Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов. Умение разрабать
рекурсивные алгоритм Задачи о Ханойской башне, его
реализация
на
ЯП.
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
Готовность и способность к самостоятельной
информационнопознавательной
деятельности,
включая умение ориентироваться в
различных источниках информации,
критически оценивать и интерпретировать информацию, получаемую
из
различных
источников.
Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов. Умение разработать
рекурсивный
алгоритм
быстрой сортировки, его
реализация
на
ЯП.
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
53
4.
5.
Лабораторная работа:
«Рекурсивные методы
программирования»
Урокпрактикум
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
Организация рекурсивных алгоритмов в среде
ООП Delphi.
Урок изучения нового
материала
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
Практическая работа за компьютером
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
Лекция,
демонстрация,
работа за
компьютером
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
Регулятивные: целеполагание
–
преобразовывать
практическую
задачу
в
образовательную.
Познавательные:
общеучебные
–
выбирать
наиболее
эффективные
решения поставленной задачи.
Коммуникативные: взаимодействие – задавать вопросы, формулировать
свою
позицию.
//////////////////////////////////////////////////////////////
////////////////////////////////////////////
//////////////////////////////////////////////////////////////
////////////////////////////////////////////
//////////////////////////////////////////////////////////////
////////////////////////////////////////////
//////////////////////////////////////////////////////////////
////////////////////////////////////////////
//////////////////////////////////////////////////////////////
////////////////////////////////////////////
//////////////////////////////////////////////////////////////
////////////////////////////////////////////
Регулятивные: целеполагание
– формулировать и удерживать
учебную задачу; планирование
–
выбирать
действия
в соответствии с поставленной
задачей
и
условиями
ее
реализации.
Познавательные:
общеучебные – использовать
общие
приемы
решения
поставленных
задач;
Коммуникативные:
инициативное сотрудничество
– ставить вопросы, обращаться
за помощью.
Готовность и способность к самостоятельной
информационнопознавательной
деятельности,
включая умение ориентироваться в
различных источниках информации,
критически оценивать и интерпретировать информацию, получаемую
из различных источников.
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
Умение продуктивно общаться и
взаимодействовать в процессе совместной деятельности, учитывать
позиции другого, эффективно разрешать конфликты.
Готовность и способность к самостоятельной
информационнопознавательной
деятельности,
включая умение ориентироваться в
различных источниках информации,
критически оценивать и интерпретировать информацию, получаемую
из различных источников.
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
Знание основных понятий:
рекурсия, рекурсивный алгоритм, рекуррентная формула, стек, глубина рекурсии, прямая рекурсия, косвенная рекурсия.
Знание основных форм рекурсивных
алгоритмов.
Умение анализировать рекурсивные алгоритмы проводить их трассировку. Знание основных конструкций
языка
программирования
необходимых для построения рекурсивных алгоритмов.
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
Знание основных понятий:
рекурсия, рекурсивный алгоритм, рекуррентная формула, стек, глубина рекурсии, прямая рекурсия, косвенная рекурсия.
Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов.
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
54
6.
7.
Задача на поиск пути в
ООП Delphi.
Комбинированный
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
*
Кривая
Гильберта
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
Комбинированный
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
Лекция,
демонстрация,
работа за
компьютером
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
Материал
для самостоятельного изучения
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
Регулятивные: целеполагание
– преобразовывать
практическую задачу
в образовательную; контроль и
самоконтроль – использовать
установленные правила в
контроле способа решения
задачи.
Готовность и способность к самостоятельной
информационнопознавательной
деятельности,
включая умение ориентироваться в
различных источниках информации,
критически оценивать и интерпретировать информацию, получаемую
из
различных
источников.
//////////////////////////////////////////////////////////////
////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
Познавательные:
общеучебные – выбирать
наиболее эффективные
решения поставленной задачи.
Коммуникативные: взаимодействие – формулировать собственное
мнение
и
позицию.
//////////////////////////////////////////////////////////////
////////////////////////////////////////////
Регулятивные: целеполагание
– преобразовывать
практическую задачу
в образовательную; контроль и
самоконтроль – использовать
установленные правила в
контроле способа решения
задачи.
Познавательные:
общеучебные – выбирать
наиболее эффективные
решения поставленной задачи.
Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов. Умение разработать
рекурсивный алгоритм задача на поиск пути в ООП
Delphi, его реализация на
ЯП.
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
Готовность и способность к самостоятельной
информационнопознавательной
деятельности,
включая умение ориентироваться в
различных источниках информации,
критически оценивать и интерпретировать информацию, получаемую
из различных источников.
Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов. Умение разработать
рекурсивный алгоритм Кривая Гильберта, его реализация
на
ЯП.
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
55
8.
Рекурсивные алгоритмы в заданиях к ЕГЭ
Комбинированный
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
9.
Лекция,
демонстрация
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
////////////////////
////////////////////
////////////////////
////////////////////
////////////////////
//////
Контрольная
работа
«Рекурсивные методы
программирования».
Урок
контроля и оценки
знаний
//////////////////////////////////////////////
//////////////////////////////////////////////
///////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
///////////////////////////
///////////////////////////
///////////////////////////
/////////////////////////
Контрольная
работа
Регулятивные: целеполагание
– преобразовывать
практическую задачу
в образовательную; контроль и
самоконтроль – использовать
установленные правила в
контроле способа решения
задачи.
Познавательные:
общеучебные – выбирать
наиболее эффективные
решения поставленной задачи.
Коммуникативные:
взаимодействие – формулировать
собственное мнение и позицию.
Готовность и способность к самостоятельной
информационнопознавательной
деятельности,
включая умение ориентироваться в
различных источниках информации,
критически оценивать и интерпретировать информацию, получаемую
из различных источников.
Регулятивные: целеполагание
– преобразовывать
практическую задачу
в образовательную; контроль и
самоконтроль – использовать
установленные правила в
контроле способа решения
задачи.
Познавательные:
общеучебные – выбирать
наиболее эффективные
решения поставленной задачи.
Коммуникативные: взаимодействие – формулировать собственное мнение и позицию.
Умение самостоятельно определять
цели и составлять планы; самостоятельно осуществлять, контролировать и корректировать учебную и
внеучебную (включая внешкольную) деятельность; использовать
все возможные ресурсы для достижения целей; выбирать успешные
стратегии в различных ситуациях.
Умение продуктивно общаться и
взаимодействовать в процессе совместной деятельности, учитывать
позиции другого, эффективно разрешать конфликты.
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
//////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////
Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов. Умение анализировать рекурсивные алгоритмы
и решать связанные с ними
задания, которые представленные
на
ЕГЭ
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
//////////////////////////////////////////////////
////////////////////////////////////////////////////////
Знание основных понятий:
рекурсия, рекурсивный алгоритм, рекуррентная формула, стек, глубина рекурсии, прямая рекурсия, косвенная рекурсия.
Знание основных форм рекурсивных
алгоритмов.
Умение анализировать рекурсивные алгоритмы проводить их трассировку. Знание основных конструкций
языка
программирования
необходимых для построения рекурсивных алгоритмов.
56
2.4. Методические рекомендации к проведению занятий.
//////////////////////////////////////////////////////////////////////////////////////////////////////////
Урок 1. Рекурсивные методы программирования. Рекурсивные подпрограммы. ////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////
Цели урока: ////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////
Образовательные (обучающие): познакомить учащихся с понятием рекурсия, рекурсивный алгоритм, разобрать примеры применения рекурсивных алгоритмов. ////////////////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////////////////
Развивающие: продолжить развивать навыки
владения ИКТ – техноло-
гией, логическое мышление, навыки работы с ЯП Pascal. ///////////////////////////////////////////////////////////////
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса.
Планируемые результаты:
Предметные:
 знание основных понятий: рекурсия, рекурсивный алгоритм, рекуррентная
формула, стек, глубина рекурсии, прямая рекурсия, косвенная рекурсия;
 знание основных форм рекурсивных алгоритмов;
 умение анализировать рекурсивные алгоритмы проводить их трассировку. Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов.
Основные понятия, изучаемые на уроке:
 рекурсия;
 рекурсивный алгоритм;
 рекурсивный объект;
 глубина рекурсии;
 рекурсивный спуск;
 рекурсивный возврат;
 рекурсивный спуск и рекурсивный возврат;
 косвенная рекурсия.
Используемые на уроке средства ИКТ:
57
 персональный компьютер (ПК) учителя, мультимедийный проектор,
экран; ПК учащихся.
Электронное приложение к учебнику:
Презентация:
 Рекурсивные методы программирования. Рекурсивные подпрограммы.
Тип урока: урок изучения нового материала.
Этапы урока:
I. Организационный момент (мотивационная беседа)
II. Повторение изученного (создание ситуации успеха)
III. Целеполагание
IV. Изучение нового материала.
V. Практическая работа.
VI. Итоги урока и оценка знаний учащихся.
VII. Задание на дом.
Особенности изложения содержания темы урока:
Начать урок следует с повторения раннее изученного материала. Важно
дать возможность учащимся вспомнить некоторые понятия моменты, связанные с
изучением подпрограмм.
Вспомнить:
-Что такое подпрограмма?
-Какие существуют виды подпрограмм?
-Что такое процедура и функция, принципы их работы.
-Формат записи в программе.
Далее привести примеры рекурсии, которые окружают нас в повседневной
жизни, для ее понимания на бытовом уровне.
Затем дать определение рекурсии в программировании. Привести пример.
Разобрать формат записи на языке программирования, принцип работы алгоритма. Указать основные формы рекурсии. Привести примеры.
Важно обратить внимание учеников на то, что задачи на решение рекурсивных алгоритмов даются в ЕГЭ.
58
В практической части занятия рекомендуется дать возможность ученикам
(10 –15 минут) реализовать некоторые из примеров рекурсивных алгоритмов.
Домашнее задание:
Записи в тетрадях.
Урок 2. Задача о Ханойской башне. Числа Фибоначчи.
Цели урока:
Образовательные (обучающие): закрепить знания учащихся по теме «Рекурсивные подпрограммы», рассмотреть решение задачи о Ханойской башне.
Развивающие: продолжить развивать навыки
владения ИКТ – техноло-
гией, логическое мышление, навыки работы с ЯП Pascal.
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса.
Планируемые результаты:
Предметные:
 знание основных форм рекурсивных алгоритмов;
 умение анализировать рекурсивные алгоритмы проводить их трассировку. Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов.
 Умение построить рекурсивный алгоритм задачи о Ханойских башнях.
 Умение построить рекурсивный алгоритм нахождения чисел Фибоначчи.
Основные понятия, изучаемые на уроке:
 рекурсия;
 рекурсивный алгоритм;
Используемые на уроке средства ИКТ:
 персональный компьютер (ПК) учителя, мультимедийный проектор,
экран; ПК учащихся.
Электронное приложение к учебнику:
Презентация:
59
 «Задача о Ханойской башне. Числа Фибоначчи».
Тип урока: комбинированный.
Этапы урока:
I. Организационный момент (мотивационная беседа).
II. Повторение изученного (создание ситуации успеха).
III. Сообщение темы и постановка цели урока.
IV. Изучение нового материала.
V. Практическая работа.
VI. Итоги урока и оценка знаний учащихся.
VII. Задание на дом.
Особенности изложения содержания темы урока
В начале урока следует провести мотивационную беседу, включив в нее
вопросы по предыдущей теме. После того, как класс совместно с учителем сформулировал тему урока и поставил задачи на текущее занятие, учитель рассказывает легенду о Ханойской башне. Рассказ также направлен на повышение мотивации учащихся.
Далее следует объяснение материала сопровождающееся демонстрацией.
Изучение Чисел Фибоначчи следует начать с автобиографии Леонардо Пизанского(Фибоначчи).
Перед практической частью урока провести динамическую паузу. практической части занятия рекомендуется дать возможность ученикам (10 –15 минут)
реализовать алгоритм задачи о Ханойской Башне и алгоритм нахождения Чисел
Фибоначчи.
Домашнее задание:
Записи в тетрадях.
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////
Урок 3. Алгоритм быстрой сортировки.
Цели урока: ////////////////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////
Образовательные (обучающие): закрепить знания учащихся по теме «Рекурсивные подпрограммы», рассмотреть алгоритм быстрой сортировки.
60
Развивающие: продолжить развивать навыки
владения ИКТ – техноло-
гией, логическое мышление, навыки работы с ЯП Pascal.
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса.
Планируемые результаты: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Предметные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 знание основных форм рекурсивных алгоритмов;
 умение анализировать рекурсивные алгоритмы проводить их трассировку. Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов.
 Умение построить алгоритм «Быстрой сортировки».
Основные понятия, изучаемые на уроке:
 рекурсия; //////////////////////////////////////////////////////////////////////////////////////////////////////////
 рекурсивный алгоритм; //////////////////////////////////////////////////////////////////////////////////////////////////////////
 алгоритм быстрой сортировки. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Используемые на уроке средства ИКТ: /////////////////////////////////////////////////////////////////////////////////////
 персональный компьютер (ПК) учителя, мультимедийный проектор,
экран; ПК учащихся.
Электронное приложение к учебнику:
Презентация: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 «Алгоритм быстрой сортировки». //////////////////////////////////////////////////////////////////////////////////////////////////////////
Тип урока: комбинированный. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Этапы урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////
I. Организационный момент. //////////////////////////////////////////////////////////////////////////////////////////////////////////
II. Проверка домашнего задания. //////////////////////////////////////////////////////////////////////////////////////////////////////////
III. Сообщение темы и постановка цели урока.
IV. Изучение нового материала. //////////////////////////////////////////////////////////////////////////////////////////////////////////
V. Практическая работа. //////////////////////////////////////////////////////////////////////////////////////////////////////////
VI. Итоги урока и оценка знаний учащихся.
61
VII. Задание на дом. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Особенности изложения содержания темы урока:
Проверка домашнего задания проходит в виде индивидуальной работы по
карточкам. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Вариант 1.
1.
Дайте определение понятию «Рекуррентная формула».
2.
Напишите рекурсивный вариант подпрограммы-процедуры
нахождения чисел Фибоначчи. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Вариант 2.
1.
Дайте определение понятию «Рекурсивная подпрограмма
(функция, процедура». //////////////////////////////////////////////////////////////////////////////////////////////////////////
2.
Напишите рекурсивный вариант нахождения факториала.
Объяснение нового материала следует начать с автобиографии Ричарда
Хоара. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Важно указать три идеи алгоритма быстрой сортировки, как его основной
принцип работы. Объяснение материала ведется на примере задачи с текущей демонстрацией.
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
Перед практической частью урока провести динамическую паузу. практической части занятия рекомендуется дать возможность ученикам (10 –15 минут) реализовать алгоритм Быстрой сортировки на компьютерах.
Домашнее задание: //////////////////////////////////////////////////////////////////////////////////////////////////////////
62
Записи в тетрадях. //////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
Урок 4. Лабораторная работа: «Рекурсивные методы программирования». //////////////////////////////////////////////////////////////////////////////////////////////////////////
Цели урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Обучающие: сформировать/закрепить навыки создания рекурсивных подпрограмм; вспомнить алгоритм создания подпрограмм в языке программирования
Pascal. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Развивающие: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Развивать способность учащихся анализировать информацию;
 Развивать образное, критическое мышление;
 Развитие системного мышления. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса.
Предметные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Сформировать представление о рекурсивных методах программирования. ////////////////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////////////////
 Умение создавать рекурсивные алгоритмы в ЯП Pascal.
Используемые на уроке средства ИКТ:
 персональный компьютер (ПК) учителя, мультимедийный проектор,
экран; ПК учащихся. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Электронное приложение к учебнику: ///////////////////////////////////////////////////////////////////////////////////////
Презентация: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Лабораторная работа: «Рекурсивные методы программирования»
Тип урока: лабораторная работа. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Этапы урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////
I. Организационный момент. //////////////////////////////////////////////////////////////////////////////////////////////////////////
II. Актуализация знаний. //////////////////////////////////////////////////////////////////////////////////////////////////////////
III. Постановка цели урока. //////////////////////////////////////////////////////////////////////////////////////////////////////////
63
IV. Практическая работа за компьютером.
V. Динамическая пауза. //////////////////////////////////////////////////////////////////////////////////////////////////////////
VI. Контроль за результатом учебной деятельности школьников.
VII. Рефлексия деятельности. //////////////////////////////////////////////////////////////////////////////////////////////////////////
VIII. Запись домашнего задания. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Особенности изложения содержания темы урока:
Урок следует начать с повторения изученного материала. Проводится фронтальный опрос учащихся. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Далее учитель сообщат тему урока. Учащиеся формулируют его цель. Учитель делит класс на два варианта. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Проводит вводный инструктаж. Отвечает на вопросы по условию предложенных заданий, возникшие у учащихся. Проводит инструктаж по технике безопасности при работе за компьютером. Рассаживает учащихся за компьютеры. По
ходу выполнения лабораторной работы ведет текущий инструктаж.
Важно сделать динамическую паузу. Это позволит сменить вид деятельности, учащиеся смогут немного отдохнуть от работы за компьютером.
В конце урока учитель проводит анализ выполненных работ. Разбирает задания и возникшие трудности. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Домашнее задание: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Записи в тетрадях. //////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
Урок 5. Организация рекурсивных алгоритмов в среде ООП Delphi.
Цели урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Образовательные (обучающие): познакомить учащихся с понятием
рекурсия, разобрать примеры применения рекурсивных алгоритмов в среде ООП
Delphi.
Развивающие: продолжить развивать навыки
владения ИКТ – техноло-
гией, логическое мышление, навыки работы в ООП Delphi.
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса. ///////////////////////////////////////////////////////////////////////
64
Планируемые результаты: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Предметные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 знание основных понятий: рекурсия, рекурсивный объект, глубина рекурсии, прямая рекурсия, косвенная рекурсия;
 умение анализировать рекурсивные алгоритмы проводить их трассировку. Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Используемые на уроке средства ИКТ:
 персональный компьютер (ПК) учителя, мультимедийный проектор,
экран; ПК учащихся. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Электронное приложение к учебнику:
Презентация: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 «Организация рекурсивных алгоритмов в среде ООП Delphi».
Тип урока: Комбинированный. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Этапы урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////
I. Организационный момент. //////////////////////////////////////////////////////////////////////////////////////////////////////////
II. Сообщение темы и постановка цели урока.
III. Изучение нового материала. //////////////////////////////////////////////////////////////////////////////////////////////////////////
IV. Практическая работа за компьютером.
IV. Итоги урока и оценка знаний учащихся.
V. Задание на дом.
Особенности изложения содержания темы урока:
В начале урока учащимся дается возможность вспомнить основные понятия
связанные с рекурсией. Учитель проводит с аналогию с рекурсивными алгоритмами в языке программирования Pascal.
Объяснение нового материала проводится с опорой на пример. В данном
случае на классический пример рекурсии – факториал. ////////////////////////////////////////////////////////////////
Учитель указывает основные компоненты необходимые для создания проекта. Производит разбор программного кода. ///////////////////////////////////////////////////////////////////////////////////////////////
65
Стоит сказать о ошибках, которые могут возникнуть при работе проекта, изза диапазона значений переменных, и что Delphi может включить в исполняемую
программу инструкции контроля диапазона значений переменных.
Далее разбирается пример задачи на поиск файлов.
Все объяснение ведется с демонстрацией. ////////////////////////////////////////////////////////////////////////////////////
В практической части урока, учащимся предлагается реализовать оба проекта за компьютером. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Задание на дом:
Задача 1. Создать проект расчета суммы
procedure TForm1.Button1Click(Sender: TObject);
var y :real; //сумма ряда
n:real; //количество членов ряд
eps:real; //точность
function s(y,u,i:real):real;
{y-значение суммы ряда в начале шага,
u-очередной член ряда,
i-номер очередного члена ряда}
var sp:real;
begin sp:=y+u;
u:=-u/(2*i-1)/(2*i); //рекуррентная формула
if abs(u)=n} then
{ для конечного ряда условие с n, а для бесконечного с eps }
begin s:=sp; //терминальная ветвь
Memo1.Lines.Add('Количество слагаемых '+FloatToStr(i))
end
else s:=s(sp,u,i+1); //рекурсивное вычисление
end;
begin Memo1.Clear;
// для конечного ряда задается n, а для бесконечного eps
eps:=StrToFloat(Edit1.Text);{n:=StrToFloat(Edit1.Text);}
ряда .
66
// задаются значения y,u,i для первого шага
y:=s(0,1,1);
Memo1.Lines.Add('Сумма '+FormatFloat('0.000000',y)) end;
(Слайд 3) Форма проекта
Урок 6. Задача на поиск пути в ООП Delphi.
Цели урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Образовательные (обучающие): закрепить знания о процедурах и функциях, разобрать примеры применения рекурсивных алгоритмов в среде ООП Delphi
для решения задач на поиск пути. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Развивающие: продолжить развивать навыки
владения ИКТ – техноло-
гией, логическое мышление, навыки работы в ООП Delphi.
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса.
Планируемые результаты: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Предметные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 знание основных понятий: рекурсия, рекурсивный объект, глубина рекурсии, прямая рекурсия, косвенная рекурсия;
67
 умение анализировать рекурсивные алгоритмы проводить их трассировку. Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Используемые на уроке средства ИКТ:
 персональный компьютер (ПК) учителя, мультимедийный проектор,
экран; ПК учащихся. ////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////
Электронное приложение к учебнику: /////////////////////////////////////////////////////////////////////////////////////////
Презентация: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 «Задача на поиск пути в ООП Delphi».
Тип урока: Комбинированный. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Этапы урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////
I. Организационный момент. //////////////////////////////////////////////////////////////////////////////////////////////////////////
II. Проверка домашнего задания. //////////////////////////////////////////////////////////////////////////////////////////////////////////
III. Сообщение темы и постановка цели урока.
IV. Изучение нового материала. //////////////////////////////////////////////////////////////////////////////////////////////////////////
V. Практическая работа за компьютером.
VI. Задание на дом. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Особенности изложения содержания темы урока:
В начале урока учитель проверяет домашнее задание. Рассаживает учащихся за компьютеры. Ученики запускают проект. Далее учитель проводит разбор и
оценку задания. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Объяснение нового материала проводится с опорой на пример. Учитель
указывает основные компоненты необходимые для создания проекта. Производит
разбор программного кода. Следует указать как проводить поиска кратчайшего
пути.
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
68
Все объяснение ведется с демонстрацией. Карта дорог между городами может быть изображена в виде графа — набора вершин, означающих города, и ребер, обозначающих дороги. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Можно показать блок - схему процедуры выбора точки маршрута.
В практической части урока, учащимся предлагается реализовать проект
задачи поиска пути за компьютером. В процессе выполнения практической работы следует сделать динамическую паузу.
Задание на дом: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Записи в тетрадях. //////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
Урок 7. Кривая Гильберта. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Образовательные (обучающие): закрепить знания о процедурах и функциях, разобрать примеры применения рекурсивных алгоритмов в среде ООП Delphi
для построения «Кривой Гильберта». //////////////////////////////////////////////////////////////////////////////////////////////////////////
69
Развивающие: продолжить развивать навыки
владения ИКТ – техноло-
гией, логическое мышление, навыки работы в ООП Delphi.
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого. /////////////////////////////////////////////////////////////////////////////////////////////
Планируемые результаты: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Предметные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 знание основных понятий: рекурсия, рекурсивный объект, глубина рекурсии, прямая рекурсия, косвенная рекурсия;
 умение анализировать рекурсивные алгоритмы проводить их трассировку. Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов.
 Умение построить алгоритм позволяющий вывести на экран «Кривую
Гильберта». //////////////////////////////////////////////////////////////////////////////////////////////////////////
Используемые на уроке средства ИКТ:
 ПК учащихся. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Электронное приложение к учебнику:
Презентация: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 «Кривая Гильберта». //////////////////////////////////////////////////////////////////////////////////////////////////////////
Тип урока: Комбинированный.
Этапы урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////
I. Организационный момент. //////////////////////////////////////////////////////////////////////////////////////////////////////////
II. Сообщение темы и постановка цели урока.
III. Изучение нового материала. //////////////////////////////////////////////////////////////////////////////////////////////////////////
IV. Практическая работа за компьютером.
V. Задание на дом. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Особенности изложения содержания темы урока:
Данная тема дается для самостоятельного изучения.
Задание на дом: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Просмотреть примеры рекурсивных алгоритмов. Записи в тетрадях.
70
Урок 8. Рекурсивные алгоритмы в заданиях к ЕГЭ.
Цели урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Образовательные (обучающие): закрепить знания учащихся по теме «Организация рекурсивных алгоритмов»; подготовить учащихся к решению заданий,
на нахождение рекурсии представленных в ЕГЭ. //////////////////////////////////////////////////////////////////////////////////
Развивающие: продолжить развивать навыки
владения ИКТ – техноло-
гией, логическое мышление. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса.
Планируемые результаты: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Предметные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 знание основных понятий: рекурсия, рекурсивный алгоритм, рекуррентная
формула, стек, глубина рекурсии, прямая рекурсия, косвенная рекурсия;
 знание основных форм рекурсивных алгоритмов;
 умение анализировать рекурсивные алгоритмы проводить их трассировку. Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов. //////////////////////////////////////////////////////////////////////////////////////////////////////////
 умение выполнять задания по решению рекурсивных алгоритмов в ЕГЭ.
Используемые на уроке средства ИКТ:
 персональный компьютер (ПК) учителя, мультимедийный проектор,
экран; ПК учащихся. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Электронное приложение к учебнику:
Презентация: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 «Рекурсивные алгоритмы в заданиях к ЕГЭ».
Тип урока: Урок обобщения и систематизации знаний.
Этапы урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////
I. Организационный момент. //////////////////////////////////////////////////////////////////////////////////////////////////////////
II. Актуализация знаний и фиксирование затруднений.
III. Целеполагание. //////////////////////////////////////////////////////////////////////////////////////////////////////////
71
IV. Обобщение и систематизация знаний.
V. Итоги урока и оценка знаний учащихся.
VI. Задание на дом. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Особенности изложения содержания темы урока:
В начале урока учащимся предоставляется возможность решить кроссворд.
Входящие в него вопросы затрагивают основные понятия, которые изучались
раннее. Данное задание позволит учащимся вспомнить изученный материал. Так
же кроссворд используется как средство мотивации. /////////////////////////////////////////////////////////////////////////
Далее следует объяснить принцип решения заданий, которые даются в ЕГЭ.
Объяснение введется на основе примера, с демонстрацией. Приводятся примеры
нескольких заданий, учащиеся совместно с учителем решают ряд заданий, после
чего предлагаются задания для самостоятельного решения.
72
Урок 9. Контрольная работа «Рекурсивные методы программирования». ////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////
Цели урока:
Образовательные (обучающие): проверить знания учащихся по теме «Рекурсивные методы программирования», проверить навыки решения рекурсивных
алгоритмов в ЯП Pascal. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Развивающие: продолжить развивать навыки
владения ИКТ – техноло-
гией, логическое мышление, навыки работы с ЯП Pascal.
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса.
Планируемые результаты: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Предметные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 знание основных понятий: рекурсия, рекурсивный алгоритм, рекуррентная
формула, стек, глубина рекурсии, прямая рекурсия, косвенная рекурсия;
 знание основных форм рекурсивных алгоритмов;
 умение анализировать рекурсивные алгоритмы проводить их трассировку. Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Используемые на уроке средства ИКТ:
 персональный компьютер (ПК) учителя, мультимедийный проектор,
экран; ПК учащихся. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Электронное приложение к учебнику:
Электронный тест: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 «Рекурсивные методы программирования».
Тип урока:
Урок контроля и оценки знаний.
Этапы урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////
I. Организационный момент. //////////////////////////////////////////////////////////////////////////////////////////////////////////
II. Сообщение темы и постановка цели урока
III. Контроль и оценка знаний. //////////////////////////////////////////////////////////////////////////////////////////////////////////
73
IV. Итоги урока и оценка знаний учащихся.
V. Задание на дом. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Особенности изложения содержания темы урока:
Выполнение контрольной работы делится на два этапа. Первый – проведение электронного тестирования. Второй – решение задач за компьютером.
Перед тем как раздать задания, учитель проводит инструктаж по технике
безопасности при работе за компьютером. Далее делит класс на два варианта.
Учащиеся рассаживаются за компьютеры. Учитель раздает задания и проводит
вводный инструктаж по выполнению контрольной работы. Учителю следует
предварительно сбросить материал контрольной работы на компьютеры.
За работу выставляются две оценки: //////////////////////////////////////////////////////////////////////////////////////////////////////////
за электронный тест(теоретические знания); ////////////////////////////////////////////////////////////////////////////
за правильность решения задач (практические навыки).
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////////
Пример теоретического занятия.
Тема урока: Рекурсивные алгоритмы в заданиях к ЕГЭ.
Цели урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Образовательные (обучающие): закрепить знания учащихся по теме
«Организация рекурсивных алгоритмов»; подготовить учащихся к решению заданий, на нахождение рекурсии представленных в ЕГЭ.
Развивающие: продолжить развивать навыки
владения ИКТ – техноло-
гией, логическое мышление. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса.
Планируемые результаты: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Личностные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 проявлять положительное отношение к урокам информатики, интерес к
способам решения новых учебных задач, понимать причины успеха или неуспеха
в своей учебной деятельности; //////////////////////////////////////////////////////////////////////////////////////////////////////////
74
 формировать готовность к самообразованию и самовоспитанию;
 устраивать эффективные групповые обсуждения и обеспечивать обмен
знаниями между членами группы для принятия совместных эффективных решений. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Метапредметные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Познавательные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 уметь оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
 развивать
мотивы
и
интересы
своей
познавательной
сти умение создавать, применять и преобразовывать знаки и символы.
Коммуникативные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 уметь оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью.
Регулятивные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 развитие навыков планирования деятельности: определение последовательности промежуточных целей с учетом конечного результата, прогнозирование результата своей деятельности; //////////////////////////////////////////////////////////////////////////////////////////////////////////
 оценивать правильность выполнения действия на уровне адекватной ретроспективной оценки. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Предметные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 знание основных понятий: рекурсия, рекурсивный алгоритм, рекуррентная
формула, стек, глубина рекурсии, прямая рекурсия, косвенная рекурсия;
 знание основных форм рекурсивных алгоритмов;
 умение анализировать рекурсивные алгоритмы проводить их трассировку. Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов. //////////////////////////////////////////////////////////////////////////////////////////////////////////
 умение выполнять задания по решению рекурсивных алгоритмов в ЕГЭ.
75
Оборудование: ПО, презентация. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Тип урока: Урок обобщения и систематизации.
Ход урока
I. Организационный момент. //////////////////////////////////////////////////////////////////////////////////////////////////////////
II. Актуализация знаний и фиксирование затруднений.
1. Решение кроссворда «Рекурсия». //////////////////////////////////////////////////////////////////////////////////////////////////////////
https://learningapps.org/watch?v=pvygevgpn18
Ответ: 1. Рекурсия. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Ответ: 2. Подпрограмма. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Ответ: 3. Условие.
76
Ответ: 4. Спуск. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Ответ: 5. Возврат.
Ответ: 6. Глубина. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Ответ: 7. Прямая. //////////////////////////////////////////////////////////////////////////////////////////////////////////
77
Ответ: 8. Косвенная. //////////////////////////////////////////////////////////////////////////////////////////////////////////
III. Целеполагание. //////////////////////////////////////////////////////////////////////////////////////////////////////////
- В заданиях предлагаемых в ЕГЭ также встречаются, задачи на умение использовать рекурсивные алгоритмы. Процент выполнение задания с рекурсией
составляет примерно всего 13,2%. Владение навыками решения таких задач является немаловажной проблемой. (Слайд 1) //////////////////////////////////////////////////////////////////////////////////////////////////////////
IV. Обобщение и систематизация знаний.
Задачи на рекурсию представлены в ЕГЭ заданием №11.
Способ решения таких заданий: последовательное выполнение операций
от начального определения до определения с введенным в алгоритм значением.
На слайдах подобраны задания из ЕГЭ. Сейчас мы рассмотрим их.(2-12).
78
Вот так выглядят задания на бланках ЕГЭ. ///////////////////////////////////////////////////////////////////////////////////////////
Ниже на пяти языках программирования записан рекурсивный алгоритм
F.(Слайд 13) //////////////////////////////////////////////////////////////////////////////////////////////////////////
Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)? //////////////////////////////////////////////////////////////////////////////////////////////////////////
Пояснение.
Первым действием процедура F(1) выведет число 1. Далее процедура F(1)
вызовет процедуру F(n + 1), в результате выполнения которой на экране появится
число n + 1 = 2. Процедура F(2) вызовет процедуру F(3), которая выведет на экран
число 3 и вызовет процедуру F(4), которая выведет на экран число 4 и вызовет
F(5), которая выведет на экран число 5. //////////////////////////////////////////////////////////////////////////////////////////////////////////
79
После этого управление вернётся к процедуре F(4), которая начнёт выполнять следующий шаг своего алгоритма, т. Е. Обратиться к процедуре F(n + 3) =
F(7). Процедура F(7) выведет на экран число 7. Далее управление вернётся к процедуре F(3). Рассуждая аналогично приходим к выводу, что процедура F(3) дополнительно выведет на экран число 6, процедура F(2) — 5. Последним действием
процедуры F(1) будет вызов процедуры F(n + 3) = F(4), которая выведет на экран
числа 4, 5, 7.
Таким образом, на экране будут числа 1, 2, 3, 4, 5, 7, 6, 5, 4, 5, 7. Их сумма
равна 49. ////////////////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////
О т ве т: 49.
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
(Слайд 14) ////////////////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(5)? ////////////////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////
Пояснение. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Значение, вычисленное алгоритмом при вызове F(5) равно:
F(5)= F(4) + F(3) = F(3) + F(2) + F(2) + F(1) = F(2) + F(1) +1 + 1 + 1 = 5.
Мы рассмотрели примеры рекурсивных алгоритмов. Сейчас вы сами попробуете решить несколько заданий.(15-21) //////////////////////////////////////////////////////////////////////////////////////////////////////////
80
V. Итоги урока и оценка знаний учащихся.
Фронтальный опрос(слайд 22) //////////////////////////////////////////////////////////////////////////////////////////////////////////
1. Что представляет собой рекурсия? //////////////////////////////////////////////////////////////////////////////////////////////////////////
2. Можно ли арифметическую и геометрическую прогрессии назвать
рекуррентными последовательностями?
3. Как описать рекурсивный алгоритм в Pascal?
4. Приведите примеры рекурсивных алгоритмов?
5. Рекурсивная последовательность это…?
6. Рекуррентная формула это …? //////////////////////////////////////////////////////////////////////////////////////////////////////////
7. Рекурсивная подпрограмма (функция, процедура) это …?
VI. Задание на дом. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Записи в тетрадях. Подготовиться к контрольной работе.////////////////////////////////////////////
81
Пример практического занятия. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Технологическая карта урока
Предмет: Информатика и ИКТ //////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Класс: 11.
Тема урока: Лабораторная работа: «Рекурсивные методы программирования» //////////////////////////////////////////////////////////////////////////////////////////////////////////
Цели урока:
Обучающие: сформировать/закрепить навыки создания рекурсивных подпрограмм; вспомнить алгоритм создания подпрограмм в языке программирования Pascal.
Развивающие:
 Развивать способность учащихся анализировать информацию; //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Развивать образное, критическое мышление; ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Развитие системного мышления. ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
Воспитательные: способствовать воспитанию интереса к своей будущей профессии, проявлению к ней устойчивого интереса.
Предполагаемые результаты обучения: ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
Предметные: ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Сформировать представление о рекурсивных методах программирования. //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Умение создавать рекурсивные алгоритмы в ЯП Pascal. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Метапредметные: ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Закрепить умение сравнивать, анализировать, делать выводы о восприятии окружающих нас объектов;
 Иметь представление о подходах к поиску информации; //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Применение рекурсивных алгоритмов для решения математических задач. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Личностные: ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Стимулирование поиска вариантов на основе имеющихся знаний; //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Формирование умения наблюдать, анализировать, сравнивать, делать выводы; //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Осуществление контроля и самоконтроля; ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Развитие находчивости, умения преодолевать трудности для достижения намеченной цели. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Используемые педагогические технологии, методы и приемы: развивающее обучение, личностно-ориентированные технологии, активное взаимодействие ученика и учителя. ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
Тип урока: лабораторная работа. ////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
Необходимое оборудование проектор, карточки с заданиями, презентация к уроку. //////////////////////////////////////////////////////////////////////////////////////////////////////////
82
СТРУКТУРА И ХОД УРОКА
№
Этап урока
Деятельность учителя
Деятельность ученика
1
2
3
4
1
Приветствует учащихся. Проверяет готовПриветствуют учителя.
Организационный
ность к уроку
Готовят рабочие места к
момент
уроку
2 Актуализация знаний
1. Задает вопросы по раннее изучен- 1.Отвечают на вопросы
ному
материалу.(Слайд
1,2) учителя.
2. Характеризуют отношение к результату своей работы.
3. Отмечают при необходимости непонятные
моменты.
Формируемые УУД
5
Регулятивные УУД: контроль знаний;
оценка качества знаний
2.
3
Постановка цели
урока
Поделить класс на два варианта. Раздать Учащиеся читают текст
карточки с заданиями.
заданий.
Формулирует тему и цели урока.
Тема: Лабораторная работа: «Рекурсивные
методы программирования»(Слайд 3)
Познавательные УУД: поиск и выделение необходимой информации;
Регулятивные УУД: целеполагание
Коммуникативные УУД: планирование учебного сотрудничества с учителем; умение полно и с точностью выражать свои мысли
83
4
Цель нашего урока: закрепить на практике
знания о методах рекурсивного программирования.
Практическая работа1. Проводит вводный инструктаж:
1. а) формулируют правиза компьютером
а)повторение правил техники безопасности ла ТБ.
при работе за компьютером.(Слайд 4, 5, 6)
б) садятся за компьютеры, слушают учителя,
задают вопросы если
возникли трудности с
пониманием условия
задачи.
2. Выполняют лабораторную работу. Если
возникают трудности в
ходе выполнения практикума, задают вопросы
учителю.
Познавательные УУД:
Поиск и выделение необходимой информации; структурирование знаний;
смысловое чтение; определение основной и второстепенной информации;
анализ
Коммуникативные УУД: планирование учебного сотрудничества со
сверстниками, управление поведением
партнера; умение с точностью выражать свои мысли
Регулятивные УУД: контроль и коррекция
Личностные УУД: нравственноэтическая ориентация, ориентация в
межличностных ролях.
84
б)разбирает задания по вариантам
Вариант 1.
Задание 1. Расчет суммы первых N натуральных чисел 2
Вычисление суммы 1+2+3+…+N разрешено определить следующим образом:
Sum(N) =
еслиN  0, тоSum  0


еслиN  0, тоSum  N  Sum( N  1)
Задание 2. Найдите наибольший общий делитель двух натуральных чисел.
*Задание 3. Нахождения суммы n членов
арифметической прогрессии, заданной значениями первого члена прогрессии а и разности d.
Лабораторная работа: «Рекурсивные методы программирования».
Вариант 2.
Задание 1. Расчет n-члена арифметической
прогрессии, заданной значением первого
члена a1 и разностью d.4
Вычисление n-члена арифметической про-
85
грессии разрешено определить следующим
образом:
 еслиN  1, тоan  a1
An = 
еслиN  1, тоan  an 1  d
Задание 2. Возведите число a в целую
степень n. 6
*Задание 3. Нахождения суммы n членов
арифметической прогрессии, заданной значениями первого члена прогрессии а и разности d.
В)проводит текущий инструктаж
Оказывает помощь учащимся, при возникновении трудностей непосредственно в ходе выполнения работы.
(Слайд 7)
5
Динамическая пауза
Предлагает выполнить упражнения для
глаз.(Слайд 9)
Выполняют гимнастику
для глаз
Личностные УУД: умение соотносить
поступки и события с принятыми этическими принципами
Регулятивные УУД: саморегуляция
86
6
7
8
Контроль за результатом учебной деятельности школьников
1. Проверяются работы.
2.Учащимся выставляются оценки.
1.Организует рефлексию собственной деятельности учащихся на уроке, предлагая
Рефлексия деятельзакончить предложения:
ности
1) На уроке я успел сделать …
2) В результате я узнал и научился …
1. Я не понял, у меня не получилось …
Выводит домашнее задание на слайд и
Запись домашнего
комментирует.
задания.
1. Если у учителя возникли вопросы по выполнению работы, дают
на них ответы.
Оценивают свою деятельность, заканчивая
предложения.
Записывают домашнее
задание «Подготовиться
к контрольной работе»
Личностные УУД: ориентация в межличностных отношениях; знание моральных норм и умение выделить нравственный аспект поведения.
Регулятивные УУД: планирование;
контроль и коррекция; оценка результатов работы; саморегуляция
Познавательные УУД: поиск и выделение необходимой информации;
структурирование информации; смысловое чтение; определение основной и
второстепенной информации; моделирование, преобразование модели; анализ; выбор критериев для сравнения
Коммуникативные УУД: планирование учебного сотрудничества со
сверстниками; управление поведением
партнера
Личностные УУД: личностное самоопределение
Регулятивные УУД: оценка результатов своей работы
Познавательные УУД: рефлексия результатов деятельности
Регулятивные УУД: прогнозирование
87
ЗАКЛЮЧЕНИЕ/////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////
В ходе выполнения выпускной квалификационной работы была достигнута
поставленная цель исследования, решены задачи.
Изучена и проанализирована методическая литература по теме исследования. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Раскрыты особенности профильных курсов по информатике на базовом и
углубленном уровнях обучения. ////////////////////////////////////////////////////////////////////////////////////////////////
Рассмотрены теоретические основы преподавания темы «Организация рекурсивных алгоритмов».
Проанализировано программно-методическое обеспечение темы «Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi» в
профильном курсе информатики в школе, рассмотрены и разобраны примеры задач на рекурсию. Разобраны задания предлагаемые учащимся в ЕГЭ.
Разработаны конспекты для профильного курса по информатике на тему
«Организация рекурсивных алгоритмов в языках программирования Pascal и Delphi». ////////////////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////////////////////////
Разработан электронный учебник «Организация рекурсивных алгоритмов в
языках программирования Pascal и Delphi». ///////////////////////////////////////////////////////////////////////////////////////////////////////
Рассматривая понятие рекурсии, нужно сказать что, оно отражает черту абстрактного мышления, проявляющуюся в самых различных областях, не только в
информатике, но также
в математике, синтаксическом анализе и трансляции,
древовидной сортировке и обработке данных с динамической структурой, шахматных задачах и т.д.
Именно в задачах такого рода лучше применять рекурсивные алгоритмы,
так как они, избавляют от необходимости последовательного описания процессов,
к тому же, практически все действующие языки программирования поддерживают рекурсию. Изучение данной темы в профильном курсе информатики позволяет
не только подготовить учащихся к сдаче ЕГЭ, но и возможно поможет будущим
88
выпускникам определиться с выбором профессии. Важно, чтобы изучению данной темы отводилось достойное место в образовательном процессе.
89
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
1. Стандарт
ке
среднего
(базовый
(полного)
уровень)
общего
образования
[Электронный
по информати-
ресурс].
URL:
http://window.edu.ru/resource/282/39282/files/35.pdf (дата обращения 20.01.2016).
2. Стандарт
ке
среднего
(профильный
(полного)
общего
образования
уровень)[Электронный
по информати-
ресурс].
URL:
http://window.edu.ru/resource/283/39283(дата обращения: 20.01.2016).
3. Лапчик М.П. и др. Методика преподавания информатики: Учеб. Пособие
для студ. Пед. Вузов / М.П. Лапчик, И.Г. Семакин, Е.К. Хеннер; Под общей ред.
М.П. Лапчика. – М.: Издательский центр Академия», 2001. –с.
4. Семакин И.Г. Программа курса «Информатика и ИКТ» для 10-11 классов
ФГОС
(углублённый
уровень)[Электронный
ресурс].
http://metodist.lbz.ru/authors/informatika/2/files/pk10-11ufgos.doc(дата
URL:
обращения:
09.02.2016).
5. Рекурсия.
Материал
сайта
Академик.
URL:
http://dic.academic.ru/dic.nsf/ruwiki/6791.
6. В.Г.Абрамов., Н.П.Трифонов., Г.Н.Трифонова. Введение в язык Пас-каль.
– М.: КНОРУС, 2011. – 384 с.
7. В.Н.Пильщиков. Язык Паскаль: упражнения и задачи. – М.: Научный
мир, 2003. – 224 с.
8. Н.Вирт. Алгоритмы и структуры данных.: Пер. с англ. – 2-е изд., испр. –
СПб.: Невский Диалект, 2001. – 352 с.: ил.
9. Златопольский Д.М. Замечательные кривые /. - -М.: Чистые пруды, 2008. 32 с. (Библиотека "Первое сентября", серия "Информатика", Вып.23).
10. Павловский А.И., Пупцев А.Е., Гращенко П.Л. Информатика: Учеб. пособие для 10-го кл. с углубл. изучением информатики общеобразоват. шк. с рус.
яз. обучения. - Мн.: Нар. асвета, 2000. - 223 с.: ил.
11. Фестиваль педагогических идей "Открытый урок". Изучение темы "Рекурсивные
графические
алгоритмы".
http://festival.1september.ru/articles/420024/
Лусникова
Е.С.
90
12. Уроки, справочники, рефераты. Рекурсия в Паскале. Батракова Л.В.
http://do. gendocs.ru/docs/index-282821.html
13. Основы программирования на PascalABC. Рекурсия. http://pascalabc2012.
narod2.ru/Rekyrsia. htm
14. Программирование.
Рекурсия
Pascal-Паскаль.
http://www.pascal.
helpov.net/index/recursion_pascal_programming
15. Чеховская
школа
программирования.
Рекурсия.
http://progshkola.ru/tag/rekursiya
16. Использование
рекурсии
в
графике.
http://www.web-pascal.
narod.ru/stat/recurs. htm
17. Виртуальный учебник TurboPascal 7.0. http://dezavarzin. narod.ru/4.6 htm
18. Рекурсия для чайников. http://botinok. co. il/node/29842
19. Рекурсия и рекурсивные алгоритмы. Персональная страничка Диканева
Т.В. http://www.tvd-home.ru/recursion
20. Антология сетевого фольклора. Рекурсия. http://www.netlore.ru/recursion
21. https://statgrad.org/
22. studbooks.net
23. http://www.ict.edu.ru/ft/004336/25.pdf
24. https://infourok.ru/statya-na-temu-sovremennaya-sistema-obrazovaniya-v-rf1492483.html
25. Информатика. УМК для старшей школы [Электронный ресурс] : 10-11
классы. Углубленный уровень. Методическое пособие для учителя / Авторсоставитель: М. Н. Бородин.-Эл. изд. -М. : БИНОМ. Лаборатория знаний, 2013. 197 с. : ил.
26. Информатика. УМК для старшей школы [Электронный ресурс] :
10-11
классы. Углубленный уровень. Методическое пособие для учителя / Авторысоставители: О. А. Полежаева, М. С. Цветкова.- Эл. изд.-М. : БИНОМ. Лаборатория знаний, 2013. -114 с. : ил.
27. Организация профильного обучения информатике в условиях внедрения
ФГОС// Современные проблемы физико-математических наук. Материалы II
91
Международной научно-практической конференции, 24-27 ноября 2016 г./ под
общ. ред. Т.Н. Можаровой.- Орел: ОГУ, 2016 - 375 с.
/////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
92
ПРИЛОЖЕНИЕ 1.
ПРИЛОЖЕНИЕ 1. КОНСПЕКТ УРОКА НА ТЕМУ «РЕКУРСИВНЫЕ
МЕТОДЫ ПРОГРАММИРОВАНИЯ. РЕКУРСИВНЫЕ ПОДПРОГРАММЫ»
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
Тема урока: Рекурсивные методы программирования. Рекурсивные подпрограммы. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Цели урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Образовательные (обучающие): познакомить учащихся с понятием рекурсия, рекурсивный алгоритм, разобрать примеры применения рекурсивных алгоритмов. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Развивающие: продолжить развивать навыки
владения ИКТ – техноло-
гией, логическое мышление, навыки работы с ЯП Pascal.
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса.
Планируемые результаты: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Личностные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 проявлять
положительное отношение к урокам информатики, интерес к
способам решения новых учебных задач, понимать причины успеха или неуспеха
в своей учебной деятельности; //////////////////////////////////////////////////////////////////////////////////////////////////////////
 формировать
 устраивать
готовность к самообразованию и самовоспитанию;
эффективные групповые обсуждения и обеспечивать обмен зна-
ниями между членами группы для принятия совместных эффективных решений.
Метапредметные:
Познавательные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 уметь
оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
 развивать
мотивы и интересы своей познавательной деятельности умение
создавать, применять и преобразовывать знаки и символы;
Коммуникативные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
93

ПРИЛОЖЕНИЕ 1.(ПРОДОЛЖЕНИЕ)
уметь оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
Регулятивные: //////////////////////////////////////////////////////////////////////////////////////////////////////////

развитие навыков планирования деятельности: определение последователь-
ности промежуточных целей с учетом конечного результата, прогнозирование результата своей деятельности; //////////////////////////////////////////////////////////////////////////////////////////////////////////

оценивать правильность выполнения действия на уровне адекватной ретро-
спективной оценки.
Предметные: //////////////////////////////////////////////////////////////////////////////////////////////////////////
 знание основных понятий: рекурсия, рекурсивный алгоритм, рекуррентная
формула, стек, глубина рекурсии, прямая рекурсия, косвенная рекурсия;
 знание основных форм рекурсивных алгоритмов;
 умение анализировать рекурсивные алгоритмы проводить их трассировку.
Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов.
Оборудование: ПО, презентация. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Тип урока: урок изучения нового материала.
Ход урока
I. Организационный момент (мотивационная беседа)
II. Повторение изученного (создание ситуации успеха)
Учитель: что такое подпрограмма? //////////////////////////////////////////////////////////////////////////////////////////////////////////
Ученик: подпрограмма
- это специальным образом оформленный алгоритм,
который может многократно использоваться при решении более общей задачи.
Учитель: Какие виды подпрограмм существует в языке Паскаль?
Ученик:
В языке Паскаль существует
два вида подпрограмм: процедура
(PROCEDURE) и функция ( FUNCTION ). //////////////////////////////////////////////////////////////////////////////////////////////////////////
Учитель: что такое формальные и фактические параметры?
Ученик: Формальные - условные обозначения в описании процедуры - описыва-
94
ПРИЛОЖЕНИЕ 1.(ПРОДОЛЖЕНИЕ)
ются в ее заголовке. Фактические - перечисляются при вызове процедуры и с ними требуется выполнить процедуру.
Учитель: В каком случае удобно использовать в программе процедуру?
Ученик: Процедуры используются в случаях, когда в подпрограмме необходимо
получить несколько результатов. (слайд 1) //////////////////////////////////////////////////////////////////////////////////////////////////////////
Учитель:
В каком случае удобно использовать в программе функцию? Ученик:
Когда в подпрограмме необходимо получить единственный результат. Учитель:
Как происходит вызов подпрограммы? //////////////////////////////////////////////////////////////////////////////////////////////////////////
Ученик: Вызов подпрограммы происходит при каждом употреблении ее имени в
основной программе. При вызове подпрограммы устанавливается взаимно однозначное соответствие между фактическими и формальными параметрами, затем
начинают выполняться команды, заданные в ней. После выполнения подпрограммы управление передается следующему оператору основной программы. (слайд 2)
Учитель:
Процедура или функция может содержать вызов других
или функций. А может ли процедура вызвать саму себя?
процедур
95
ПРИЛОЖЕНИЕ 1.(ПРОДОЛЖЕНИЕ)
Ученик: Возможные ответы учащихся: //////////////////////////////////////////////////////////////////////////////////////////////////////////
-нет, это замкнутый круг, это приведет к зацикливанию программы.
-да, при правильной организации вызова. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Учитель: Это возможно. Никакого парадокса здесь нет – компьютер лишь последовательно выполняет встретившиеся ему в программе команды и, если встречается вызов процедуры, просто начинает выполнять эту процедуру. Без разницы,
какая процедура дала команду это делать. Собственно в этом и заключается сущность рекурсии. //////////////////////////////////////////////////////////////////////////////////////////////////////////
III. Целеполагание //////////////////////////////////////////////////////////////////////////////////////////////////////////
Рекурсией называется ситуация, когда подпрограмма вызывает сама себя.
Тема урока: " Рекурсивные методы программирования. Рекурсивные подпрограммы". (слайд 3) //////////////////////////////////////////////////////////////////////////////////////////////////////////
Исходя из этого, что это первое знакомство с рекурсией, сформулируйте
цель нашего урока.
Возможные ответы учащихся: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Продолжить изучение подпрограмм. Узнать, что такое рекурсия, какими
свойствами она обладает, как выполняется рекурсивный алгоритм.
Цели на слайде: (слайд 4)

Познакомится с понятием
рекурсивного объекта и рекурсивного
определения.

Познакомиться с рекурсивными алгоритмами.

Рассмотреть программы с использованием рекурсивных подпрограмм.
96
ПРИЛОЖЕНИЕ 1.(ПРОДОЛЖЕНИЕ)
IV. Изучение нового материала.
Что такое рекурсивный объект и каковы его свойства?
В жизни на не раз приходилось сталкиваться с рекурсией. (слайд 5)

Мифология //////////////////////////////////////////////////////////////////////////////////////////////////////////
Уроборос – змей, кусающий свой собственный хвост. Это древний символ бесконечности Вселенной и времени, круговорота жизни, отождествляемых с рекурсией. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Классическим примером бесконечной рекурсии являются два поставленные друг
напротив друга зеркала: в них образуются два коридора из затухающих отражений зеркал. //////////////////////////////////////////////////////////////////////////////////////////////////////////

Рекурсия вокруг нас… //////////////////////////////////////////////////////////////////////////////////////////////////////////
Пример: Русские матрешки //////////////////////////////////////////////////////////////////////////////////////////////////////////

Русском фольклоре //////////////////////////////////////////////////////////////////////////////////////////////////////////

Прием рекурсии в литературе.(слайд 6, 7, 8, 9)
97
ПРИЛОЖЕНИЕ 1.(ПРОДОЛЖЕНИЕ)
Несколько рассказов Станислава Лема посвящены (возможным) казусам
при бесконечной рекурсии. Рассказ из «Кибериады» о разумной машине, которая
обладала достаточным умом и ленью, чтобы для решения поставленной задачи
построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание
ей). //////////////////////////////////////////////////////////////////////////////////////////////////////////
Н.В. Гоголь в повести «Портрет» описывает сон художника Черткова, который, как далее выясняется, оказывается сном третьего уровня рекурсии.
Проснувшись от этого сна (первый раз), Чертков попадает на второй уровень рекурсии – во второй сон. Проснувшись от второго сна, он попадает в первый сон,
от которого тоже придется проснуться. //////////////////////////////////////////////////////////////////////////////////////////////////////////

Прием рекурсии в живописи.(слайд 10)
98
ПРИЛОЖЕНИЕ 1.(ПРОДОЛЖЕНИЕ)
Гравюра голландского художника Мориса Эшера «Рисующие руки» - одна из
лучших иллюстраций понятия рекурсии. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Существует специальный раздел графики – фрактальная графика. В основе которой рекурсивное изображение одного и того же узора в самом себе.

Прием рекурсии в архитектуре.(слайд 11)
Сооружения с элементами фрактала "Треугольник Серпинского" - это Эйфелева
Башня в Париже; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Исторический музей, Москва; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Фрактальность современных архитектурных форм.
Рекурсия и жизнь. (слайд 12, 13,14)
99
ПРИЛОЖЕНИЕ 1.(ПРОДОЛЖЕНИЕ)

Рекурсия в математике(слайд 15) //////////////////////////////////////////////////////////////////////////////////////////////////////////
Идеи рекурсии известны людям издавна. Рекурсивные определения как мощный
аналитический аппарат используются во многих областях науки, особенно в математике.
1) Арифметическая прогрессия:
а)а1=а0; //////////////////////////////////////////////////////////////////////////////////////////////////////////
б) аn=аn-1+d. //////////////////////////////////////////////////////////////////////////////////////////////////////////
2) Геометрическая прогрессия:
а) а1=а0;
б) аn=а n-1*q.
3)(слайд 16)
100
ПРИЛОЖЕНИЕ 1.(ПРОДОЛЖЕНИЕ)
Факториал an=n! n!=1*2*3*4*5*б*...*n. а)а1=1;
б) аn=n*аn-1.
4) Числа Фибоначчи. x1=x2=1
xn=xn-1+xn-2 при n > 2
Каждый элемент ряда Фибоначчи является суммой двух предшествующих элементов, т.е. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,… //////////////////////////////////////////////////////////////////////////////////////////////////////////
Мы рассмотрели примеры рекурсивных объектов. Рекурсивным называется
любой объект, который частично определяется через себя. Т.е. объект определяется в терминах более простого случая этого же объекта.
Свойства рекурсивных объектов.(слайд 17)
 Простота построения; //////////////////////////////////////////////////////////////////////////////////////////////////////////
 Несхожесть конечного результата с начальными данными;
 Внутреннее самоподобие. //////////////////////////////////////////////////////////////////////////////////////////////////////////

Рекурсия в программировании (слайд18)
Рекурсия — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма вызывает сама себя.
В языке программирования Pascal рекурсивностью могут обладать как функции,
так и процедуры. //////////////////////////////////////////////////////////////////////////////////////////////////////////
101
ПРИЛОЖЕНИЕ 1.(ПРОДОЛЖЕНИЕ)
Рекурсивная функция (или процедура) обязательно должна содержать в себе
условие окончания рекурсивности или граничное условие, чтобы не вызвать
зацикливания программы. Потому что бесконечный вызов рекурсии приводит к
переполнению стека и возникновению ошибки времени исполнения.
Большая часть всех шуток о рекурсии касается бесконечной рекурсии, в
которой нет условия выхода. «Чтобы понять рекурсию, нужно сначала понять
рекурсию». //////////////////////////////////////////////////////////////////////////////////////////////////////////
(слайд 19)
Выполнение рекурсивного алгоритма можно представить следующим образом: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Каждый рекурсивный вызов процедуры F порождает в памяти компьютера новую
копию этой процедуры и запускает ее на выполнение со своими значениями
входных параметров. //////////////////////////////////////////////////////////////////////////////////////////////////////////
После того как процедура F завершила работу, выполнение программы продолжается со следующего оператора после вызова F.
Существуют три разных формы рекурсивных рекурсивных подпрограмм(слайд
20) //////////////////////////////////////////////////////////////////////////////////////////////////////////
102
рекурсивный
ПРИЛОЖЕНИЕ 1.(ПРОДОЛЖЕНИЕ)
рекурсивный спуск и рекурсивный
возврат
возврат
Begin
Begin
Begin
If Условия
операторы;
операторы;
рекурсивный спуск
then Рекурсия; опера- If
торы;
еnd;
Условия
then
еnd;
If Условия
Рекурсия; then Рекурсия; операторы;
еnd;
Как уже говорилось выше, в языке программирования Pascal рекурсивностью могут обладать как функции, так и процедуры, рассмотрим примеры таких
подпрограмм.(слайд 21) //////////////////////////////////////////////////////////////////////////////////////////////////////////
Пример рекурсивной процедуры: Пример рекурсивной функции:
procedure Rec(a: integer); begin
function Rec(n: integer): integer; begin
if a>0 then Rec(a-1); writeln(a);
if n>0 then Rec(n-1);
end;
writeln(n); end;
Типичная конструкция рекурсивной процедуры имеет вид:
Procedure Rec (t: Integer) ; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Begin //////////////////////////////////////////////////////////////////////////////////////////////////////////
действия на входе в рекурсию; //////////////////////////////////////////////////////////////////////////////////////////////////////////
103
ПРИЛОЖЕНИЕ 1.(ПРОДОЛЖЕНИЕ)
If проверка условия
//////////////////////////////////////////////////////////////////////////////////////////////////////////
Then Rec (t+1) ; //////////////////////////////////////////////////////////////////////////////////////////////////////////
действия на выходе из рекурсии; End; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Пример рекурсивной процедуры: //////////////////////////////////////////////////////////////////////////////////////////////////////////
Program n1; uses crt; //////////////////////////////////////////////////////////////////////////////////////////////////////////
procedure Rec(i: integer); begin //////////////////////////////////////////////////////////////////////////////////////////////////////////
if i>1 then Rec(i-1); writeln(i); //////////////////////////////////////////////////////////////////////////////////////////////////////////
end; begin clrscr; Rec(5); //////////////////////////////////////////////////////////////////////////////////////////////////////////
end. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Общая форма записи(слайд 22, 23)
Procedure Rec(<список формальных параметров>); Begin
…
If <проверка условия> Then Rec(n-1); //////////////////////////////////////////////////////////////////////////////////////////////////////////
…
End; //////////////////////////////////////////////////////////////////////////////////////////////////////////
Количество одновременно выполняемых процедур называют глубиной рекурсии. //////////////////////////////////////////////////////////////////////////////////////////////////////////
Для вас я подготовил примеры рекурсивных алгоритмов, уже реализованных на языке Паскаль. (показ примеров)
Сейчас Вы попробуете самостоятельно реализовать алгоритм нахождения
факториала.(слайд 24) //////////////////////////////////////////////////////////////////////////////////////////////////////////
V. Практическая работа. //////////////////////////////////////////////////////////////////////////////////////////////////////////
104
ПРИЛОЖЕНИЕ 1.(ПРОДОЛЖЕНИЕ)
1. Инструктаж по правилам ТБ.
2. Выполнение практической работы.
V. Итоги урока и оценка знаний учащихся.
Фронтальный опрос(слайд 25) //////////////////////////////////////////////////////////////////////////////////////////////////////////
1.
Что представляет собой рекурсия?
2.
Можно ли арифметическую и геометрическую прогрессии назвать ре-
куррентными последовательностями?
3.
Как описать рекурсивный алгоритм в Pascal?
4.
Приведите примеры рекурсивных алгоритмов?
5.
Рекурсивная последовательность это…?
6.
Рекуррентная формула это …? //////////////////////////////////////////////////////////////////////////////////////////////////////////
7.
Рекурсивная подпрограмма (функция, процедура) это …?
VI. Задание на дом. //////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////
105
ПРИЛОЖЕНИЕ 2.
ПРИЛОЖЕНИЕ 2. КОНСПЕКТ УРОКА НА ТЕМУ «ЗАДАЧА О ХАНОЙСКОЙ БАШНЕ»//////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// ////////////////////
Класс: 11. ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// //////////////
Тема урока: Задача о Ханойской башне. Числа Фибоначчи.
Цели урока: ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
Образовательные (обучающие): закрепить знания учащихся по теме «Рекурсивные подпрограммы», рассмотреть решение задачи о Ханойской башне.
Развивающие: продолжить развивать навыки
владения ИКТ – технологи-
ей, логическое мышление, навыки работы с ЯП Pascal. ////////////////////////////////////// ///////////////////////
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса. ////////////////////////////////////// ///////////////////////
Планируемые результаты: ////////////////////////////////////// ///////////////////////
Личностные: ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
 проявлять
положительное отношение к урокам информатики, интерес к
способам решения новых учебных задач, понимать причины успеха или неуспеха
в своей учебной деятельности; ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
 формировать
 устраивать
готовность к самообразованию и самовоспитанию;
эффективные групповые обсуждения и обеспечивать обмен зна-
ниями между членами группы для принятия совместных эффективных решений.
Метапредметные: ////////////////////////////////////// ///////////////////////////////////////////////////////////// /////////////////////////////////////////////
Познавательные: ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
 уметь
оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
 развивать
мотивы и интересы своей познавательной деятельности умение
создавать, применять и преобразовывать знаки и символы; ////////////////////////////////////// ///////////////////////
Коммуникативные: ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
106

ПРИЛОЖЕНИЕ 2.(ПРОДОЛЖЕНИЕ)
уметь оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
Регулятивные: ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////

развитие навыков планирования деятельности: определение последователь-
ности промежуточных целей с учетом конечного результата, прогнозирование результата своей деятельности; ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////

оценивать правильность выполнения действия на уровне адекватной ретро-
спективной оценки. ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
Предметные: ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
 знание основных форм рекурсивных алгоритмов; ////////////////////////////////////// ///////////////////////
 умение анализировать рекурсивные алгоритмы проводить их трассировку.
Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов. ////////////////////////////////////// ///////////////////////
 Умение построить рекурсивный алгоритм задачи о Ханойских башнях.
 Умение построить рекурсивный алгоритм нахождения чисел Фибоначчи.
Оборудование: ПО, презентация. ////////////////////////////////////// ///////////////////////
Тип
урока:
комбинированный//////////////////////////////////////
/////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
Ход урока
I. Организационный момент (мотивационная беседа) ////////////////////////////////////// ///////////////////////
II. Повторение изученного (создание ситуации успеха) ////////////////////////////////////// ///////////////////////
(Слайд 1) ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
107
1.
ПРИЛОЖЕНИЕ 2.(ПРОДОЛЖЕНИЕ)
Что представляет собой рекурсия? ////////////////////////////////////// ///////////////////////
2.
Приведите примеры рекурсии из повседневной жизни?
3.
Можно ли арифметическую и геометрическую прогрессии назвать ре-
куррентными последовательностями? ////////////////////////////////////// ///////////////////////
4.
Как описать рекурсивный алгоритм в Pascal? ////////////////////////////////////// ///////////////////////
5.
Приведите примеры рекурсивных алгоритмов? ////////////////////////////////////// ///////////////////////
6.
Рекурсивная последовательность это…?////////////////////////////////////// ///////////////////////
7.
Рекуррентная формула это …?////////////////////////////////////// ///////////////////////
8.
Назовите виды рекурсии? ////////////////////////////////////// ///////////////////////
III. Сообщение темы и постановка цели урока////////////////////////////////////// ///////////////////////
На прошлом уроке вы изучили и рассмотрели рекурсивные алгоритмы. Сегодня мы рассмотрим один из ярких примеров рекурсивного алгоритма «Задачу о
Ханойской башне» и алгоритм вычисляющий n-е число Фибоначчи. Попробуете реализовать эти алгоритмы на компьютере. ////////////////////////////////////// ///////////////////////
IV.
Изучение нового материала////////////////////////////////////// ///////////////////////
Применение рекурсивных методов для решения вычислительных задач не
всегда эффективно. В большинстве случаев для решения той же задачи можно построить оптимальный нерекурсивный алгоритм. В то же время существуют задачи
не вычислительного содержания, решить которые без использования рекурсии
оказывается крайне проблематичным. К числу таких задач относится известная
головоломка под названием «Ханойская башня» . ////////////////////////////////////// ///////////////////////
Легенда(Слайд 3.4) ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
108
ПРИЛОЖЕНИЕ 2.(ПРОДОЛЖЕНИЕ)
(Слайд 5) ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// /////////////////
На площадке (назовем ее А) находится пирамида, составленная из дисков
уменьшающегося от основания пирамиды к ее вершине размера. Эту пирамиду в
том же виде требуется переместить на площадку В . При выполнении работы
необходимо соблюдать следующие ограничения
•
(Слайд 6)
Перекладывать можно только по одному диску, взятому сверху
109
ПРИЛОЖЕНИЕ 2.(ПРОДОЛЖЕНИЕ)
Пирамиды;
•
Класть диск можно только либо на основание площадки, либо
На диск большего размера; ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
•
В качестве дополнительной можно использовать площадку С.
Название «Ханойская башня» связано с легендой, согласно которой в давние времена монахи одного ханойского храма взялись переместить по этим правилам башню, состоящую из 64 дисков. С завершением их работы должен был
наступить конец света. ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
Нетрудно решить эту задачу для двух дисков. Обозначая перемещения диска, например, с площадки А на площадку В так: А = > В, напишем алгоритм для
этого случая(Слайд 7) ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
Попробуйте оценить, сколько лет на это потребуется.
Составим программу, по которой машина рассчитает алгоритм перемещения дисков и выведет его для любого значения п (количества дисков). Пусть на
площадке А находится п дисков. Алгоритм решения задачи будет следующим.
1.
Если п = 0, то ничего не делать. ////////////////////////////////////// ///////////////////////
2.
Если п > О, то: ////////////////////////////////////// ///////////////////////
> Переместить
п - 1 дисков на С через В ;
> Переместить
диск с А на В (А => В ) ; ////////////////////////////////////// ///////////////////////
> Переместить
п - 1 дисков с С на Б через А.(Слайд 8)
110
ПРИЛОЖЕНИЕ 2.(ПРОДОЛЖЕНИЕ)
При выполнении пункта 2 последовательно будем иметь три состояния.
Описание алгоритма имеет явно рекурсивный характер. Перемещение п
дисков описывается через перемещение п - 1 дисков. А где же выход из этой последовательности рекурсивных ссылок? Он в пункте 1, как бы ни показалось
странным его тривиальное содержание. ////////////////////////////////////// ///////////////////////////////////////////////////////////// ////////////
А теперь составим программу на Паскале. В ней имеется рекурсивная процедура Напоу, выполнение которой заканчивается только при я = 0. При обращении к процедуре используются фактические имена площадок, заданные их номерами: 1, 2, 3. Поэтому на выходе цепочка перемещений будет описываться в таком виде(Слайд 9)
//////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
111
ПРИЛОЖЕНИЕ 2.(ПРОДОЛЖЕНИЕ)
Следующая задача интересна не меньше.
С XIII века в математике известна замечательная числовая последовательность,
названная
именем
своего
автора:
числа
Фи-
боначчи.(Слайд 10) ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
Первые два значения числового ряда Фибоначчи равны единице.
Каждое следующее значение равно сумме двух предыдущих. Если
функцию вычисления п -то элемента ряда обозначить как F ib( n ), то ее
математическое определение запишется так(Слайд 11)
Очевидно, что это частично-рекурсивная функция с двумя начальными
(граничными) значениями. На основании данной формулы можно запрограммировать рекурсивную подпрограмму- функцию на Паскале. В следующей программе описана такая функция и с ее помощью вычислены первые 10 чисел Фибоначчи (Слайд12) ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
112
ПРИЛОЖЕНИЕ 2.(ПРОДОЛЖЕНИЕ)
В
результате
выполнения
программы
получим
числовую
после-
довательность первых десяти чисел Фибоначчи:
1 1 2 3 5 8 13 21 34 55 ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
При выполнении этой программы компьютер будет строить два стека, поскольку в определении функции присутствуют два рекурсивных обращения к ней
самой. Вопреки лаконичной простоте текста программы, ее выполнение — достаточно тяжелый процесс для компьютера с точки зрения времени счета и расхода
памяти на построение стека.
Удивительные программы, не правда ли? Попробуйте воспроизвести их на
компьютере. ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
V.
Практическая работа
1.
Повторение правил ТБ работы за компьютером.(Слайд 13)
2.
Практическая работа.
113
ПРИЛОЖЕНИЕ 2.(ПРОДОЛЖЕНИЕ)
Задание 1.
Реализуйте на компьютере программу решения задачи о Ханойской
башне. ////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
VI. Итоги урока и оценка знаний учащихся.
1. Что нового вы узнали на уроке?
2. Сформулируйте идею рекурсивного алгоритма решения задачи о
Ханойской башне.
////////////////////////////////////// ///////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////
//////////////
VII. Задание на дом.
//////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////
///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// ////////////////////////////////// /////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////// ///////////////////////
114
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ 3.
3. КОНСПЕКТ УРОКА НА ТЕМУ «АЛГОРИТМ
БЫСТРОЙ СОРТИРОВКИ»////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Класс: 11. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Тема урока: Алгоритм быстрой сортировки////////////////////////////////////////////////////////////////////////////////
Цели урока: ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Образовательные (обучающие): закрепить знания учащихся по теме «Рекурсивные подпрограммы», рассмотреть алгоритм быстрой сортировки.
Развивающие: продолжить развивать навыки
владения ИКТ – технологи-
ей, логическое мышление, навыки работы с ЯП Pascal. //////////////////////////////////////////////////////////////////////////
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса. ////////////////////////////////////////////////////////////////////////////
Планируемые результаты: ////////////////////////////////////////////////////////////////////////////////
Личностные: ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 проявлять
положительное отношение к урокам информатики, интерес к
способам решения новых учебных задач, понимать причины успеха или неуспеха
в своей учебной деятельности; ////////////////////////////////////////////////////////////////////////////////
 формировать
 устраивать
готовность к самообразованию и самовоспитанию;
эффективные групповые обсуждения и обеспечивать обмен зна-
ниями между членами группы для принятия совместных эффективных решений.
Метапредметные: //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Познавательные:
 уметь
оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
 развивать
мотивы и интересы своей познавательной деятельности умение
создавать, применять и преобразовывать знаки и символы;
Коммуникативные: ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
115

ПРИЛОЖЕНИЕ 3.(ПРОДОЛЖЕНИЕ)
уметь оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
Регулятивные: ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

развитие навыков планирования деятельности: определение последователь-
ности промежуточных целей с учетом конечного результата, прогнозирование результата своей деятельности; ////////////////////////////////////////////////////////////////////////////////

оценивать правильность выполнения действия на уровне адекватной ретро-
спективной оценки. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Предметные: ////////////////////////////////////////////////////////////////////////////////
 знание основных форм рекурсивных алгоритмов;
 умение анализировать рекурсивные алгоритмы проводить их трассировку.
Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов. ////////////////////////////////////////////////////////////////////////////////
 Умение построить алгоритм «Быстрой сортировки».
Оборудование: ПО, презентация. ////////////////////////////////////////////////////////////////////////////////
Тип урока: комбинированный////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Ход урока
I.
Организационный момент. ////////////////////////////////////////////////////////////////////////////////
II.
Проверка домашнего задания////////////////////////////////////////////////////////////////////////////////
1.
Письменный опрос по карточкам////////////////////////////////////////////////////////////////////////////////
Вариант 1.
1.
Дайте определение понятию «Рекуррентная формула».
2.
Напишите рекурсивный вариант подпрограммы-процедуры
нахождения чисел Фибоначчи.
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////
116
ПРИЛОЖЕНИЕ 3.(ПРОДОЛЖЕНИЕ)
Вариант 2.
1.
Дайте определение понятию «Рекурсивная подпрограмма
(функция, процедура». ////////////////////////////////////////////////////////////////////////////////
2.
Напишите рекурсивный вариант нахождения факториала.
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
III.
Сообщение темы и постановка цели урока. /////////////////////////////////////////////////////////////////
IV.
Изучение нового материала. ////////////////////////////////////////////////////////////////////////////////
Сегодня мы рассмотрим оптимальный по времени работы алгоритм, который называется алгоритмом быстрой сортировки. (Слайд 1)
Этот алгоритм был разработан Энтони Хоаром в 1960 году. Покажем, как он
реализуется через рекурсивную процедуру.(Слайд 2)
В алгоритме быстрой сортировки используются три идеи(Слайд 3)
117
ПРИЛОЖЕНИЕ 3.(ПРОДОЛЖЕНИЕ)
1)
разделение сортируемого массива на две части: левую и правую;
2)
взаимное упорядочение двух частей (подмассивов) так, чтобы все зна-
чения элементов левой части не превосходили значений элементов правой части;
3)
рекурсия, при которой подмассив упорядочивается точно таким же
способом, как и весь массив. ////////////////////////////////////////////////////////////////////////////////
(Слайд 4)Для первоначального разделения массива на две части нужно выбрать некоторое «барьерное» значение. Это значение должно удовлетворять единственному условию: лежать в диапазоне значений для данного массива (т. е. между минимальной и максимальной величинами). В качестве «барьера» можно выбрать значение любого элемента массива, например первого или последнего, или
находящегося в середине. ////////////////////////////////////////////////////////////////////////////////
Далее нужно сделать так, чтобы в левом подмассиве оказались все элементы
со значениями, меньшими или равными барьеру, а в правом — большими или
равными. Для этого, просматривая массив слева направо, нужно найти позицию
118
ПРИЛОЖЕНИЕ 3.(ПРОДОЛЖЕНИЕ)
первого элемента со значением, большим или равным барьеру, а просматривая
справа налево, найти первый элемент со значением, меньшим или равным барьеру. Поменять местами эти значения. Затем продолжить встречное движение до
следующей пары элементов, предназначенных для обмена. Так продолжать до тех
пор, пока индекс лево го просмотра не станет больше индекса правого просмотра.
Эти индексы будут разделителями двух взаимно упорядоченных под- массивов.
Далее алгоритм рекурсивно применяется к каждому из подмассивов (левому и
правому). В конечном счете приходим к совокупности из п взаимно упорядоченных одноэлементных массивов, которые делить дальше невозможно. Эта совокупность образует один полностью упорядоченный массив. Сортировка завершена!
В следующей программе вещественный массив А заполняется случайными
числами в диапазоне от 0 до 10. Затем этот массив сортируется с помощью процедуры быстрой сортировки QSort.(Слайд 5)
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
119
ПРИЛОЖЕНИЕ 3.(ПРОДОЛЖЕНИЕ)
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Константа N и массив А описаны в программе глобально. Процедура Qsort
(L, R) сортирует по возрастанию значений элементы массива А. Параметр L процедуры обозначает нижнее значение индекса сортируемого массива (крайний левый индекс), параметр R — верхнее значение индекса (крайний правый индекс).
Барьерное значение b a r вычисляется как значение элемента, имеющего индекс,
равный целой части среднего арифметического между L и R . ( С л а й д 6 )
120
ПРИЛОЖЕНИЕ 3.(ПРОДОЛЖЕНИЕ)
V.
Практическая работа. ////////////////////////////////////////////////////////////////////////////////
1.
Повторение правил ТБ работы за компьютером.(Слайд 7)
2.
Практическая работа. ////////////////////////////////////////////////////////////////////////////////
Задание 1. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Реализуйте на компьютере программу сортировки массива с использованием процедуры быстрой сортировки.
IV. Итоги урока и оценка знаний учащихся.
1. Что нового вы узнали на уроке? ////////////////////////////////////////////////////////////////////////////////
2. Сформулируйте идею алгоритма быстрой сортировки.
VI. Задание на дом.
121
ПРИЛОЖЕНИЕ 4.
ПРИЛОЖЕНИЕ 4. КОНСПЕКТ УРОКА НА ТЕМУ «ЛАБОРАТОРНАЯ РАБОТА. РЕКУРСИВНЫЕ МЕТОДЫ ПРОГРАММИРОВАНИЯ»
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Технологическая карта урока
Предмет:
Информатика.///////////////////////////////////////////////////////////////////
Класс: 11. ///////////////////////////////////////////////////////////////////
Тема урока: Лабораторная работа: «Рекурсивные методы программирования» //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Цели урока: //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Обучающие: сформировать/закрепить навыки создания рекурсивных подпрограмм; вспомнить алгоритм создания подпрограмм в языке программирования
Pascal. /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Развивающие: /////////////////////////////////////////////////////////////////////////////////////////////
 Развивать способность учащихся анализировать информацию;
 Развивать образное, критическое мышление;
 Развитие системного мышления. ///////////////////////////////////
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса. ///////////////////////////////////////////////////////////////////
Предполагаемые результаты обучения:
Предметные: ////////////////////////////////////////////////////////////////
 Сформировать представление о рекурсивных методах программирования.
 Умение создавать рекурсивные алгоритмы в ЯП Pascal.
 Метапредметные: //////////////////////////////////////////////////////
 Закрепить умение сравнивать, анализировать, делать выводы о восприятии
окружающих нас объектов;
 Иметь представление о подходах к поиску информации; Применение рекурсивных алгоритмов для решения математических задач.
Личностные: Стимулирование поиска вариантов на основе имеющихся
знаний; Формирование умения наблюдать, анализировать, сравнивать, делать выводы; Осуществление контроля и самоконтроля; Развитие находчивости, умения
преодолевать трудности для достижения намеченной цели.
122
ПРИЛОЖЕНИЕ 4.(ПРОДОЛЖЕНИЕ)
Используемые педагогические технологии, методы и приемы: развивающее обучение, личностно-ориентированные технологии, активное взаимодействие ученика и учителя. //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Тип урока: лабораторная работа./ ///////////////////////////////////////////////////////////////////
Необходимое оборудование проектор, карточки с заданиями, презентация
к уроку. //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
СТРУКТУРА И ХОД УРОКА
№
Этап урока
Деятельность учителя
1
1
2
3
Приветствует учащихся.
Проверяет готовность к
уроку
1. Задает вопросы по
раннее изученному материалу.(Слайд 1,2)
2
Организационный момент
Актуализация
знаний
Деятельность ученика
4
Приветствуют учителя. Готовят рабочие места к уроку
1.Отвечают на вопросы учителя.
2. Характеризуют
отношение к результату своей работы.
3. Отмечают при
необходимости непонятные моменты.
Формируемые УУД
5
Регулятивные
УУД: контроль знаний; оценка качества знаний
2.
3
Постановка
цели урока
Поделить класс на два ва- Учащиеся читают
рианта. Раздать карточки с текст заданий.
заданиями.
Формулирует тему и цели
урока.
Тема: Лабораторная работа: «Рекурсивные методы
программирования»(Слайд
3)
Познавательные
УУД: поиск и выделение необходимой информации;
Регулятивные
УУД: целеполагание
Коммуникативные
УУД: планирование
учебного сотрудничества с учителем;
умение полно и с
точностью выражать
свои мысли
123
ПРИЛОЖЕНИЕ 4.(ПРОДОЛЖЕНИЕ)
4
Цель нашего урока: закрепить на практике знания
о методах рекурсивного
программирования.
Практическая 1. Проводит вводный ин1.
работа за ком- структаж:
пьютером
а)повторение правил техники безопасности при работе за компьютером.(Слайд 4, 5, 6)
б)разбирает задания по вариантам
Вариант 1.
Задание 1. Расчет суммы
первых N натуральных чисел 2
Вычисление суммы
а) формулируют
правила ТБ.
б) садятся за компьютеры, слушают
учителя, задают вопросы если возникли
трудности с пониманием условия задачи.
2. Выполняют лабораторную работу.
Если возникают
трудности в ходе
выполнения практикума, задают вопросы учителю.
Познавательные
УУД:
Поиск и выделение
необходимой информации; структурирование знаний;
смысловое чтение;
определение основной и второстепенной информации;
анализ
Коммуникативные
УУД: планирование
учебного сотрудничества со сверстниками, управление
поведением партнера; умение с точностью выражать свои
мысли
Регулятивные
УУД: контроль и
коррекция
Личностные УУД:
нравственноэтическая ориентация, ориентация в
межличностных ролях.
124
ПРИЛОЖЕНИЕ 4.(ПРОДОЛЖЕНИЕ)
1+2+3+…+N можно определить следующим образом:
Sum(N) =
еслиN  0, тоSum  0


еслиN  0, тоSum  N  Sum( N  1)
Задание 2. Найдите
наибольший общий делитель двух натуральных чисел.
*Задание 3. Нахождения
суммы n членов арифметической прогрессии, заданной значениями первого
члена прогрессии а и разности d.
Лабораторная работа: «Рекурсивные методы программирования».
Вариант 2.
Задание 1. Расчет n-члена
арифметической прогрессии, заданной значением
первого члена a1 и разностью d.4
Вычисление n-члена арифметической прогрессии
можно определить следующим образом:
An =
 еслиN  1, тоan  a1

еслиN  1, тоan  an 1  d
Задание 2. Возведите
число a в целую степень n.
6
*Задание 3. Нахождения
суммы n членов арифметической прогрессии, заданной значениями первого
члена прогрессии а и разности d.
В)проводит текущий инструктаж
Оказывает помощь учащимся, при возникновении
трудностей непосредствен-
125
ПРИЛОЖЕНИЕ 4.(ПРОДОЛЖЕНИЕ)
но в ходе выполнения работы.
(Слайд 7)
5
Динамическая
пауза
Предлагает выполнить
упражнения для
глаз.(Слайд 9)
Выполняют гимнастику для глаз
Личностные УУД:
умение соотносить
поступки и события
с принятыми этическими принципами
Регулятивные
УУД: саморегуляция
6
Контроль за
результатом
учебной деятельности
школьников
1. Проверяются работы.
2.Учащимся выставляются
оценки.
1. Если у учителя
возникли вопросы по
выполнению работы,
дают на них ответы.
Личностные УУД:
ориентация в межличностных отношениях; знание моральных норм и
умение выделить
нравственный аспект поведения.
Регулятивные
УУД: планирование; контроль и коррекция; оценка результатов работы;
саморегуляция
Познавательные
УУД: поиск и выделение необходимой
информации; структурирование информации; смысловое чтение; определение основной и
второстепенной информации; моделирование, преобразование модели; анализ; выбор критериев для сравнения
126
ПРИЛОЖЕНИЕ 4.(ПРОДОЛЖЕНИЕ)
7
8
1.Организует рефлексию
Оценивают свою десобственной деятельности
ятельность, заканчиучащихся на уроке, предла- вая предложения.
гая закончить предложения:
1) На уроке я успел сделать …
Рефлексия де2) В результате я узнал и
ятельности
научился …
1. Я не понял, у меня не
получилось …
Запись домашнего задания.
Выводит домашнее задание
на слайд и комментирует.
Записывают домашнее задание «Подготовиться к контрольной работе»
Коммуникативные
УУД: планирование
учебного сотрудничества со сверстниками; управление
поведением партнера
Личностные УУД:
личностное самоопределение
Регулятивные
УУД: оценка результатов своей работы
Познавательные
УУД: рефлексия результатов деятельности
Регулятивные
УУД: прогнозирование
127
ПРИЛОЖЕНИЕ 5.
ПРИЛОЖЕНИЕ 5. КОНСПЕКТ УРОКА НА ТЕМУ «КОНТРОЛЬНАЯ
РАБОТА «РЕКУРСИВНЫЕ МЕТОДЫ ПРОГРАММИРОВАНИЯ»
Класс: 11.
Тема урока: Контрольная работа «Рекурсивные методы программирования».
Цели урока:
Образовательные (обучающие): проверить знания учащихся по теме «Рекурсивные методы программирования», проверить навыки решения рекурсивных
алгоритмов в ЯП Pascal.
Развивающие: продолжить развивать навыки
владения ИКТ – технологи-
ей, логическое мышление, навыки работы с ЯП Pascal.
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса (ОК 1 – общая компетенция).
Планируемые результаты:
Личностные:
 проявлять
положительное отношение к урокам информатики, интерес к
способам решения новых учебных задач, понимать причины успеха или неуспеха
в своей учебной деятельности;
 формировать
 устраивать
готовность к самообразованию и самовоспитанию;
эффективные групповые обсуждения и обеспечивать обмен зна-
ниями между членами группы для принятия совместных эффективных решений.
Метапредметные:
Познавательные:
 уметь
оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
 развивать
мотивы и интересы своей познавательной деятельности умение
создавать, применять и преобразовывать знаки и символы;
128
ПРИЛОЖЕНИЕ 5.(ПРОДОЛЖЕНИЕ)
Коммуникативные:

уметь оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
Регулятивные:

развитие навыков планирования деятельности: определение последователь-
ности промежуточных целей с учетом конечного результата, прогнозирование результата своей деятельности;

оценивать правильность выполнения действия на уровне адекватной ретро-
спективной оценки.
Предметные:
 знание основных понятий: рекурсия, рекурсивный алгоритм, рекуррентная
формула, стек, глубина рекурсии, прямая рекурсия, косвенная рекурсия;
 знание основных форм рекурсивных алгоритмов;
 умение анализировать рекурсивные алгоритмы проводить их трассировку.
Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов.
Оборудование: ПО, раздаточный материал (Карточки с заданиями), электронный тест.
Тип урока: урок контроля и оценки знаний.
Ход урока
I. Организационный момент.
II. Сообщение темы и постановка цели урока
III. Контроль и оценка знаний
1. Выполните электронное тестирование.
129
ПРИЛОЖЕНИЕ 5.(ПРОДОЛЖЕНИЕ)
2. Разбор условий предлагаемых в контрольной работе заданий.
Контрольная работа «Рекурсивные методы программирования»
Вариант 1.
Задание 1. Напишите рекурсивный вариант подпрограммы-функции вычисления чисел Фибоначчи.
Задание 2. Представьте натуральное число n в двоичной системе счисления.
Контрольная работа «Рекурсивные методы программирования»
Вариант 2.
Задание 1. Напишите рекурсивный вариант подпрограммы-процедуры задачи о Ханойской башне.
Задание 2. Найдите произведение n членов арифметической прогрессии,
заданной значениями первого члена прогрессии а и разности d.
3. Текущий инструктаж в ходе выполнения работы
Вариант 1.
130
1.
ПРИЛОЖЕНИЕ 5.(ПРОДОЛЖЕНИЕ)
Напишите рекурсивный вариант подпрограммы-функции вычисления
чисел Фибоначчи.
2. Представьте натуральное число в двоичной системе счисления.
Program Pr7;
Var
N:integer;
Procedure Bin_n(n:integer);
Begin
If n>1 then Bin_n(n div 2);
Write( n mod 2)
End;
BEGIN
{основная программа}
Write('n='); Readln(n);
Bin_n(n);
Readln
END.
Вариант 2.
1. Напишите рекурсивный вариант подпрограммы-процедуры задачи о Ханойской башне.
131
ПРИЛОЖЕНИЕ 5.(ПРОДОЛЖЕНИЕ)
4. Найдите произведение n членов арифметической прогрессии, заданной
значениями первого члена прогрессии а и разности d.
Program Pr5;
Var
Р,a,n,d: integer;
Function рa(n,a,d:integer):integer;
Begin
If n>0 then рa:=a+ рa(n-1,a+d,d) else рa:=1;
End;
BEGIN
{основная программа}
Write('n='); Readln(n);
Write('a='); Readln(a);
Write('d='); Readln(d);
Write(рa(n,a,d));
Readln
END.
IV. Итоги урока и оценка знаний учащихся.
1. Как вы оцениваете выполненую работу?
2. Какие задания вызвали наибольшие затруднения?
V. Задание на дом.
132
ПРИЛОЖЕНИЕ 6.
ПРИЛОЖЕНИЕ 6. КОНСПЕКТ УРОКА НА ТЕМУ «ОРГАНИЗАЦИЯ РЕКУРСИВНЫХ АЛГОРИТМОВ В СРЕДЕ ООП DELPHI»
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Класс: 11. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Тема урока: Организация рекурсивных алгоритмов в среде ООП Delphi.
Цели урока: ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Образовательные (обучающие): познакомить учащихся с понятием рекурсия, разобрать примеры применения рекурсивных алгоритмов в среде ООП
Delphi. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Развивающие: продолжить развивать навыки
владения ИКТ – технологи-
ей, логическое мышление, навыки работы в ООП Delphi. ////////////////////////////////////////////
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса. ////////////////////////////////////////////
Планируемые результаты: ////////////////////////////////////////////
Личностные: ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 проявлять
положительное отношение к урокам информатики, интерес к
способам решения новых учебных задач, понимать причины успеха или неуспеха
в своей учебной деятельности; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 формировать
 устраивать
готовность к самообразованию и самовоспитанию;
эффективные групповые обсуждения и обеспечивать обмен зна-
ниями между членами группы для принятия совместных эффективных решений.
Метапредметные: ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Познавательные: ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 уметь
оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
 развивать
мотивы и интересы своей познавательной деятельности умение
создавать, применять и преобразовывать знаки и символы; ////////////////////////////////////////////
Коммуникативные: ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
133

ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
уметь оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
Регулятивные: ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

развитие навыков планирования деятельности: определение последователь-
ности промежуточных целей с учетом конечного результата, прогнозирование результата своей деятельности; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

оценивать правильность выполнения действия на уровне адекватной ретро-
спективной оценки. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Предметные: ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 знание основных понятий: рекурсия, рекурсивный объект, глубина рекурсии, прямая рекурсия, косвенная рекурсия; ////////////////////////////////////////////////////////////////////////////////////////
 умение анализировать рекурсивные алгоритмы проводить их трассировку.
Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов. ////////////////////////////////////////////////////////////////////////////////////////
Оборудование: ПО, презентация, ПК. ////////////////////////////////////////////////////////////////////////////////////////
Тип урока: комбинированный. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Ход урока
I. Организационный момент. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
II. Сообщение темы и постановка цели урока. ////////////////////////////////////////////////////////////////////////////////////////
-Сегодня на уроке узнаете как реализуются рекурсивные алгоритмы на языку ООП Delphi.(Слайд 1). ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
III. Изучение нового материала.
134
ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
- Давайте вспомним что же такое рекурсия?(Слайд 2)
Рекурсивным называется объект, частично состоящий или определяемый с
помощью самого себя. ////////////////////////////////////////////////////////////////////////////////////////
Как вы уже знаете Факториал — это классический пример рекурсивного
объекта.(Слайд 3). ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Факториал числа n — это произведение целых чисел от 1 до п. Обозначается факториал числа n так: n!. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Согласно определению
N! = 1 х 2 х 3 х ... Х (n - 1) х п. Приведенное выражение можно переписать
так: ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
N! = nх ((n - 1) х (n - 2) х ...х 3 х 2 х 1) = n х (n - 1)!То есть, факториал числа
n равен произведению числа п на факториал числа (n - 1). В свою очередь, факториал числа («-!) — это произведение числа (n - 1) на факториал числа (n - 2) и т. Д.
Таким образом, если вычисление факториала n реализовать как функцию, то
в теле этой функции будет инструкция вызова функции вычисления факториала
числа (n - 1), т. Е. Функция будет вызывать сама себя. Такой способ вызова назы-
135
ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
вается рекурсией, а функция, которая обращается сама к себе, называется рекурсивной функцией. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
В листинге 12.1 приведена рекурсивная функция вычисления факториала.(Слайд 4) ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Листинг 12.1. Рекурсивная функция вычисления факториала
Function factorial(n: integer): integer; ////////////////////////////////////////////////////////////////////////////////////////
Begin////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
If n <> 1////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Then factorials n * factorial(n-1) ////////////////////////////////////////////////////////////////////////////////////////
// функция вызывает сама себя////////////////////////////////////////////////////////////////////////////////////////
Else factorial := 1; // рекурсивный процесс закончен
End; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Обратите внимание, что функция вызывает сама себя только в том случае,
если значение полученного параметра k не равно единице. Если значение параметра равно единице, то функция сама себя не вызывает, а возвращает значение, и
рекурсивный процесс завершается. ////////////////////////////////////////////////////////////////////////////////////////
На рис. 12.1 приведен вид диалогового окна программы, которая для вычисления факториала числа использует рекурсивную функцию factorial. Текст программы приведен в листинге 12.2.(Слайд 5)
136
ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
Рис. 12.1. Окно программы вычисления факториал
Листинг 12.2. Использование рекурсивной функции(Слайд 6)
Unit factor ; ////////////////////////////////////////////
Interface////////////////////////////////////////////
Uses////////////////////////////////////////////
Windows, Messages, sysutils, Classes, ////////////////////////////////////////////
Graphics, Controls, Forms, Dialogs, stdctrls; ////////////////////////////////////////////
Type////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Tform1 = class(tform) ////////////////////////////////////////////////////////////////////////////////////////
Label1: tlabel; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Edit1: tedit; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Button1: tbutton;
Label2: tlabel; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Procedure buttonlclick(Sender: tobject) ;
Private////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
{ Private declarations } public////////////////////////////////////////////////////////////////////////////////////////
137
ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
{ Public declarations } end; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Var////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Form1: tform1; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Implementation////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
{$R *.DFM}////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// рекурсивная функция////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Function factorial(n: integer): integer; ////////////////////////////////////////////////////////////////////////////////////////
Begin////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
If n > 1////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Then factorial := n * factorial(n-1) // функция вызывает сама себя
Else factorial:= 1; // факториал 1 равен 1 ////////////////////////////////////////////////////////////////////////////////////////
End; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Procedure tforml.buttonlclick(Sender: tobject); ////////////////////////////////////////////
Var////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
K:integer; // число, факториал которого надо вычислить
F:integer; // значение факториала числа k////////////////////////////////////////////////////////////////////////////////////////
Begin////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
K := strtoint(Edit1.Text); ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
F := factorial(k); ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Label2.caption:='Факториал числа '+Edit1.Text////////////////////////////////////////////
+ ' равен '+inttostr(f); ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
End; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
End. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
На рис. 12.2 приведены два диалоговых окна. Результат вычисления факториала, представленный на рис. 12.2, а, соответствует ожидаемому.(Слайд 7)
138
ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
Рис. 12.2. Примеры работы программы вычисления факториала
Результат, представленный на рис. 12.2, б, не соответствует ожидаемому.
Факториал числа 44 равен нулю! Произошло это потому, что факториал числа 44
настолько велик, что превысил максимальное значение для переменной типа
integer, и, как говорят программисты, произошло переполнение с потерей значения. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Delphi может включить в исполняемую программу инструкции контроля
диапазона значений переменных. Чтобы инструкции контроля были добавлены в
программу, нужно во вкладке Compiler диалогового окна Project Options (рис.
12.3) установить флажок Overflow checking (Контроль переполнения), который
находится в группе Runtime errors (Ошибки времени выполнения).
Рис. 12.3. Вкладка Compiler диалогового окна Project Options
В качестве примера использования рекурсии рассмотрим задачу поиска
файлов. (Слайд 8) ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
139
ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
Пусть нужно получить список всех файлов, например, с расширением bmp,
которые находятся в указанном пользователем каталоге и во всех подкаталогах
этого каталога. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Словесно алгоритм обработки каталога может быть представлен так:
1. Вывести список всех файлов удовлетворяющих критерию запроса.
2. Если в каталоге есть подкаталоги, то обработать каждый из этих каталогов. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Приведенный алгоритм (его блок-схема представлена на рис. 12.4) является
рекурсивным: для того чтобы обработать подкаталог, процедура обработки текущего каталога должна вызвать сама себя.(Слайд 9)
Рис. 12.4. Рекурсивный алгоритм поиска файлов
Вид диалогового окна программы приведен на рис. 12.5, текст — в листинге
12.3.
Поле Файл (Edit1) используется для ввода имени искомого файла или маски
(для поиска файлов одного типа). Имя каталога, в котором нужно выполнить поиск, можно ввести непосредственно в поле Папка или выбрать из стандартного
140
ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
диалогового окна Обзор папок, которое появляется в результате щелчка на кнопке Папка. Окно Обзор папок (рис. 12.6) выводит на экран стандартная функция
Seiectoirectory. Следует обратить внимание, что имя каталога, который используется в диалоговом окне Обзор папок в качестве корневого, должно передаваться
функции seiectdirectory как Строка whidechar. Для Преобразования обычной строки в строку widechar использована функция stringtowhidechar.(Слайд 10)
Рис. 12.5. Окно программы Поиск файлов(Слайд 11)
Рис. 12.6. Диалоговое окно Обзор папок появляется в результате щелчка на
кнопке Папка
Основную работу выполняет рекурсивная функция Find. У функции Find
один-единственный параметр — структура searchrec, которая используется функциями findfirst и findnext для поиска соответственнопервого и следующего файла,
удовлетворяющего критерию поиска. Следует обратить внимание на то, как осуществляется перебор каталогов в текущем каталоге. Если текущий каталог не
корневой, то помимо обычных, то есть имеющих имя, в каталоге есть еще два ка-
141
ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
талога: .. И ., которые обозначают каталог предыдущего уровня. Эти два каталога
не обрабатываются, так как при входе в эти каталоги фактически выполняется
выход (переход) в родительский каталог. Если этого не учесть, то программа зациклится.
Листинг 12.3. Программа поиск файлов(Слайд 12-14)
// поиск файла в указанном каталоге и его подкаталогах
// используется рекурсивная процедура Find
Unit findfile_;
Interface
Uses
Windows, Messages, sysutils, Variants,
Classes, Graphics, Controls, Forms,
Dialogs, stdctrls, filectr;
Type
Tform1 = class(tform)
Editl: tedit; // что искать
142
ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
Edit2: tedit; // где искать
Memo1: tmemo; // результат поиска
Button1: tbutton; // кнопка Поиск
Button2: tbutton; // кнопка Папка
Label1: tlabel;
Label2: tlabel;
Label3: tlabel;
Label4: tlabel;
Procedure Button1Click(Sender: tobject);
Procedure Button2Click(Sender: tobject);
Private
{ Private declarations }
Public
{ Public declarations }
End;
Var
Form1: tform1;
Implementation
{$R *.dfm}
Var
Filename: string; // имя или маска искомого файла
Cdir: string;
N: integer; // кол-во файлов, удовлетворяющих запросу
// поиск файла в текущем каталоге
Procedure Find;
Var
Searchrec: tsearchrec; // информация о файле или каталоге
Begin
Getdir(0,cdir); // получить имя текущего каталога
If cdir [length (cdir) ] <> 'V then cdir := cdir+'\';
143
ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
If findfirst(filename, faarchive,searchrec) = 0
Then repeat
If (searchrec.Attr and faanyfile) = searchrec.Attr
Then begin
Form1.Memo1.Lines.Add(cdir + searchrec.Name);
N := n + 1; end; until findnext(searchrec) <> 0;
// обработка подкаталогов текущего каталога
If findfirst('*', fadirectory, searchrec) = 0 then repeat
If (searchrec.Attr and fadirectory) = searchrec.Attr then begin
// каталоги .. И . Тоже каталоги,
// но в них входить не надо .'.'.'
If searchrec.Name[1] <> '.' then begin
Chdir(searchrec.Name);// войти в каталог
Find; // выполнить поиск в подкаталоге
Chdir('..');// выйти из каталога
End;
End;
Until findnext(searchrec) <> 0;
End;
/ возвращает каталог, выбранный пользователем
Function getpath(mes: string):string;
Var
Root: string; // корневой каталог
Pwroot : pwidechar; Dir: string;
Begin
Root := '';
Getmem(pwroot, (Length(Root)+1) * 2);
Pwroot := stringtowidechar(Root, pwroot, MAX_PATH*2);
If selectdirectory(mes, pwroot, Dir) then
If length(Dir) =2 // пользователь выбрал корневой каталог
144
ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
Then getpath := Dir+'\' else getpath := Dir else
Getpath := '';
End;
Щелчок на кнопке Поиск
Procedure tforml.buttonlclick(Sender: tobject);
Begin
Memo1.Clear; // очистить поле Memol
Label4.Caption := '';
Filename := Edit1.Text; // что искать.
Cdir := Edit2.Text; // где искать
N:=0; // кол-во найденных файлов
Chdir(cdir); // войти в каталог начала поиска
Find; // начать поиск
If n = 0 then
Showmessage('Файлов, удовлетворяющих критерию поиска нет.')
Else Label4.Caption := 'Найдено файлов:' + inttostr(n);
End;
// щелчок на кнопке Папка
Procedure tforml.Button2Click (Sender: tobject);
Var
Path: string; begin
Path := getpath('Выберите папку');
If Path <> ''
Then Edit2.Text := Path;
End;
End.
IV. Практическая работа за компьютером
1. Повторение правил техники безопасности при работе за компьютером.
2. Выполнение заданий.(Слайд 15)
145
ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
Задание 1.Реализуйте проект нахождения факториала.
Задание 2.Реализуйте проект поиска файлов.
IV. Итоги урока и оценка знаний учащихся.
1. Что нового вы узнали на уроке?
2. Сформулируйте идею рекурсивного алгоритма.
V. Задание на дом.
Задача 1. Создать проект расчета суммы ряда
procedure TForm1.Button1Click(Sender: TObject);
var y :real; //сумма ряда
n:real; //количество членов ряд
eps:real; //точность
function s(y,u,i:real):real;
{y-значение суммы ряда в начале шага,
u-очередной член ряда,
i-номер очередного члена ряда}
var sp:real;
begin sp:=y+u;
u:=-u/(2*i-1)/(2*i); //рекуррентная формула
if abs(u)=n} then
{ для конечного ряда условие с n, а для бесконечного с eps }
begin s:=sp; //терминальная ветвь
Memo1.Lines.Add('Количество слагаемых '+FloatToStr(i))
end
else s:=s(sp,u,i+1); //рекурсивное вычисление
end;
begin Memo1.Clear;
// для конечного ряда задается n, а для бесконечного eps
146
ПРИЛОЖЕНИЕ 6.(ПРОДОЛЖЕНИЕ)
eps:=StrToFloat(Edit1.Text);{n:=StrToFloat(Edit1.Text);}
// задаются значения y,u,i для первого шага
y:=s(0,1,1);
Memo1.Lines.Add('Сумма '+FormatFloat('0.000000',y)) end;
(Слайд 3) Форма проекта
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
147
ПРИЛОЖЕНИЕ 7.
ПРИЛОЖЕНИЕ 7. КОНСПЕКТ УРОКА НА ТЕМУ «ЗАДАЧА НА ПОИСК
ПУТИ»
Класс: 11.
Тема урока: Задача на поиск пути в ООП Delphi.
Цели урока:
Образовательные (обучающие): закрепить знания о процедурах и функциях, разобрать примеры применения рекурсивных алгоритмов в среде ООП Delphi
для решения задач на поиск пути.
Развивающие: продолжить развивать навыки
владения ИКТ – технологи-
ей, логическое мышление, навыки работы в ООП Delphi.
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса.
Планируемые результаты:
Личностные:
 проявлять
положительное отношение к урокам информатики, интерес к
способам решения новых учебных задач, понимать причины успеха или неуспеха
в своей учебной деятельности;
 формировать
 устраивать
готовность к самообразованию и самовоспитанию;
эффективные групповые обсуждения и обеспечивать обмен зна-
ниями между членами группы для принятия совместных эффективных решений.
Метапредметные:
Познавательные:
 уметь
оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
 развивать
мотивы и интересы своей познавательной деятельности умение
создавать, применять и преобразовывать знаки и символы;
Коммуникативные:
148

ПРИЛОЖЕНИЕ 7.(ПРОДОЛЖЕНИЕ)
уметь оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
Регулятивные:

развитие навыков планирования деятельности: определение последователь-
ности промежуточных целей с учетом конечного результата, прогнозирование результата своей деятельности;

оценивать правильность выполнения действия на уровне адекватной ретро-
спективной оценки.
Предметные:
 знание основных понятий: рекурсия, рекурсивный объект, глубина рекурсии, прямая рекурсия, косвенная рекурсия;
 умение анализировать рекурсивные алгоритмы проводить их трассировку.
Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов.
 Умение построить рекурсивный алгоритм «Задача на поиск пути».
Оборудование: ПО, презентация, ПК.
Тип урока: комбинированный.
Ход урока
I.
Организационный момент.
II. Проверка домашнего задания.
1.
Проверка и разбор задачи
Задача 1. Создать проект расчета сум(Слайд 1)
мы
ряда.
149
ПРИЛОЖЕНИЕ 7.(ПРОДОЛЖЕНИЕ)
Рещение: (Слайд 2)
procedure TForm1.Button1Click(Sender: TObject);
var y :real; //сумма ряда
n:real; //количество членов ряд
eps:real; //точность
function s(y,u,i:real):real;
{y-значение суммы ряда в начале шага,
u-очередной член ряда,
i-номер очередного члена ряда}
var sp:real;
begin sp:=y+u;
u:=-u/(2*i-1)/(2*i); //рекуррентная формула
if abs(u)=n} then
{ для конечного ряда условие с n, а для бесконечного с eps }
begin s:=sp; //терминальная ветвь
Memo1.Lines.Add('Количество слагаемых '+FloatToStr(i))
end
else s:=s(sp,u,i+1); //рекурсивное вычисление
end;
begin Memo1.Clear;
// для конечного ряда задается n, а для бесконечного eps
eps:=StrToFloat(Edit1.Text);{n:=StrToFloat(Edit1.Text);}
// задаются значения y,u,i для первого шага
150
ПРИЛОЖЕНИЕ 7.(ПРОДОЛЖЕНИЕ)
y:=s(0,1,1);
Memo1.Lines.Add('Сумма '+FormatFloat('0.000000',y)) end;
(Слайд 3) Форма проекта
III. Сообщение темы и постановка цели урока.
Механизм рекурсии весьма эффективен при программировании задач поиска. В качестве еще одного примера рассмотрим задачу поиска пути между двумя
городами. (Слайд 4)
IV. Изучение нового материала.
151
ПРИЛОЖЕНИЕ 7.(ПРОДОЛЖЕНИЕ)
Условие. Если несколько городов соединены дорогами, то очевидно, что
попасть из одного города в другой можно различными маршрутами. Задача состоит в нахождении всех возможных маршрутов.(Слайд 5).
Карта дорог между городами может быть изображена в виде графа — набора вершин, означающих города, и ребер, обозначающих дороги (рис. 12.9).(Слайд
6)
Рис. 12.9. Представление карты дорог в виде графа
Процесс поиска может быть представлен как последовательность шагов. На
каждом шаге с использованием некоторого критерия выбирается точка, в которую
можно попасть из текущей. Если очередная выбранная точка совпала с заданной
конечной точкой, то маршрут найден. Если не совпала, то делаем из этой точки
еще шаг. Так как текущая точка может быть соединена с несколькими другими, то
152
ПРИЛОЖЕНИЕ 7.(ПРОДОЛЖЕНИЕ)
нужен какой-то формальный критерий выбора. В простейшем случае можно выбрать точку с наименьшим номером.
Пусть, например, надо найти все возможные пути из точки 1 в точку 5. Согласно принятому правилу, сначала выбираем точку 2. На следующем шаге выясняем, что точка 2 тупиковая, поэтому возвращаемся в точку 1 и делаем шаг в точку 3. Из точки 3 — в точку 4, из 4 — в 6 и из точки 6 — в точку 5. Один маршрут
найден. После этого возвращаемся в точку 6 и проверяем, возможен ли шаг в точку, отличную от 5. Так как это возможно, то делаем шаг в точку 7, и затем — в 5.
Найден еще один путь. Таким образом, процесс поиска состоит из шагов вперед и
возвратов назад. Поиск завершается, если из узла начала движения уже некуда
идти.
Алгоритм поиска имеет рекурсивный характер: чтобы сделать шаг, мы выбираем точку и опять делаем шаг, и так продолжаем до тех пор, пока не достигнем цели.
Таким образом, задача поиска маршрута может рассматриваться как задача
выбора очередной точки (города) и поиска оставшейся части маршрута, т. е. имеет место рекурсия.
Граф можно представить двумерным массивом, который назовем тар (карта). Значение элемента массива map[i, j] — это расстояние между городами i и j,
если города соединены дорогой, или ноль, если города не соединены прямой дорогой. Для приведенного графа массив тар можно изобразить в виде таблицы,
представленной на рис. 12.10.(Слайд 7)
153
ПРИЛОЖЕНИЕ 7.(ПРОДОЛЖЕНИЕ)
Рис. 12.10. Массив тар
Содержимое ячейки таблицы на пересечении строки i и столбца j соответcтвует значению map [ i, j ].
Помимо массива тар нам потребуются массив road (дорога) и массив incl(от
include — включать). В road мы будем записывать номера пройденных городов. В
момент достижения конечной точки он будет содержать номера всех пройденных
точек, т. е. описание маршрута.
В inci [i] будем записывать true, если точка с номером i включена в маршрут. Делается это для того, чтобы не включать в маршрут уже пройденную точку
(не ходить по кругу).
Так как мы используем рекурсивную процедуру, то надо обратить особое
внимание на условие завершения рекурсивного процесса. Процедура должна прекратить вызывать сама себя, если текущая точка совпала с заданной конечной
точкой.
На рис. 12.11 приведена блок-схема алгоритма процедуры выбора очередной точки формируемого маршрута, а диалоговое окно — на рис. 12.12.
Для ввода массива, представляющего описание карты, используется компонент stringGridl (значения его свойств приведены в таблице 12.1), для вывода результата (найденного маршрута) — поле метки Label 1. Начальная и конечная
точки маршрута задаются вводом значений в поля редактирования Edit1 и Edit2.
Процедура поиска запускается щелчком кнопки Поиск (Buttonl). Поля меток
Label2, Label3 и Label4 используются для вывода поясняющего текста.
154
ПРИЛОЖЕНИЕ 7.(ПРОДОЛЖЕНИЕ)
Рис. 12.11. Блок-схема процедуры выбора точки маршрута(Слайд 8)
Рис. 12.12. Окно программы Поиск маршрута(Слайд 9)
Таблица 12.1. Значения свойств компонента stringGrid1(Слайд 10)
Свойство
Значение
Name
StringGrid1
ColCount
11
RowCount
11
FixedCols
1
FixedRows
1
Options . goEditing
TRUE
DefaultColWidth
16
155
ПРИЛОЖЕНИЕ 7.(ПРОДОЛЖЕНИЕ)
DefaultRowHeight
14
Текст программы приведен в листинге 12.5.
Листинг 12.5. Поиск маршрута(Слайд 11-13)
unit road_;
interface
uses
Windows, Messages, SysUtils, Classes,
Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids;
type
TForml = class(TForm)
StringGridl: TStringGrid;
Edit1: TEdit;
Edit2: TEdit;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Button1: TButton;
Label4: TLabel;
procedure FormActivate(Sender: TObject);
procedure ButtonlClickfSender: TObject);
private
{ Private declarations } public
{ Public declarations } end;
var
Form1: TForm1;
implementation
{$R *.DFM}
procedure TForml.FormActivate(Sender: TObject);
var
i:integer; begin
// нумерация строк
for i:=1 to 10 do
StringGridl.Cells[0,i]:=IntToStr(i); // нумерация колонок
for i:=l to 10 do
StringGridl.Cells[1,0]:=IntToStr(i);
// описание предопределенной карты StringGridl.Cells[1,2]:='1' StringGridl.Cells[2,l]:='1'
StringGridl.Cells[1,3]:='1'
StringGridl.Cells[3,1]:='1'
StringGridl.Cells[1,4]:='1'
StringGridl.Cells[4,1]:='1'
156
ПРИЛОЖЕНИЕ 7.(ПРОДОЛЖЕНИЕ)
StringGridl.Cells[3,7]:='1'
StringGridl.Cells[7,3]:='1'
StringGridl.Cells[4,6]:='1'
StringGridl.Cells[6,4]:='1'
StringGridl.Cells[5,6]:='1'
StringGridl.Cells[6,5]:='1'
StringGridl.Cells[5,7]:='1'
StringGridl.Cells[7,5]:='1'
StringGridl.Cells[6,7]:='1'
StringGridl.Cells[7,6]:='1'
end;
procedure TForml.ButtonlClick(Sender: TObject);
const
N=10;// кол-во вершин графа var
map:array[1..N,1..N]of integer; // Карта.map[i,j]ne 0,
// если точки i и j соединены
road:array[1..N]of integer;
// Дорога - номера точек карты
incl:array[1..N]of boolean; // incl[1]равен TRUE, если точка
// с номером i включена в road
start,finish:integer; // Начальная и конечная точки
found:boolean; i,j:integer;
procedure step(s,f,p:integer);
var
с:integer;// Номер точки, в которую делаем очередной шаг
i:integer;
begin
if s=f then begin
// Точки s и f совпали !
found:=TRUE;
Labell.caption:=Labell.caption+#13+'Путь:';
for i:=l to p-1 do
Labell.caption:=Labell.caption+' '
+IntToStr(road[i]); end
else begin
// выбираем очередную точку for c:=l to N do
begin // проверяем все вершины
if(map[s,c]<> 0)and(NOT incite1)
// точка соединена с текущей и не включена в маршрут
then begin
road[p]:=c;// добавим вершину в путь
incl[c]:=TRUE;// пометим вершину как включенную
step(c,f,p+l); incite]:=FALSE; road[p]:=0;
end;
157
ПРИЛОЖЕНИЕ 7.(ПРОДОЛЖЕНИЕ)
end;
end;
end;// конец процедуры step
begin
Label1.caption: =' ' ;
// инициализация массивов
for i:=l to N do road[i]:=0;
for i:=l to N do incl[i]:=FALSE;
// ввод описания карты из SrtingGrid.Cells
for i:=l to N do
for j:=1 to N do
if StringGrid1.Cells[i,j] <> ''
then map[i,j]:=StrToInt(StringGridl.Cells[i, j] ;
else map[i,j]:=0;
start:=StrToInt(Editl.text);
finish:=StrToInt(Edit2.text);
road[l]:=start;// внесем точку в маршрут
incl[start]:=TRUE;// пометим ее как включенную
step(start,finish,2);//ищем вторую точку маршрута
// проверим, найден ли хотя бы один путь
if not found
then Labell.caption:='Указанные точки не соединены!';
end;
end.
При запуске программы в момент активизации формы приложения происходит событие onActivate, процедура обработки которого заполняет массив
StringGridl.cells значениями, представляющими описание карты. Этаже процедура
нумерует строки и столбцы таблицы, заполняя зафиксированные ячейки первого
столбца и первой строки StringGridl.
Поиск маршрута инициирует процедура TFormi.Buttoniciick, которая запускается щелчком на кнопке Поиск. Данная процедура для поиска точки, соединенной с исходной точкой, вызывает процедуру step, которая после выбора первой
точки, соединенной с начальной, и включения ее в маршрут вызывает сама себя.
При этом в качестве начальной точки задается уже не исходная, а текущая, только
что включенная в маршрут.
Поиск кратчайшего пути
Обычно задача поиска пути на графе формулируется следующим образом:
найти наилучший маршрут. Под наилучшим маршрутом, как правило, понимают
158
ПРИЛОЖЕНИЕ 7.(ПРОДОЛЖЕНИЕ)
кратчайший. Найти кратчайший маршрут можно выбором из всех найденных.
Однако совсем не обязательно искать все маршруты.
Можно поступить иначе: во время выбора очередной точки проверить, не
превысит ли длина формируемого маршрута длину уже найденного пути, если эта
точка будет включена в маршрут; если превысит, то эту точку следует пропустить
и выбрать другую.
Таким образом, после того как будет найден первый маршрут, программа
будет вести поиск только по тем ветвям графа, которые могут улучшить найденное решение, отсекая пути, делающие формируемый маршрут длиннее уже
найденного.
В листинге 12.6 приведена процедура, которая использует процедуру step,
выполняющую выбор очередной точки маршрута таким образом, что обеспечивается поиск пути минимальной длины.(Слайд 14-15)
Листинг 12.6. Поиск кратчайшего пути
procedure TForm1.Button1Click(Sender: TObject);
const
N=10;{ кол-во вершин графа} var
map:array[1..N,1..N]of integer;
// Карта.map[i,j] не 0,если
// точки i и j соединены
road:array[1..N]of integer;
// Дорога — номера точек карты
incl:array[1..N]of boolean; // incl[1]равен TRUE,если точка
// с номером i включена в road
start, finish:integer;
// Начальная и конечная точки
found:boolean; len:integer; // длина найденного (минимального)
// маршрута } c_len:integer; // длина текущего (формируемого)
// маршрута i,j:integer;
// выбор очередной точки
procedure step(s,f,p:integer);
var
с:integer; { Номер точки, в которую делаем очередной шаг }
i:integer; begin
if s=f then begin
len:=c_len;{ сохраним длину найденного маршрута }
{ вывод найденного маршрута }
159
ПРИЛОЖЕНИЕ 7.(ПРОДОЛЖЕНИЕ)
for i:=1 to p-1 do
Label1.caption:=Label1.caption+' '+IntToStr(road[i]);
Label1.caption:=Label1.caption
+', длина:'+IntToStr(len)+#13;
end
else
{ выбираем очередную точку }
for c:=l to N do { проверяем все вершины }
if(map[s,c]<> 0)and(NOT incite])
and((len=0)or(c_len+map[s,c]< len)) then begin
// точка соединена с текущей, но не включена в
// маршрут
roadtp]:=c;{ добавим вершину в путь }
incl[c]:=TRUE;{ пометим вершину как включенную }
c_len:=c_len+map[s,с];
step(c,f,p+l);
incite]:=FALSE; roadtp]:=0;
c_len:=c_len-map[s,с];
end;
end;
{ конец процедуры step }
begin
Labell.caption:='';
{ инициализация массивов }
for i: =1 to N do road [ i ] : =0;
for i:=l to N do incl[i]:=FALSE;
{ ввод описания карты из SrtingGrid.Cells}
for i:=l to N do
for j:=1 to N do
if StringGridl.Cells[i, j] <> "
then mapti,j]:=StrToInt(StringGridl.Cells[i,j])
else mapti,j]:=0;
len:=0; // длина найденного (минимального) маршрута с
len:=0,- // длина текущего (формируемого) маршрута
start:=StrToInt(Edit1.text);
finish:=StrToInt(Edit2.text);
road[1]:=start;{ внесем точку в маршрут }
incl[start]:=TRUE;{ пометим ее как включенную }
step(start,finish,2);{ищем вторую точку маршрута }
// проверим, найден ли хотя бы один путь
if not found
then Label1.caption:='Указанные точки не соединены!';
end;
160
ПРИЛОЖЕНИЕ 7.(ПРОДОЛЖЕНИЕ)
Диалоговое окно программы поиска кратчайшего пути и процедура обработки события OnActivate ничем не отличаются от диалогового окна и соответствующей процедуры OnActivate программы поиска всех возможных маршрутов,
рассмотренной выше.
2. Динамическая пауза (Слайд 16)
IV. Практическая работа за компьютером
1. Повторение правил техники безопасности при работе за компьютером.
2. Выполнение заданий.
Задание 1.Реализуйте проект поиска пути.
IV. Итоги урока и оценка знаний учащихся.
1. Что нового вы узнали на уроке?
2. Рекурсия это…
2. Сформулируйте идею алгоритма поиска пути.
V. Задание на дом.
Записи в тетради.
161
ПРИЛОЖЕНИЕ 8
ПРИЛОЖЕНИЕ 8. КОНСПЕКТ УРОКА НА ТЕМУ «РЕКУРСИВНЫЕ
АЛГОРИТМЫ В ЗАДАНИЯХ К ЕГЭ»
Тема урока: Рекурсивные алгоритмы в заданиях к ЕГЭ.
Цели урока:
Образовательные (обучающие): закрепить знания учащихся по теме «Организация рекурсивных алгоритмов»; подготовить учащихся к решению заданий,
на нахождение рекурсии представленных в ЕГЭ.
Развивающие: продолжить развивать навыки
владения ИКТ – техноло-
гией, логическое мышление.
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса.
Планируемые результаты:
Личностные:
 проявлять положительное отношение к урокам информатики, интерес к
способам решения новых учебных задач, понимать причины успеха или неуспеха
в своей учебной деятельности;
 формировать готовность к самообразованию и самовоспитанию;
 устраивать эффективные групповые обсуждения и обеспечивать обмен
знаниями между членами группы для принятия совместных эффективных решений.
Метапредметные:
Познавательные:
 уметь оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
 развивать
мотивы
и
интересы
своей
познавательной
сти умение создавать, применять и преобразовывать знаки и символы.
Коммуникативные:
162
ПРИЛОЖЕНИЕ 8(ПРОДОЛЖЕНИЕ)
 уметь оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью.
Регулятивные:
 развитие навыков планирования деятельности: определение последовательности промежуточных целей с учетом конечного результата, прогнозирование результата своей деятельности;
 оценивать правильность выполнения действия на уровне адекватной ретроспективной оценки.
Предметные:
 знание основных понятий: рекурсия, рекурсивный алгоритм, рекуррентная
формула, стек, глубина рекурсии, прямая рекурсия, косвенная рекурсия;
 знание основных форм рекурсивных алгоритмов;
 умение анализировать рекурсивные алгоритмы проводить их трассировку. Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов.
 умение выполнять задания по решениею рекурсивных алгоритмов в ЕГЭ.
Оборудование: ПО, презентация.
Тип урока: Урок обобщения и систематизации.
Ход урока
I. Организационный момент.
II. Актуализация знаний и фиксирование затруднений.
1. Решение кроссворда «Рекурсия».
https://learningapps.org/watch?v=pvygevgpn18
163
ПРИЛОЖЕНИЕ 8(ПРОДОЛЖЕНИЕ)
Ответ: 1. Рекурсия.
Ответ: 2. Подпрограмма.
Ответ: 3. Условие.
164
ПРИЛОЖЕНИЕ 8(ПРОДОЛЖЕНИЕ)
Ответ: 4. Спуск.
Ответ: 5. Возврат.
Ответ: 6. Глубина.
165
ПРИЛОЖЕНИЕ 8(ПРОДОЛЖЕНИЕ)
Ответ: 7. Прямая.
Ответ: 8. Косвенная.
III. Целеполагание.
- В заданиях предлагаемых в ЕГЭ также встречаются, задачи на умение использовать рекурсивные алгоритмы. Процент выполнение задания с рекурсией
составляет примерно всего 13,2%. Владение навыками решения таких задач является немаловажной проблемой. (Слайд 1)
IV. Обобщение и систематизация знаний.
Задачи на рекурсию представлены в ЕГЭ заданием №11.
Способ решения таких заданий: последовательное выполнение операций
от начального определения до определения с введенным в алгоритм значением.
На слайдах подобраны задания из ЕГЭ. Сейчас мы рассмотрим их.(2-12).
166
ПРИЛОЖЕНИЕ 8(ПРОДОЛЖЕНИЕ)
Вот так выглядят задания на бланках ЕГЭ.
Ниже на пяти языках программирования записан рекурсивный алгоритм
F.(Слайд 13)
167
ПРИЛОЖЕНИЕ 8(ПРОДОЛЖЕНИЕ)
Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)?
Пояснение.
Первым действием процедура F(1) выведет число 1. Далее процедура F(1)
вызовет процедуру F(n + 1), в результате выполнения которой на экране появится
число n + 1 = 2. Процедура F(2) вызовет процедуру F(3), которая выведет на экран
число 3 и вызовет процедуру F(4), которая выведет на экран число 4 и вызовет
F(5), которая выведет на экран число 5.
После этого управление вернётся к процедуре F(4), которая начнёт выполнять следующий шаг своего алгоритма, т. Е. Обратиться к процедуре F(n + 3) =
F(7). Процедура F(7) выведет на экран число 7. Далее управление вернётся к процедуре F(3). Рассуждая аналогично приходим к выводу, что процедура F(3) дополнительно выведет на экран число 6, процедура F(2) — 5. Последним действием
процедуры F(1) будет вызов процедуры F(n + 3) = F(4), которая выведет на экран
числа 4, 5, 7.
Таким образом, на экране будут числа 1, 2, 3, 4, 5, 7, 6, 5, 4, 5, 7. Их сумма
равна 49.
О т ве т: 49.
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
(Слайд 14)
168
ПРИЛОЖЕНИЕ 8(ПРОДОЛЖЕНИЕ)
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(5)?
Пояснение.
Значение, вычисленное алгоритмом при вызове F(5) равно:
F(5)= F(4) + F(3) = F(3) + F(2) + F(2) + F(1) = F(2) + F(1) +1 + 1 + 1 = 5.
Мы рассмотрели примеры рекурсивных алгоритмов. Сейчас вы сами попробуете решить несколько заданий.(15-21)
169
ПРИЛОЖЕНИЕ 8(ПРОДОЛЖЕНИЕ)
V. Итоги урока и оценка знаний учащихся.
Фронтальный опрос(слайд 22)
1. Что представляет собой рекурсия?
2. Можно
ли
арифметическую
и
геометрическую
прогрессии
назвать рекуррентными последовательностями?
3. Как описать рекурсивный алгоритм в Pascal?
4. Приведите примеры рекурсивных алгоритмов?
5. Рекурсивная последовательность это…?
6. Рекуррентная формула это …?
7. Рекурсивная подпрограмма (функция, процедура) это …?
VI. Задание на дом.
Записи в тетрадях. Подготовиться к контрольной работе.
170
ПРИЛОЖЕНИЕ 9.
ПРИЛОЖЕНИЕ 9. КОНСПЕКТ УРОКА НА ТЕМУ «КРИВАЯ ГИЛЬБЕРТА» (МАТЕРИАЛ ДЛЯ САМОСТОЯТЕЛЬНОГО ИЗУЧЕНИЯ)
Класс: 11.
Тема урока: Кривая Гильберта
Цели урока:
Образовательные (обучающие): закрепить знания о процедурах и функциях, разобрать примеры применения рекурсивных алгоритмов в среде ООП Delphi
для построения «Кривой Гильберта».
Развивающие: продолжить развивать навыки
владения ИКТ – технологи-
ей, логическое мышление, навыки работы в ООП Delphi.
Воспитательные: способствовать воспитанию интереса к своей будущей
профессии, проявлению к ней устойчивого интереса.
Планируемые результаты:
Личностные:
 проявлять
положительное отношение к урокам информатики, интерес к
способам решения новых учебных задач, понимать причины успеха или неуспеха
в своей учебной деятельности;
 формировать
 устраивать
готовность к самообразованию и самовоспитанию;
эффективные групповые обсуждения и обеспечивать обмен зна-
ниями между членами группы для принятия совместных эффективных решений.
Метапредметные:
Познавательные:
 уметь
оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
 развивать
мотивы и интересы своей познавательной деятельности умение
создавать, применять и преобразовывать знаки и символы;
Коммуникативные:
171

ПРИЛОЖЕНИЕ 9.(ПРОДОЛЖЕНИЕ)
уметь оформлять свои мысли в устной форме; слушать и понимать речь
других; совместно договариваться о правилах поведения и общения в школе и
следовать им; выражать свои мысли с достаточной полнотой и точностью;
Регулятивные:

развитие навыков планирования деятельности: определение последователь-
ности промежуточных целей с учетом конечного результата, прогнозирование результата своей деятельности;

оценивать правильность выполнения действия на уровне адекватной ретро-
спективной оценки.
Предметные:
 знание основных понятий: рекурсия, рекурсивный объект, глубина рекурсии, прямая рекурсия, косвенная рекурсия;
 умение анализировать рекурсивные алгоритмы проводить их трассировку.
Знание основных конструкций языка программирования необходимых для построения рекурсивных алгоритмов.
 Умение построить алгоритм позволяющий вывести на экран
«Кривую
Гильберта».
Оборудование: ПО, презентация, ПК.
Тип урока: комбинированный.
Ход урока
I. Организационный момент.
II. Сообщение темы и постановка цели урока
-Сегодня на уроке мы рассмотрим такой рекурсивный алгоритм, как алгоритм построения «Кривой Гильберта». Вам будет предложено создать проект для
реализации данного алгоритма.(Слайд 4)
172
ПРИЛОЖЕНИЕ 9.(ПРОДОЛЖЕНИЕ)
III. Изучение нового материала.
Алгоритм был разработан Давидом Гильбертом(Слайд 5)
Данная программа вычерчивает в диалоговом окне кривую Гильберта. На
рис. 12.7 приведены кривые Гильберта первого, второго и третьего порядков. Если присмотреться, то видно, что кривая второго порядка получается путем соединения прямыми линиями четырех кривых первого порядка. Аналогичным образом
получается кривая третьего порядка, но при этом в качестве "кирпичиков" используются кривые второго порядка. Таким образом, чтобы нарисовать кривую
третьего порядка, надо нарисовать четыре кривых второго порядка. В свою очередь, чтобы нарисовать кривую второго порядка, надо нарисовать четыре кривых
первого порядка. Таким образом, алгоритм вычерчивания кривой Гильберта является рекурсивным.
Диалоговое окно программы Кривая Гильберта, в котором находится кривая
пятого порядка, приведено на рис. 12.8, текст программы — в листинге
12.4.(Слайд 6)
173
ПРИЛОЖЕНИЕ 9.(ПРОДОЛЖЕНИЕ)
Рис. 12.7. Кривые Гильберта первого, второго и третьего порядков
Рис. 12.8. Кривая Гильберта пятого порядка(Слайд 7)
Листинг 12.4. Кривая Гильберта(Слайд 8-10)
unit gilbert_;
interface
uses
Windows, Messages, SysUtils,
Variants, Classes, Graphics,
Controls, Forms, Dialogs, StdCtrls, ComCtrls;
type
TForml = class(TForm)
procedure FormPaint(Sender: TObject);
private
{ Private declarations }
public
174
ПРИЛОЖЕНИЕ 9.(ПРОДОЛЖЕНИЕ)
{ Public declarations }
end;
var
Form1: TForm1;
implementation {$R *.dfm}
var
p: integer =5; // порядок кривой
u: integer =7; // длина штриха
{ Кривую Гильберта можно получить путем
соединения элементов а,b,с и d.
Каждый элемент строит
соответствующая процедура. }
procedure a(i:integer; canvas: TCanvas); forward;
procedure b(i:integer; canvas: TCanvas); forward;
procedure с(i:integer; canvas: TCanvas); forward;
procedure d(i:integer; canvas: TCanvas); forward;
// Элементы кривой
procedure a(i: integer; canvas: TCanvas);
begin
if i > 0 then begin
d(i-l, canvas);
canvas.LineTo(canvas.PenPos.X+u,canvas.PenPos.Y);
a(i-l, canvas);
canvas.LineTo(canvas.PenPos.X,canvas.PenPos.Y+u);
a(i-l, canvas);
canvas.LineTo(canvas.PenPos.X-u,canvas.PenPos.Y);
с (i-1, canvas);
end;
end;
procedure b(i: integer; canvas: TCanvas);
begin
if i > 0 then begin
c(i-l, canvas);
canvas.LineTo(canvas.PenPos.X-u,canvas.PenPos.Y);
b(i-1, canvas);
canvas.LineTo(canvas.PenPos.X,canvas.PenPos.Y-u);
b(i-l, canvas);
canvas.LineTo(canvas.PenPos.X+u, canvas.PenPos.Y);
d(i-l, canvas);
end;
end;
procedure c(i: integer; canvas: TCanvas);
begin
if i > 0 then begin
175
ПРИЛОЖЕНИЕ 9.(ПРОДОЛЖЕНИЕ)
b(i-1, canvas);
canvas.LineTo(canvas.PenPos.X,canvas.PenPos.Y-u);
с (i-1, canvas);
canvas.LineTo(canvas.PenPos.X-u,canvas.PenPos.Y);
c(i-1, canvas);
canvas.LineTo(canvas.PenPos.X,canvas.PenPos.Y+u);
a(i-1, canvas);
end;
end;
procedure d(i: integer; canvas: TCanvas);
begin
if i > 0 then begin
a(i-1, canvas);
canvas.LineTo(canvas.PenPos.X,canvas.PenPos.Y+u);
d(i-1, canvas);
canvas.LineTo(canvas.PenPos.X+u,canvas.PenPos. Y) ;
d(i-1, canvas);
canvas.LineTo(canvas.PenPos.X,canvas.PenPos.Y-u);
b(i-1, canvas);
end;
end;
procedure TForml.FormPaint(Sender: TObject);
begin
Form1.Canvas.MoveTo(u, u) ;
a(5,Form1.Canvas); // вычертить кривую Гильберта
end;
end.
Следует обратить внимание на следующую особенность реализации программы. Процедура, которая вычерчивает элемент а, помимо самой себя (для вычерчивания элемента а кривой более низкого порядка) вызывает процедуры d и b,
описание (текст) которых в тексте программы находится после процедуры а. Чтобы компилятор не вывел сообщение об ошибке, в текст программы помещено
объявление процедуры с ключевым словом forward, означающим, что это только
объявление, а описание (реализация) находится дальше. Таким образом, уже в
процессе компиляции процедуры а, компилятор "знает", что имена d и b означают
процедуры.(Слайд 11)
176
ПРИЛОЖЕНИЕ 9.(ПРОДОЛЖЕНИЕ)
IV. Практическая работа за компьютером
1.
Повторение правил техники безопасности при работе за компью-
тером.
2.
Выполнение заданий.
Задание 1.Реализуйте проект построения «Кривой Гильберта».
V. Итоги урока и оценка знаний учащихся.
1.
Что нового вы узнали на уроке?
2.
Как описать процедуру в ООП Delphi?
3.
Как описать функцию в ООП Delphi?
4.
Рекурсия это…
5.
Сформулируйте идею алгоритма поиска пути.
6.
Какие компоненты будут вам необходимы при создании проекта
«Кривая Гильберта»?
VI. Задание на дом.
Просмотреть примеры рекурсивных алгоритмов. Записи в тетрадях.
177
ПРИЛОЖЕНИЕ 10
ПРИЛОЖЕНИЕ 10. ЭЛЕКТРОННЫЙ УЧЕБНИК «ОРГАНИЗАЦИЯ
РЕКУРСИВНЫХ АЛГОРИТМОВ В ЯЗЫКАХ ПРОГРАММИРОВАНИЯ
PASCAL И DELPHI
178
ПРИЛОЖЕНИЕ 10.(ПРОДОЛЖЕНИЕ)
179
ПРИЛОЖЕНИЕ 10.(ПРОДОЛЖЕНИЕ)
180
ПРИЛОЖЕНИЕ 10.(ПРОДОЛЖЕНИЕ)
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
1/--страниц
Пожаловаться на содержимое документа