- •Технология подготовки и решения задач с помощью компьютера
- •Базовые конструкции для написания структурированных программ. Способы обращения неструктурированных программ в структурированные.
- •Ввод и вывод данных, оператор присваивания.
- •Условный оператор: группа If
- •Цикл с параметром: группа For
- •Цикл с параметром: While, Repeat
- •Контрольные вопросы:
- •Пошаговая детализация алгоритма
- •Процедуры и функции
- •Контрольные вопросы.
- •Структуры данных: массивы, строки, записи. Размещение в памяти. Пользовательские типы данных.
- •Контрольные вопросы.
- •Модульное программирование. Организация личных библиотек.
- •Контрольные вопросы:
- •Рекурсивные алгоритмы
- •Контрольные вопросы.
- •Сортировка и поиск. Методы внутренней сортировки.
- •Быстрые алгоритмы сортировки
- •Контрольные вопросы
- •Статистическое и динамическое распределение памяти. Динамические структуры данных.
- •Контрольные вопросы.
- •Алгоритмы с возвращением.
- •Поиск в глубину
- •Поиск в ширину
- •Деревья
- •Достижимость
- •Метод построения максимального потока в сети
- •Метод локальной оптимизации
- •Организация файловой системы. Создание и обработка баз данных.
- •Варианты
- •Контрольные вопросы:
- •Библиотечные модули системы программирования Паскаль: Crt, Dos, Graph.
- •Графический режим работы экрана
- •Основные графические функции и процедуры
- •Контрольные вопросы:
- •Комбинаторные алгоритмы.
- •Перебор с возвратом. Общая схема
- •Задача о рюкзаке (перебор вариантов)
- •Задача о коммивояжере (перебор вариантов)
- •Объектно-ориентированное программирование
Контрольные вопросы:
Что такое модуль?
Какие существуют стандартные модули в системе Paskal?
Файл какого типа получается после трансляции модуля Paskal?
Какова структура модуля в Paskal?
Каково назначение интерфейсного разделяя модуля?
На какие типы можно разделить модули?
Рекурсивные алгоритмы
Цель: Сформировать умения решать нетиповые задачи с использованием рекурсивных процедур и функций
Рекурсия - вызов функции самой себя. Различают два вида рекурсии:
прямая рекурсия;
косвенная рекурсия.
Прямая рекурсия - функция вызывает непосредственно саму себя. Изображение прямой рекурсии на функциональной схеме программы приведено на рис. 5.1.
Рис. 5.1 - Изображение прямой рекурсии
Косвенная рекурсия - функция вызывает себя посредством другой функции. Например, функция А вызывает функцию Б, которая, в свою очередь, вызывает функцию А. Изображение косвенной рекурсии на функциональной схеме программы приведено на рисунке 5.2.
ПРИМЕЧАНИЕ: Косвенная рекурсия на практике используется довольно редко, и здесь рассматриваться не будет.
Рис. 5.2 - Изображение косвенной рекурсии
В качестве примера прямой рекурсии рассмотрим рекурсивную функцию вычисления факториала:
function fact(n:byte):longint;
begin
if n=1 then fact:=1
else fact:=n*fact(n-1);
end;
В первой строчке тела функции осуществляется проверка выхода из рекурсии: факториал числа один равен самому числу. Во второй строчке осуществляется умножение значения параметра n, приведенного к вещественному числу, на рекурсивный вызов функции, в которую в качестве параметра передается значение n уменьшенное на один.
Таким образом, вычисление, например, факториала числа пять будет иметь следующую последовательность вызовов:
Fact(5)
5*Fact(4)
4*Fact(3)
3*Fact(2)
2*Fact(1)
1
Рекурсия может оказаться несовместной с экономией памяти, так как каждом вызове функции в стек помещается адрес возврата и параметры функции, что приводит к быстрому использованию отведенной под стек памяти и, как следствие, его переполнению.
Рекурсия также не дает выигрыша в производительности. Но рекурсивный код обычно компактнее, и его значительно легче писать и дорабатывать, чем его аналог без рекурсии. Рекурсия особенно удобна при работе с рекурсивно определенными структурами данных наподобие деревьев.
Задания:
Необходимо разработать программу согласно варианту задания. При написании программы реализовать рекурсивную функцию. Работу рекурсивной функции продемонстрировать в функции main. Программу реализовать в диалоговом режиме: запрос данных - вывод ответа. После каждого вывода ответа запрашивать у пользователя выход и, в случае положительного ответа, осуществлять завершение программы.
Вычислить сумму ряда с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно.
Вычислить сумму ряда с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно.
Вычислить сумму ряда с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно.
Вычислить сумму ряда с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно.
Вычислить сумму ряда с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно.
Реализовать рекурсивную функцию, находящую значение n-й степени числа x по формуле: x0=1, xn = x·xn-1 при n > 0, xn=1/x-n при n<0 (x>=0 - вещественное число, n - целое).
Реализовать рекурсивную функцию, находящую приближенное значение корня k-й степени из числа x по формуле: y(0) = 1, y(n+1)=y(n)-[y(n) - x / y(n)k-1]/k, (x - вещественный параметр, k и n - целые; x > 0, k > 1, n > 0).
Реализовать рекурсивную функцию C(m,n) целого типа, находящую число сочетаний из n элементов по m, используя формулу: C(0,n) = C(n,n) = 1, C(m,n) = C(m,n-1) + C(m-1,n-1) при 0<m<n (m и n - целые параметры; n>0, 0<=m<=n).
Реализовать рекурсивную функцию NOD(A,B) целого типа, находящую наибольший общий делитель двух натуральных чисел A и B, используя алгоритм Евклида: NOD(A,B) = NOD(B mod A,A), если A <> 0; NOD(0,B) = B.
Реализовать рекурсивную функцию вычисления n-го числа из последовательности Фибоначчи по формуле: Fin(1)=1; Fib(n)=Fib(n-1)+Fib(n-2).
Дан массив целых положительных чисел (размер и элементы массива вводит пользователь) и целое число. Расставить операции сложения и вычитания между элементами массива так, чтобы получилось верное равенство с введенным целым значением.