Рекурсивные функции и алгоритмы. Примеры рекурсивных алгоритмов и программ

Рекурсия — ситуация, когда функция вызывает саму себя. Рекурсия, когда функция обращается сама к себе непосредственно, называется прямой; в противном случае она называется косвенной.

В функции должно присутствовать хотя бы одно условие завершения рекурсии.

Обработка вызова рекурсивной функции ничем не отличается от вызова обычной: перед вызовом функции в стек помещаются её аргументы, затем адрес точки возврата, затем, уже при выполнении функции — локальные переменные относительно этой функции. Но если при вызове обычных функций число обращений к ним невелико, то для рекурсивных функций число вызовов и, следовательно, количество данных, размещаемых в стеке, определяется глубиной рекурсии. Возможно переполнение стека.

Если попытаться отследить по тексту программы процесс выполнения рекурсивной функции, то мы придем к такой ситуации: войдя в рекурсивную функцию, мы “движемся” по ее тексту до тех пор, пока не встретим ее вызова, после чего мы опять начнем выполнять ту же самую функцию сначала. При этом следует отметить самое важное свойство рекурсивной функции — ее первый вызов еще не закончился. Чисто внешне создается впечатление, что текст функции воспроизводится (копируется) всякий раз, когда функция сама себя вызывает. На самом деле этот эффект воспроизводится в компьютере. Однако копируется при этом не весь текст функции (не вся функция), а только ее части, связанные с данными (формальные, фактические параметры, локальные переменные и точка возврата). Алгоритм (операторы, выражения) рекурсивной функции не меняется, поэтому он присутствует в памяти компьютера в единственном экземпляре.

int func(int n)

{

if (n == 0) // Условие выхода из рекурсии

return 1;

return n*func(n - 1);

}

6. Основные структуры данных — линейные односвязные и двусвязные списки. Основные операции. Примеры использования. Реализация в современных языках программирования (C#, C++ и Java).

Список — совокупность данных, структурные свойства которой ограничены лишь относительным расположением элементов. Это множество неопределенной длины с элементами, которые могут иметь как тождественный тип, так и разные типы.

Физическое расположение элементов в памяти никак не связано с их логическим положением. В массиве при i>j a[i] физически расположен в памяти раньше, чем a[j]. В списке этого не соблюдается. Сначала может в физической памяти располагаться a1, потом a100, потом a37 и т.д. Но заданные между элементами связи определяют их истинный последовательный логический порядок. В этом состоит принципиальное отличие списка от массива.

Самый простой способ связать множество элементов — сделать так, чтобы каждый элемент содержал ссылку на следующий. Такой список называется односвязным (однонаправленным).

Если добавить в каждый элемент вторую ссылку — на предыдущий элемент, получится двусвязный (двунаправленный) список. При этом первый элемент не имеет ссылки на предыдущий, что является признаком того, что этот элемент первый. Последний элемент не имеет ссылки на следующий (признак последнего элемента). Если последний элемент связать указателем с первым, получится кольцевой список.

Каждый элемент списка содержит ключ, идентифицирующий этот элемент. Ключ обычно бывает либо целым числом, либо строкой и является частью поля данных. В качестве ключа в процессе работы со списком могут выступать разные части поля данных. Например, если создается линейный список из записей, содержащих фамилию, год рождения, стаж работы и пол, любая часть записи может выступать в качестве ключа: при упорядочивании списка по алфавиту ключом будет фамилия, а при поиске, к примеру, ветеранов труда ключом будет стаж. Ключи разных элементов могут совпадать.

Основные операции над списками:

· начальное формирование списка (создание первого элемента);

· добавление элемента в конец списка;

· чтение элемента с заданным ключом;

· вставка элемента в заданное место списка (до и после элемента с заданным ключом);

· объединение двух списков;

· разбиение списка на два различных списка;

· удаление части списка;

· проход по списку;

· поиск элемента в списке;

· создание копии списка;

· определение количества элементов в списке;

· удаление элемента с заданным ключом;

· упорядочивание списка по ключу;

· удаление списка.

7. Основные структуры данных — деревья, бинарные деревья. Основные операции. Примеры использования. Реализация в современных языках программирования (C#, C++ и Java).

Дерево — структура, отображающая в памяти некоторый граф, не имеющий циклов и у которого в каждый узел входит не более одного ребра.

Бинарное дерево — это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья. На каждый узел имеется ровно одна ссылка. Начальный узел называется корнем дерева. Узел, не имеющий поддеревьев, называется листом. Исходящие узлы называются предками, входящие — потомками. Высота дерева определяется количеством уровней, на которых располагаются его узлы.

Если дерево организованно таким образом, что для каждого узла все ключи его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева — больше, оно называется деревом поиска. Одинаковые ключи не допускаются. В дереве поиска можно найти элемент по ключу, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значения ключа в каждом узле. Такой поиск гораздо эффективнее поиска по списку, поскольку время поиска определяется высотой дерева, а она пропорциональна двоичному логарифму количества узлов.

Дерево является рекурсивной структурой данных, поскольку каждое поддерево также является деревом. Действия с такими структурами изящнее всего описываются с помощью рекурсивных алгоритмов.

Дерево называется сбалансированным, когда для каждого узла высота его поддеревьев различается не более чем на 1. Дерево называется несбалансированным, когда длины правой и левой ветвей отличаются более чем на 1. Красным отмечен узел, для которого не выполняется условие сбалансированности.

Дерево называется идеально сбалансированным, если для каждого его узла количество узлов в его поддеревьях различается не более чем на 1.

Основные операции:

· создание дерева;

· включения узла в дерево;

· поиска по дереву;

· обхода дерева;

· определение количества узлов в дереве;

· удаление дерева;

· удаления узла.

Для каждого рекурсивного алгоритма можно создать его нерекурсивный эквивалент.

8. Основные структуры данных — стек, очередь. Операции над ними. Реализация в современных языках программирования (C#, C++ и Java).

Стек — динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.

Другие операции со стеком не определены. При выборке элемент исключается из стека. Говорят, что стек реализует принцип обслуживания LIFO (last in — first out, последним пришел — первым ушел). Стек проще всего представить себе как закрытую с одного конца узкую трубу, в которую бросают мячи. Достать первый брошенный мяч можно только после того, как вынуты все остальные. Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах.

Стек можно организовать на базе любой структуры данных, где возможно хранение нескольких однотипных элементов и где можно реализовать определение стека: линейный массив, типизированный файл, однонаправленный или двунаправленный список. В нашем случае наиболее подходящим для реализации стека является однонаправленный список, причём в качестве вершины стека выберем начало этого списка.

Основные операции над стеком и его элементами:

· добавление элемента в стек;

· удаление элемента из стека;

· проверка, пуст ли стек;

· просмотр элемента в вершине стека без удаления;

· очистка стека.

Очередь — частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка — из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Очередь реализует принцип обслуживания FIFO (first in — first out, первым пришел — первым ушел). Очередь проще всего представить себе, постояв в ней час-другой. В программировании очереди применяются, например, при моделировании, диспетчеризации задач ОС, буферизованном вводе/выводе.

Добавлять новые элементы можно только в конец очереди, забирать элементы можно только из начала. В отличие от обычной очереди, которую всегда можно при желании покинуть, из середины программистской очереди удалять элементы нельзя.

В случае очереди наиболее популярны две реализации: непрерывная на базе массива, которую называют также реализацией на базе кольцевого буфера, и ссылочная реализация, или реализация на базе списка.

Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать все элементы очереди, будем в отдельном поле m_start хранить индекс элемента массива, с которого начинается очередь. При удалении элементов, очередь будет "ползти" дальше от начала массива. Чтобы при этом не происходил выход за границы массива, замкнем массив в кольцо: будем считать, что за последним элементом массива следует первый.

9. Статические и виртуальные методы класса. Иерархические библиотеки классов.

Виртуальный метод — в объектно-ориентированном программировании метод класса, который может быть переопределён в классах-наследниках так, что конкретная реализация метода для вызова будет определяться во время исполнения. Т. о., программисту необязательно знать точный тип объекта для работы с ним через виртуальные методы: достаточно лишь знать, что объект принадлежит классу или наследнику класса, в котором метод объявлен. Виртуальные методы — один из важнейших приёмов реализации полиморфизма. Они позволяют создавать общий код, который может работать как с объектами базового класса, так и с объектами любого его класса-наследника. При этом, базовый класс определяет способ работы с объектами и любые его наследники могут предоставлять конкретную реализацию этого способа.

По умолчанию методы не являются виртуальными. Такой метод нельзя переопределить.

Ключевое слово virtual используется для изменения объявлений методов, свойств, индексаторов и событий и разрешения их переопределения в любом производном классе.

Модификатор override требуется для расширения или изменения абстрактной или виртуальной реализации унаследованного метода, свойства, индексатора или события.

Virtual нельзя использовать с модификаторами static, abstract, private или override.

Действие виртуальных свойств аналогично абстрактным методам, за исключением отличий в синтаксисе объявлений и вызовов.

Нельзя создавать экземпляры статического класса. Другими словами, нельзя использовать ключевое слово new для создания переменной типа класса. Поскольку нет переменной экземпляра, доступ к членам статического класса осуществляется с использованием самого имени класса.

Основные характеристики статического класса: содержит только статические члены, нельзя создавать экземпляры, он закрыт, не может содержать конструкторов экземпляров.

По сути, создания статического класса аналогично созданию класса, содержащего только статические члены и закрытый конструктор. Закрытый конструктор не допускает создания экземпляров класса.

Нестатический класс может содержать статические методы, поля, свойства или события. Статический член вызывается для класса даже в том случае, если не создано экземпляра класса. Доступ к статическому члену всегда выполняется по имени класса. Существует только одна копия статического члена, независимо от того, сколько создано экземпляров класса. Статические методы и свойства не могут обращаться к нестатическим полям и событиям, и они не могут обращаться к переменной экземпляра объекта, если он не передается явно в параметре метода.

Для объявления статических методов класса используется ключевое слово static перед возвращаемым типом члена.

Библиотека классов.NET Framework содержит все классы, интерфейсы и типы значений, входящие в Microsoft.NET Framework. Эта библиотека предоставляет разработчикам доступ к системным средствам. Она разрабатывалась как основа для создания приложений, компонентов и элементов управления.NET Framework.

В типах.NET Framework используется иерархическая схема именования с точкой. При таком подходе связанные типы группируются в пространства имен, что упрощает их поиск и создание ссылок. Первая часть полного имени — до крайней правой точки — это имя пространства имен. Последняя часть имени — это имя типа. Например System.Collections.ArrayList представляет собой тип ArrayList, который принадлежит пространству имен System.Collections. Типы в System.Collections можно использовать для работы с коллекциями объектов.

Такая схема именования упрощает разработчикам библиотек задачу расширения.NET Framework с целью создания иерархических групп типов и присвоения им согласованных между собой и понятных имен. Она также позволяет однозначно идентифицировать типы по их полным именам (то есть по пространству имен и имени типа), которые предотвращают конфликты имен типов.

При построении объектно-ориентированной программы рассматривается иерархия классов. Часто, например в ObjectWindows, можно рассматривать некоторую базовую иерархию классов или библиотеку. Библиотеки создаются опытными программистами. Можно непосредственно использовать библиотеку классов для решения разных задач, а также расширять и совершенствовать ее. Предположим, имеется некоторая иерархия библиотечных классов. В этом случае можно:

· определить объект для заданного класса;

· построить новый класс, наследуя его из существующего класса;

· изменить поведение нового класса (изменить его функции или добавить новые).

Когда строится новый класс, наследуемый из существующего, можно:

· добавить в новый класс новые компоненты-данные;

· добавить в новый класс новые компоненты-функции;

· заменить в новом классе наследуемые из старого класса компоненты-функции.

10. Абстрактные методы и абстрактные классы. Интерфейсы. Использование интерфейсов и абстрактных классов в современных языках программирования.

Класс — это шаблон, который позволяет создавать свои собственные пользовательские типы путем группирования переменных других типов, методов и событий.

Класс, содержащий хотя бы один чисто виртуальный метод, называется абстрактным. Абстрактные классы предназначены для представления общих понятий, которые предполагается конкретизировать в потомках. Абстрактный класс может использоваться только в качестве базового для других классов — объекты абстрактного класса создавать нельзя, поскольку прямой или косвенный вызов чисто виртуального метода приводит к ошибке при выполнении.

При определении абстрактного класса необходимо иметь в виду следующее:

· абстрактный класс нельзя использовать при явном приведении типов, для описания типа параметра и типа возвращаемого функцией значения;

· допускается объявлять указатели и ссылки на абстрактный класс, если при инициализации не требуется создавать временный объект;

· если класс, производный от абстрактного, не определяет все чисто виртуальные функции, он также является абстрактным.

Таким образом, можно создать функцию, параметром которой является указатель на абстрактный класс. На место этого параметра при выполнении программы может передаваться указатель на объект любого производного класса. Это позволяет создавать полиморфные функции, работающие с объектом любого типа.

Модификатор abstract в объявлении класса указывает, что класс предназначен только для использования в качестве базового класса для других классов. Члены, помеченные как абстрактные или включенные в абстрактный класс, должны быть реализованы с помощью классов, производных от абстрактных классов.

Особенности абстрактных классов:

· создавать экземпляры абстрактного класса нельзя;

· абстрактные классы могут содержать абстрактные методы и методы доступа;

· абстрактный класс с модификатором sealed изменить нельзя, поскольку эти два модификатора имеют взаимоисключающие значения. Модификатор sealed запрещает наследовать классу, в то время как модификатор abstract указывает, что класс обязан иметь производные классы;

· потомок абстрактного, должен содержать фактические реализации всех наследуемых абстрактных методов и методов доступа.

Возможности абстрактных методов.

· абстрактный метод является неявным виртуальным методом;

· объявления абстрактных методов допускаются только в абстрактных классах.

Поскольку объявление абстрактного метода не предоставляет фактической реализации, тело метода отсутствует; объявление метода просто заканчивается двоеточием, а после сигнатуры ставить фигурные скобки не нужно. Реализация предоставляется методом переопределения override, который является членом неабстрактного класса. Использование статических или виртуальных модификаторов в объявлении абстрактного метода является недопустимым.

Интерфейс содержит только сигнатуры методов, свойств, событий или индексаторов. Класс или структура, которые реализуют интерфейс, должны реализовать члены этого интерфейса, указанные в его определении.

Класс или интерфейс может наследовать нескольких интерфейсов.

Если в списке базовых типов содержится базовый класс и интерфейсы, то базовый класс должен стоять в списке на первом месте.

Класс, реализующий интерфейс, может явным образом реализовывать члены этого интерфейса. Явно реализованный член можно вызвать только через экземпляр интерфейса, но не через экземпляр класса.

Абстрактный класс содержит по крайней мере один абстрактный метод (остальные методы могут быть нормальными, а интерфейс по определению не содержит не-абстрактных методов.

class Account {

public:

Account(double d); // Constructor.

virtual double GetBalance(); // Obtain balance.

virtual void PrintBalance() = 0; // Pure virtual function.

private:

double _balance;

};

interface Interface_A {

void Function_2();

};