Слияние

Под слиянием понимается объединение двух (или более) упорядоченных последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Слияние - намного более простая операция, чем сортировка.Прямое слияние. Алгоритм Боуза - Нельсона

Вопрос№51_2

1. Последовательность а разбивается на две половины b и с.

2. Последовательности b и с сливаются при помощи объединения отдельных элементов в упорядоченные пары.

3. Полученной последовательности присваивается имя а, после чего повторяются шаги 1 и 2; при этом упорядоченные пары сливаются в упорядоченные четверки.

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

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

Рекурсия

Рекурсия - это одна из фундаментальных концепций в математике и программировании, Рекурсия - это одна из форм мышления, это мощное средство, позволяющее строить элегантные и выразительные алгоритмы.

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

Если процедура р содержит явное обращение к самой себе, то она называется явно рекурсивной. Если процедура р содержит обращение    к некоторой процедуре q, которая в свою очередь содержит прямое или косвенное обращение к р, то р - называется косвенно рекурсивной.

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

Реккурентность - это рекурсивное определение функции. Они широко распространены в математике. Возможно наиболее знакомая Вам из такого рода функций - это факториал. Факториал - это произведение натуральных чисел от единицы до какого - либо данного натурального числа. Он определяется формулой:

N!=N((N-1)!,     для N>=1 и 0! = 1.

Это напрямую соответствует нижеследующей рекурсивной программе:

function factorial( N : integer ) : integer; begin     if N=0 then         factorial := 1     else         factorial := N * factorial(N-1); end;

Эта программа демонстрирует основные свойства рекурсивных программ: программа вызывает сама себя (с меньшим значением аргумента), и у нее есть терминальное условие при котором она прямо вычисляет результат.

Вопрос№52 Основы объектно-ориентированного программирования. (инкапсул., полиморфизм, наследов.)

   Объектно-ориентированное программирование - это методология построения программ, являющаяся дальнейшим развитием методологии структурного программирования и методов абстрагирования данных. Объектно-ориентированное программирование (ООП) - это метод программирования, имитирующий способы, какими, по нашим представлениям, выполнены те или иные объекты. ООП более структурировано, модульно и абстрактно, чем предыдущие попытки в абстрагировании данных и сокрытии деталей.

   Основными понятиями ООП являются:

1. объект - совокупность свойств (параметров) определенных сущностей и методов их обработки (программных средств). Объект содержит инструкции (программный код), определяющие действия, которые может выполнять объект, и обрабатываемые данные;

2. свойство - характеристика объекта, его параметр. Все объекты наделены определенными свойствами, которые в совокупности выделяют объект из множества других;

   Одним из свойств объекта является метод его обработки. Метод - программа действий над объектом или его свойствами. Метод рассматривается как программный код, связанный с определенным объектом; осуществляет преобразование свойств, изменяет поведение объекта.

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

   По мере развития систем обработки данных создаются стандартные библиотеки методов, в состав которых включаются типизированные методы обработки объектов определенного класса (аналог - стандартные подпрограммы обработки данных при структурном подходе), которые можно заимствовать для различных объектов.

3. событие - изменение состояния объекта. Внешние события генерируются пользователем (например, клавиатурный ввод или нажатие кнопки мыши, выбор пункта меню и т.д.); внутренние события генерируются системой.

   Объекты могут объединяться в классы (группы или наборы - в различных программных системах возможна другая терминология).

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

  Три основных свойства характеризуют язык объектно - ориентированного программирования:

• инкапсуляция - это объединение в одном программном модуле данных и процедур их обработки. Это свойство превращает их в новый тип данных - object (объект), который по аналогии с типом данных record (записи) содержит поля данных (определяющих свойства или атрибуты объекта) и, кроме того, включает описания процедур и функций (определяющих поведение объекта), т.е. процедуры и функции существуют не отдельно в программе, а инкапсулированы (встроены) в описание соответствующего объекта. Явление инкапсуляции дает возможность рассматривать объект как единое целое в неразрывной связи всех его свойств и поведения;

• наследование - это заимствование и преемственность атрибутов и поведения от объекта к объекту, т.е. из объектов можно строить иерархические структуры типов данных, например:    При этом любой объект-потомок наследует поля данных, процедуры и функции своего объекта-предка: у объекта-потомка имеются, кроме объявленных дополнительно, все те же поля данных, процедуры и функции (и с теми же именами), что и у породившего его объекта-предка. Иными словами наследование в ООП служит для использования однажды определенного объекта в построении целой иерархии производных объектов, каждый из которых наследует доступ к данным и методам работы с ними всех своих так называемых "прародителей";

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

   Возможен же полиморфизм благодаря позднему связыванию - компоновке программы на этапе ее выполнения