- •A. Государственный образовательный стандарт
- •B. Рабочая программа учебной дисциплины b.1. Цели и задачи дисциплины, ее место в учебном процессе
- •B.2. Протокол согласования рабочей программы с другими дисциплинами специальности на 200_ учебный год
- •B.3. Объем дисциплины и виды учебной работы
- •B.4. Содержание дисциплины b.4.1.Тематический план
- •B.4.2. Лекционный курс
- •B.4.3. Лабораторный практикум
- •B.4.4. Самостоятельная работа студентов
- •B.5. Список рекомендуемой литературы для изучения дисциплины
- •B.6. Вопросы к экзамену
- •B.9. Тематический план
- •C.2.Технические и программные средства реализации информационных процессов.
- •C3. Модели решения функциональных и вычислительных задач. Алгоритмизация и программирование. Алгоритмы, классы, типы, свойства алгоритмов, Языки программирования высокого уровня (обзор).
- •C.4. Тема 4. Основы и методы защиты информации.
- •C.5. Тема 5.Компьютерный практикум.
- •C.9. Тема 9. Постановка задачи и спецификация программы. Способы записи алгоритмов. Стандартные типы данных.
- •5. Описание процедур и функций. Этот вопрос рассматривается в пункте 6.
- •C.10.5. Лекция 5 (1час) Понятие рекурсии, примеры рекурсивных задач и программ с рекурсивными вызовами процедур и функций.
- •C.10.7. Лекция 7 (2 часа) Множества
- •D. Лабораторный практикум d.1 Лабораторная работа № 1
- •D.2. Лабораторная работа № 2
- •D.3. Лабораторная работа № 3
- •D.3.1. Варианты для задания 1. «Простейшие циклы»
- •D.3.2. Варианты для задания 2 «Обработка одномерных массивов»
- •D.4. Лабораторная работа № 4
- •D.5. Лабораторная работа № 5
- •D.6. Лабораторная работа № 6
- •D.7. Лабораторная работа № 7
- •D.8. Лабораторная работа № 8
- •D.9. Лабораторная работа № 9
- •D.10. Лабораторная работа № 10
- •D.11. Литература к лабораторным работам
- •E. Самостоятельная работа. E.1. Задачи для самостоятельной работы e.1.1. Задачи для самостоятельной работы по теме: "Запись числовых констант, переменных и выражений".
- •E.1.2. Задачи для самостоятельной работы по теме: "Типы данных. Операции и функции над данными разных типов".
- •E.1.3. Задачи для самостоятельной работы по теме: "Операторы цикла".
- •E.1.4. Задачи для самостоятельной работы по теме: "Массивы".
- •E.1.5. Задачи для самостоятельной работы по теме: "Процедуры и функции".
- •E.1.6. Задачи для самостоятельной работы по теме: "Строки".
- •E.1.7. Задачи для самостоятельной работы по теме: "Множества".
- •E.1.8. Задачи для самостоятельной работы по теме: "Файлы".
- •E.2. Задачи и упражнения на тему «Структуры данных»
- •E.2.1. Векторы
- •E.2.2. Матрицы
- •E.2.3. Строки
- •E.2.4. Записи и таблицы
- •E.2.5. Списки
- •E.2.6. Очереди, стеки, деревья
- •E.2.7. Двоичные деревья
- •E.2.8. Литература по теме «Структуры данных»
- •G. Контрольные задания по лабораторным работам g.1. Контрольная работа по лабораторным № 3,4
- •G.2. Контрольная работа по лабораторной № 5
- •G.3. Контрольная работа по лабораторным № 6, 7, 8
- •H. Тематика контрольных работ по дисциплине Информатика и программирование
- •I. Вопросы к экзамену
- •J. Литература
C.10.5. Лекция 5 (1час) Понятие рекурсии, примеры рекурсивных задач и программ с рекурсивными вызовами процедур и функций.
В математике рекурсией называется способ описания функций или процессов через самих себя.
Широкое проникновение рекурсивных методов в практику программирования началось с распространения универсального языка программирования АЛГОЛ-60, допускающего рекурсивное обращение к процедурам. Рекурсия отражает существенную характерную черту a6cтpaктнoro мышления, проявляющуюся при анализе сложных алгоритмических и структурных конструкций в самых различных приложениях. Пользуясь рекурсией, мы избавляемся от необходимости утомительного последовательного описания конструкции и ограничиваемся выявлением взаимосвязей между различными уровнями этой конструкции.
В последнее время в связи с широким распространением прикладных программ, не связанных с проведением расчетов, бытует взгляд на рекурсию как на интересное, но необязательное украшение системы программирования. Даже в некоторых последних книгах по Турбо Паскалю не находится места для описания рекурсии.
Если процедура или функция в ходе выполнения вызывает саму себя, то мы имеем дело с рекурсией. Такой вызов процедур или функций может возникнуть либо вследствие рекурсивного описания, либо вследствие рекурсивного обращения. Рекурсивное описание предполагает, что в исполняемой части блока процедуры или функции присутствует обращение к ней самой. Примером рекурсивного описания может служить функция вычисления факториала:
Function Factorial (N: Integer): Integer;
Begin
if N =1 Then Factorial := 1
Else Factorial :=N*Factoirial(N-1);
End.
Здесь Factorial(N) определяет через значение Frictorial(N-i), которое определяется через Factorial(N*2), и т.д. до сведения к значению Factorial(O), которое определено явно и равно 1. Любое рекурсивное описание должно содержать явное определение для некоторых значений аргумента (илиаргументов), так как иначе процесс сведения оказался бы бесконечным. Таким образом при рекурсивном описании необходимо наличие базовой части описания, которая обеспечивала бы завершение рекурсивных вызовов функции (процедуры).
Рекурсивное обращение можно рассмотреть на примере вычисления определенного двойного интеграла по формуле трапеций. Точность этого приближения тем выше, чем больше число участков разбиения п. Увеличивая число п, можно достигнуть заданной точности. Если, допустим, функция TRAP вычисляет интеграл по методу трапеций при заданном числе интервалов N и А, В - пределы интегрирования, a FN - функция вычисления подынтегрального выражения, вычисление двойного интеграла можно осуществить с помощью следующего рекурсивного обращений к функции TRAP:
J :=TRAP (N1, A1, B1, TRAP (N2, A2, B2, FN));
Ниже приведена рекурсивная функция, предназначенная для вычислений наибольшего общего делителя двух целых чисел N1 и N2.
Пример 3.1.
Function HlighFactor(N1 ,N2:lnteger):lnteger;
Var P: Integer;
Begin
If N1 > N2 Then P:=HighFactor(N1,N2)
Else
If N2<0 Then р:=N1 {нерекурсивное решение}
Else P:=HighFactor(N2,N1 Mod N2);
HighFactor := P
End;
Дл того чтобы выполнение рекурсивной программы завершалось, необходимо существование в наиболее простых случаях нерекурсивного решения. В противном случае не исключено зацикливание.
Некоторые алгоритмы гораздо проще описать, используя рекурсию нежели итерацию. Это относится в первую Очередь к алгоритмам, работающим с разного рода списковыми структурами.
Использование рекурсивных процедур и функций делает программу целом более гибкой и наглядной, но не всегда эффективной, так как работает такая программа, как правило, медленнее и требует больше памяти. Дело том, что при каждом вызове рекурсивной процедуры или функции отводится память под локальные переменные.
При сравнении итерационных методов решения и методов, использующих рекурсию, часто эффективными оказываются первые. Таким образом, рекурсии следует применять только там, где нет очевидного итерационного решения. Уровень вложенности рекурсий может быть ограничен в конкретных реализациях языка.
Различают прямую и косвенную рекурсию. Функция HighFactor являете характерным примером прямой рекурсии. Косвенная рекурсия возникает тогда когда один блок вызывает второй, а второй, в свою очередь, первый.
C.10.6. Лекция 6 (1 часа)Понятие данных символьного типа. Представление символов в ЭВМ. Таблица ASCI. Операции над символьными данными. Функции CНR( ), ORD( ), SUCC( ), PRED( ).Символьные строки (string). Операции над строками, встроенные процедуры и функции для работы со строками символов
String(строка) - это один из дополнительных типов данных, введенных в системе программирования Турбо-Паскаль. Структура данных типаString [N] аналогична структуре данных типаArray [1..N]Of Char. Количество символов в данных типа String [N]может быть любым от 1 доN. Максимальное возможное значение константыN=255. Это максимальное значение принимается по умолчанию, если в описании строки отсутствует конструкция[N].В отличие от массивов строки (а не только их отдельные элементы) могут быть параметрами в процедурах ввода и вывода. К любому символу в строке можно обратиться точно также, как к элементу одномерного массива, указав имя строки и индекс. В системе Турбо-Паскаль для работы со строками предусмотрен ряд процедур и функции: К строкам можно применять операцию“+” - сцепление, например: st:= ‘a’ + ‘b’; st:= st + ‘c’; {st содержит ‘abc’}
Copy(st, index, count)- функция типаString; копирует из строки st count символов, начиная с символа с номером index.Delete(st, index, count)- процедура; удаляет сount символов в строке st, начиная с символа с номером index.Insert(subst, st, index)- процедура; вставляет подстроку subst в строку st, начиная с символа с номером index.Length(st) - функция типа Integer; возвращает длину строки st.Pos(subst,st)- функция типа Integer; отыскивает в строке st первое вхождение подстроки subst и возвращает номер позиции, с которой она начинается; если подстрока не найдена, возвращается 0.Str(x:[width[ : decimals] ], st) - процедура; преобразует число x вещественного или целого типов в строку символов st так, как это делает процедураWritelnперед выводом.Val(st,x,code)- процедура; преобразует строку символов st во внутреннее представление целой или вещественной переменной x, которое определяется типом этой переменной; параметр code содержит ноль, если преобразование прошло успешно, и тогда в x помещается результат преобразования, в противном случае он содержит номер позиции в строке st, где обнаружен ошибочный символ, и в этом случае содержимое x не меняется; ведущие пробелы в строке st должны отсутствовать. Операции отношения =, <>, >, <, >=, <=выполняются над двумя строками посимвольно, слева направо с учетом внутренней кодировки символов.