АЛГОРИТМ СОРТИРОВКИ МЕТОДОМ ВСТАВКИ

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

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

procedure Сортировка (< список> ) assign N the value 2;

while (значение N не превышает < длина списка> )

do (Выбрать N-й элемент списка в качестве опорного; Переместить этот элемент во временное хранилище, оставив в списке пустое место;

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

do (переместить имя, находящееся над пустым местом вниз, оставив в прежней позиции пустое место); Поместить опорный элемент на пустое место в списке assign N the value N+1

здесь N - счетчик, параметр < длина списка> - количество эле­ментов в списке.

Программа сортирует список, многократно повторяя следую­щие действия: «Элемент извлекается из списка, а затем вставляется на надлежащее ему место».

Каждое выполнение тела внешнего цикла приводит к тому, что внутренний цикл инициализируется и выполняется до тех пор, пока не будет выполнено условие его окончания. Условие окончания внешнего цикла выполняется, когда значение счетчика N превысит длину сортируемого списка.

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

15. Модульное программирование

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

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

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

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

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

Среди множества модулей различают:

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

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

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

Модуль должен обладать следующими свойствами:

• один вход и один выход – на входе программный модуль получает определенный набор исходных данных, выполняет содержательную обработку и возвращает один набор результатных данных, т.е. реализуется стандартный принцип IPO ( Input–Process–Output – вход-процесс-выход);
• функциональная завершенность – модуль выполняет перечень регламентированных операций для реализации каждой отдельной функции в полном составе, достаточных для завершения начатой обработки;
• логическая независимость – результат работы программного модуля зависит только от исходных данных, но не зависит от работы других модулей;
• слабые информационные связи с другими программными модулями – обмен информацией между модулями должен быть по возможности минимизирован;
• обозримый по размеру и сложности программный код.

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

Модули содержат:

• определение доступных для обработки данных;
• операции обработки данных;
• схемы взаимосвязи с другими модулями.

Каждый модуль состоит из спецификации и тела. Спецификации определяют правила использования модуля, а тело – способ реализации процесса обработки.

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

При определении набора модулей, реализующих функции конкретного алгоритма, необходимо учитывать следующее:

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

В результате дальнейшей детализации алгоритма создается функционально-модульная схема ( ФМС ) алгоритма приложения, являющаяся основой для программирования (рис. 2).

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

Рис. 3. Функционально-модульная структура алгоритма приложения

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

• точки (момент, условие) начала диалога;
• инициатор диалога – человек или программный продукт;
• параметры и содержание диалога – сообщения, состав и структура меню, экранные формы и т.п.;
• реакция программного продукта на завершение диалога.

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

Графический интерфейс пользователя ( GUI, Graphics User Interface) является обязательным компонентом большинства современных программных продуктов, ориентированных на работу конечного пользователя.

 

 

16. Нисходящее проектирование

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

Спецификация задачи является ее первичным проектом. От неё мы движемся к программе, постепенно уточняя описание.

Постепенное уточнение проекта называется методом проектирования сверху вниз (пошаговой детализации или нисходящего проектирования).

Пример 1. В качестве примера рассмотрим проект одевания ребенка.

Решение:

1. Первичная цель:

Одеть.

2. Конкретизация цели на первом шаге:

Одеть нижнюю половину.

Одеть верхнюю половину.

2.1. Нижнюю половину можно одеть в два этапа:

Надеть брюки.

Надеть носки и ботинки.

2.2. Верхнюю половину можно также одеть в два этапа:

Надеть рубашку.

Надеть куртку.

3. Окончательный проект выглядит так:

Надеть брюки.

Надеть носки.

Надеть ботинки.

Надеть рубашку.

Надеть куртку.

Метод нисходящего проектирования предполагает последовательное разложение общей функции обработки данных на простые функциональные элементы («сверху-вниз»). В результате строится иерархическая схема – функциональная структура алгоритма ( ФСА ), отражающая состав и взаимоподчиненность отдельных функций (рис. 2).

Рис. 2. Функциональная структура приложения

Последовательность действий по разработке ФСА приложения следующая:

1. определяются цели автоматизации предметной области и их иерархия (цель-подцель);

2. устанавливается состав приложений (задач обработки), обеспечивающих реализацию поставленных целей;

3. уточняется характер взаимосвязи приложений и их основные характеристики (информация для решения задач, время и периодичность решения, условия выполнения и др.);

4. определяются необходимые для решения задач функции обработки данных;

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

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

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

Функции ввода-вывода информации рекомендуется отделять от функций вычислительной или логической обработки данных.

По частоте использования функции обработки делятся на:

• однократно выполняемые;
• повторяющиеся.

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

17. Структурное кодирование

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

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

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

Свойство структурности операторов состоит в том, что каждый оператор имеет один вход и один выход. Программа, построенная из структурных операторов, называется структурированной.

Фундаментом структурного программирования является теорема о структурировании, сформулированная итальянскими математиками К.Бомом и Дж.Якопини в 1966 г.

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

• следования ( begin-end – начало-конец),
• ветвления ( if - then - else – если-то-иначе),
• циклов с предусловием ( while – пока).

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

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

 

18. ООП

19. Основные понятия ООП

1. Класс. Представьте себе, что вы являетесь конструктором и собираетесь спроектировать легковой автомобиль. Вы знаете, что автомобиль должен содержать кузов, двигатель, подвеску, две передних фары, 4 колеса, и т.д. Ещё вы знаете, что автомобиль должен иметь возможность набирать и сбавлять скорость, совершать поворот и двигаться задним ходом. И, что самое главное, вы точно знаете, как взаимодействует двигатель и колёса, согласно каким законам движется распредвал и коленвал, а также как устроены дифференциалы. Вы уверены в своих знаниях и начинаете проектирование.

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

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

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

Класс = Набор данных + Методы

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

В нашем случае, класс будет отображать сущность – автомобиль.

Атрибуты класса «Автомобиль»: кузов, двигатель, подвеска, четыре колеса и т.д.

Методы класса «Автомобиль»: открыть дверь, нажать на педаль газа, а также «закачать порцию бензина из бензобака в двигатель».

Очевидно, что первые два метода доступны для выполнения другим классам (в частности, классу «Водитель» ). Последний описывает взаимодействия внутри класса и не доступен пользователю.

2. Объект. Вы отлично потрудились и автомобили, разработанные по вашим чертежам, сходят с конвейера. Вот они, стоят ровными рядами на заводском дворе. Каждая из них точно повторяет ваши чертежи. Все системы взаимодействуют именно так, как вы спроектировали. Но каждая машина уникальна. Они все имеют номер кузова и двигателя, но все эти номера разные, автомобили различаются цветом, а некоторые даже имеют литьё вместо штампованных дисков. Эти автомобили, по сути, являются объектами вашего класса.

Объект ( экземпляр ) – это отдельный представитель класса, имеющий конкретное состояние и поведение, полностью определяемое классом.

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

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

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

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

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

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

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

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

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

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

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

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

Инкапсуляция – это свойство системы, позволяющее объединить данные и методы, работающие с ними, в классе и скрыть детали реализации от пользователя.

Инкапсуляция неразрывно связана с понятием интерфейса класса. По сути, всё то, что не входит в интерфейс, инкапсулируется в классе.

5. Абстракция. Представьте, что водитель едет в автомобиле по оживлённому участку движения. Понятно, что в этот момент он не будет задумываться о химическом составе краски автомобиля, особенностях взаимодействия шестерён в коробке передач или влияния формы кузова на скорость (разве что, автомобиль стоит в глухой пробке и водителю абсолютно нечем заняться). Однако, руль, педали, указатель поворота (ну и, возможно, пепельницу) он будет использовать регулярно.

Абстрагирование – это способ выделить набор значимых характеристик объекта, исключая из рассмотрения незначимые. Соответственно, абстракция – это набор всех таких характеристик.

6. Полиморфизм. Любое обучение вождению не имело бы смысла, если бы человек, научившийся водить, скажем, ВАЗ 2106 не мог потом водить ВАЗ 2110 или BMW X3. С другой стороны, трудно представить человека, который смог бы нормально управлять автомобилем, в котором педаль газа находится левее педали тормоза, а вместо руля – джойстик.

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

Если человеку надо доехать с работы до дома, то он сядет за руль автомобиля и будет выполнять одни и те же действия, независимо от того, какой именно тип автомобиля он использует. По сути, можно сказать, что все автомобили имеют один и тот же интерфейс, а водитель, абстрагируясь от сущности автомобиля, работает именно с этим интерфейсом. Если водителю предстоит ехать по немецкому автобану, он, вероятно, выберет быстрый автомобиль с низкой посадкой, а если предстоит возвращаться из отдалённого маральника в Горном Алтае после дождя, скорее всего, будет выбран УАЗ с армейскими мостами. Но, независимо от того, каким образом будет реализовываться движение и внутреннее функционирование машины, интерфейс останется прежним.

Полиморфизм (многообразие) – это свойство системы использовать объекты с одинаковым интерфейсом без информации о типе и внутренней структуре объекта.

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

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

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

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

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

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

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

⇐ Предыдущая123456Следующая ⇒

Поделиться: