- •Основы алгоритмизации и программирования
- •Введение
- •1.1. Структура программы
- •1.2. Типы данных
- •1.2.1. Целый тип данных
- •1.2.2. Логические типы данных – Boolean
- •1.2.3. Данные символьного типа
- •1.3. Операторы языка программирования Турбо Паскаль
- •1.3.1. Операции в Турбо Паскаль
- •1.3.2. Правила вычисления выражений
- •1.3.3. Встроенные функции в Турбо Паскаль
- •1.3.4. Описание констант и переменных
- •1.3.5. Операторы в Турбо Паскаль
- •Вопросы для самопроверки
- •Лабораторная работа №1 Организация программ линейных структур
- •Варианты заданий
- •2. Организация форматного вывода данных на языке Паскаль
- •Вопросы для самопроверки
- •Лабораторная работа №2 Организация ввода-вывода данных на языке Паскаль
- •Методические указания
- •Варианты задания
- •3. Организация программ разветвляющихся структур
- •3.1. Полная форма условного оператора
- •3.2. Краткая форма условного оператора
- •Вопросы для самопроверки
- •Лабораторная работа №3 Организация программ разветвляющихся структур
- •Варианты заданий
- •4. Организация циклических процессов
- •Лабораторная работа №4 Составление циклических программ
- •Варианты заданий
- •Методические указания
- •Варианты заданий
- •5. Программирование структур с вложенными циклами
- •Вопросы для самопроверки
- •Лабораторная работа №5 программирование структур с вложенными циклами. Вычисление суммы ряда
- •Методические указания
- •Варианты заданий
- •6. Перечислимые и ограниченные типы данных
- •6.1 Перечислимый тип данных
- •6.2. Ограниченный тип данных
- •6.3. Оператор выбора (варианта)
- •Вопросы для самопроверки
- •Лабораторная работа №6 Перечислимые и ограниченные типы данных
- •Варианты заданий.
- •7. Регулярные типы данных
- •7.1. Одномерные массивы
- •7.1.1. Краткая форма объявления одномерного массива
- •7.1.2. Полная форма объявления одномерного массива
- •7.1.3. Доступ к элементам массива
- •Вопросы для самопроверки
- •Лабораторная работа №7_1 регулярные типы данных. Массивы
- •Варианты заданий
- •7.2. Двумерные массивы
- •Полная форма описания матрицы:
- •Формирование элементов случайным образом:
- •Формирование элементов матрицы при вводе с клавиатуры:
- •Фрагменты программ по обработке 2-х мерных массивов
- •Вопросы для самопроверки
- •Лабораторная работа №7_2 регулярные типы данных. МАтрицы
- •Варианты заданий
- •7.3. Сортировка элементов массива
- •7.3.1. Сортировка методом «пузырька»
- •7.3.2. Сортировка вставками
- •7.3.3. Сортировка посредством выбора
- •7.3.4. Быстрая сортировка
- •8. Составление программ с использованием подпрограмм
- •8.1. Область видимости идентификатора переменной
- •8.2. Подпрограммы - процедуры (procedure)
- •8.2.1. Формальные и фактические параметры
- •Вопросы для самопроверки
- •Лабораторная работа №8_1 составление программ с использованием подпрограмм - процедур
- •Методические указания
- •Варианты заданий
- •8.3. Подпрограммы-функции (function)
- •Вопросы для самопроверки
- •Лабораторная работа №8_2 составление программ с использованием подпрограмм - функций
- •Варианты заданий
- •8.4. Рекурсия
- •8.4.1. Вычисление факториала
- •8.4.2. Формы рекурсивных процедур
- •8.4.3. Числа Фибоначчи
- •Вопросы для самопроверки
- •9. Модули
- •Структура модуля
- •Interface
- •Implementation
- •Вопросы для самопроверки
- •10.2. Стандартные процедуры и функции для строк
- •10.3. Хранение строк
- •Вопросы для самопроверки
- •Лабораторная работа №10 обработка символьной информации
- •Варианты заданий
- •11. Комбинированные типы. Записи (Record)
- •11.1 Записи с фиксированными частями
- •11.2. Оператор with…do
- •11.3. Вариантные записи
- •Вопросы для самопроверки
- •Лабораторная работа №11 Комбинированные типы. Записи
- •Варианты заданий
- •12. Файлы
- •12.1. Классификация файлов
- •12.1.1. Чтение файла
- •12.1.2. Запись файла
- •Вопросы для самопроверки
- •13.1. Объявление множества
- •13.2. Операции над множествами
- •13.3. Сравнение множеств
- •Include (s, I);
- •13.4. Старшинство множественных операций
- •Вопросы для самопроверки
- •Лабораторная работа №13 множества
- •Варианты заданий
- •Горячие клавиши
- •Библиографический список
- •Оглавление Введение 3
- •1. Программирование на языке Паскаль 5
- •1.1. Структура программы 5
- •2. Организация форматного вывода данных на языке Паскаль 17
- •Лабораторная работа №7_1.
- •Лабораторная работа №7_2.
- •Лабораторная работа №8_2.
8.4. Рекурсия
Рекурсивным называется объект, который частично определяется через самого себя. Рассмотрим функцию n!
n!:= 1 * 2 * 3 *..* n;
Такое произведение можно вычислить с помощью интерактивных циклических конструкций.
f:=l;
for i:=l to n do f := f * i;
Однако существует другое определение факториала, в котором используется рекуррентная формула. Тогда, факториал определяется следующим образом:
0! = 1;
для любого n > 0 n! = n* (n-1)!;
Организация вычисления по рекуррентным формулам можно и без использования рекурсий. Однако при этом встаёт вопрос о качестве программы и доказательстве её эквивалентности формы.
Использование рекурсии позволяет почти дословно запрограммировать вычисление по рекуррентным формулам.
Так, прямая формула чисел Фибоначчи:
F(1)=l;
F(2)=l;
для любого n > 0 F(n) = F(n-l) + F(n-2);
8.4.1. Вычисление факториала
Для написания рекурсивных алгоритмов необходимо и достаточно наличие понятия процедуры и функции.
Рекурсия - это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих её операторов обращается сама к себе.
Рассмотрим классический пример — вычисление факториала. Программа вводит с клавиатуры целое число N и выводит на экран значение n!, которое вычисляется с помощью рекурсивной функции Fасt. Для выхода из программы необходимо либо ввести достаточно большое целое число, чтобы вызвать переполнение при умножении чисел с плавающей запятой, либо нажать Ctrl-Z и Enter.
При выполнении правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В ниже приведённом примере решение при n=0 тривиально и используется для остановки рекурсии.
Пример 8.3.
Листинг программы
Program Factorial;
{$S+} {Включаем контроль переполнения стека}
var n : integer;
function Fасt (n : integer) :real;
{Рекурсивная функция, вычисляющая n!}
begin
if n < 0 then writeln ('Ошибка в задании N')
else
if n = 0 then Fact := 1
else Fact := n * Fact (n-1);
end;
begin
repeat
readln (n);
writeln ('n! = ', Fact (n));
until EOF;
end.
Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и даёт более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека (при каждом входе в программу её локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком). Переполнение стека особенно ощутимо сказывается при работе с сопроцессором: если программа использует арифметический сопроцессор, результат любой вещественной функции возвращается через аппаратный стек сопроцессора, рассчитанный всего на 8 уровней. Если, например, попытаться заменить тип real функции Fасt на Extended, программа перестанет работать уже при n = 8. Чтобы избежать переполнения стека сопроцессора, следует размещать промежуточные результаты во вспомогательной переменной. Правильный пример для работы с типом Extended:
Пример 8.4.
Листинг программы
Program Factorial; {$S+, $N+, $E+}
{Включаем контроль переполнения стека и работу сопроцессора}
var n : integer;
function Fact (n : integer) :real;
var F : extended;
{Рекурсивная функция, вычисляющая n!}
begin
if n < 0 then writeln ('Ошибка в задании N')
else
if n = 0 then Fact := 1
else
begin
F:= Fact (n-1);
Fact := F * n;
end;
end;
begin
repeat
readln (n);
writeln ('n! = ', Fact (n));
until EOF;
end.
Напишем процедуру, которая будет бесконечно печатать некоторую фразу. Обратим внимание, если операторы переставить.
Например,
Uses crt;
Procedure pop;
Begin
Writeln ('\У попа была собака...');
Pop;
End;
Begin
Pop;
End.
Но, если в теле процедуры изменить последовательность операторов:
Например,
Uses crt;
Procedure pop;
Begin
Pop;
Writeln ('У попа была собака...');
End;
Begin
Pop;
End.
Такое качество алгоритма вытекает из того, что рекурсивная процедура указывает, что нужно делать.
В нашем примере вызов копии процедуры происходит раньше, чем вызов процедуры.