По материалам публикации "Е.А. Ерёмин, А.П. Шестаков. Примерные ответы на профильные билеты." //Информатика, 2006-2007
Программирование — сравнительно молодая и быстро развивающаяся отрасль науки и техники. Опыт ведения реальных разработок и совершенствования имеющихся программных и технических средств постоянно переосмысливается, в результате чего появляются новые методы, методологии и технологии, которые, в свою очередь, служат основой более современных средств разработки программного обеспечения. Исследовать процессы создания новых технологий и определять их основные тенденции целесообразно, сопоставляя эти технологии с уровнем развития программирования и особенностями имеющихся в распоряжении программистов программных и аппаратных средств.
Технологией программирования называют совокупность методов и средств, используемых в процессе разработки программного обеспечения. Как любая другая технология, технология программирования представляет собой набор технологических инструкций, включающих:
Кроме набора операций и их последовательности, технология также определяет способ описания проектируемой системы, точнее модели, используемой на конкретном этапе разработки.
Различают технологии, используемые на конкретных этапах разработки или для решения отдельных задач этих этапов, и технологии, охватывающие несколько этапов или весь процесс разработки. В основе первых, как правило, лежит ограниченно применимый метод, позволяющий решить конкретную задачу. В основе вторых обычно лежит базовый метод или подход (парадигма), определяющий совокупность методов, используемых на разных этапах разработки, или методологию.
Исторически в развитии программирования можно выделить несколько принципиально отличающихся методологий.
Изначально понятие технологии как таковой — это 60-е годы прошлого столетия — это период "стихийного" программирования. В этот период отсутствовало понятие структуры программы, типов данных и т.д. Вследствие этого код получался запутанным, противоречивым. Программирование тех лет считалось искусством. Конец 60-х — кризис в программирование.
Выход из этого кризиса — переход к структурной парадигме программирования. Структурный подход к программированию представляет собой совокупность рекомендуемых технологических приемов, охватывающих выполнение всех этапов разработки программного обеспечения. В основе структурного подхода лежит декомпозиция (разбиение на части) сложных систем с целью последующей реализации в виде отдельных небольших подпрограмм. С появлением других принципов декомпозиции (объектного, логического и т.д.) данный способ получил название процедурной декомпозиции.
Другим базовым принципом структурного программирования является использование при составлении программ только базовых алгоритмических структур (см. билет 4), запрет на использование оператора GOTO.
Структурный подход требовал представления задачи в виде иерархии подзадач простейшей структуры. Проектирование осуществлялось "сверху-вниз" и подразумевало реализацию общей идеи, обеспечивая проработку интерфейсов подпрограмм. Одновременно вводились ограничения на конструкции алгоритмов, рекомендовались формальные модели их описания, а также специальный метод проектирования алгоритмов — метод пошаговой детализации.
Поддержка принципов структурного программирования была заложена в основу так называемых процедурных языков программирования. Как правило, они включали основные "структурные" операторы передачи управления, поддерживали вложение подпрограмм, локализацию и ограничение области "видимости" данных. Среди наиболее известных языков этой группы стоит назвать PL/1, ALGOL-68, Pascal, С.
Дальнейший рост сложности и размеров разрабатываемого программного обеспечения потребовал развития структурирования данных. Как следствие этого в языках появляется возможность определения пользовательских типов данных. Одновременно усилилось стремление разграничить доступ к глобальным данным программы, чтобы уменьшить количество ошибок, возникающих при работе с глобальными данными. В результате появилась и стала развиваться технология модульного программирования.
Модульное программирование предполагает выделение групп подпрограмм, использующих одни и те же глобальные данные, в отдельно компилируемые модули (библиотеки подпрограмм), например, модуль графических ресурсов. Связи между модулями при использовании данной технологии осуществляются через специальный интерфейс, в то время как доступ к реализации модуля (телам подпрограмм и некоторым "внутренним" переменным) запрещен. Эту технологию поддерживают современные версии языков Pascal и С (C++), языки Ада и Modula.
Объектно-ориентированное программирование (ООП) определяется как технология создания сложного программного обеспечения, основанная на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определенного типа (класса), а классы образуют иерархию с наследованием свойств. Взаимодействие программных объектов в такой системе осуществляется путем передачи сообщений.
Основным достоинством объектно-ориентированного программирования по сравнению с модульным программированием является "более естественная" декомпозиция программного обеспечения, которая существенно облегчает его разработку. Это приводит к более полной локализации данных и интегрированию их с подпрограммами обработки, что позволяет вести практически независимую разработку отдельных частей (объектов) программы. Кроме этого, объектный подход предлагает новые способы организации программ, основанные на механизмах наследования, полиморфизма, композиции, наполнения. Эти механизмы позволяют конструировать сложные объекты из сравнительно простых. В результате существенно увеличивается показатель повторного использования кодов и появляется возможность создания библиотек классов для различных применений.
Бурное развитие технологий программирования, основанных на объектном подходе, позволило решить многие проблемы. Так были созданы среды, поддерживающие визуальное программирование, например, Delphi, C++ Builder, Visual C++ и т. д. При использовании визуальной среды у программиста появляется возможность проектировать некоторую часть, например, интерфейсы будущего продукта, с применением визуальных средств добавления и настройки специальных библиотечных компонентов. Результатом визуального проектирования является заготовка будущей программы, в которую уже внесены соответствующие коды.
Можно дать обобщающее определение: объект ООП — это совокупность переменных состояния и связанных с ними методов (операций). Упомянутые методы определяют, как объект взаимодействует с окружающим миром.
Под методами объекта понимают процедуры и функции, объявление которых включено в описание объекта и которые выполняют действия. Возможность управлять состояниями объекта посредством вызова методов в итоге и определяет поведение объекта. Эту совокупность методов часто называют интерфейсом объекта.
Инкапсуляция — это механизм, который объединяет данные и методы, манипулирующие этими данными, и защищает и то и другое от внешнего вмешательства или неправильного использования. Когда методы и данные объединяются таким способом, создается объект.
Применяя инкапсуляцию, мы защищаем данные, принадлежащие объекту, от возможных ошибок, которые могут возникнуть при прямом доступе к этим данным. Кроме того, применение этого принципа очень часто помогает локализовать возможные ошибки в коде программы. А это намного упрощает процесс поиска и исправления этих ошибок. Можно сказать, что инкапсуляция подразумевает под собой скрытие данных, что позволяет защитить эти данные. Однако применение инкапсуляции ведет к снижению эффективности доступа к элементам объекта. Это обусловлено необходимостью вызова методов для изменения внутренних элементов (переменных) объекта. Но при современном уровне развития вычислительной техники эти потери в эффективности не играют существенной роли.
Наследование — это процесс, посредством которого один объект может наследовать свойства другого объекта и добавлять к ним черты, характерные только для него. В итоге создаётся иерархия объектных типов, где поля данных и методов "предков" автоматически являются и полями данных и методов "потомков".
Смысл и универсальность наследования заключается в том, что не надо каждый раз заново ("с нуля") описывать новый объект, а можно указать "родителя" (базовый класс) и описать отличительные особенности нового класса. В результате новый объект будет обладать всеми свойствами родительского класса плюс своими собственными отличительными особенностями.
Полиморфизм — это свойство, которое позволяет одно и тоже имя использовать для решения нескольких технически разных задач. Полиморфизм подразумевает такое определение методов в иерархии типов, при котором метод с одним именем может применяться к различным родственным объектам. В общем смысле концепцией полиморфизма является идея "один интерфейс — множество методов". Преимуществом полиморфизма является то, что он помогает снижать сложность программ, разрешая использование одного интерфейса для единого класса действий. Выбор конкретного действия, в зависимости от ситуации, возлагается на компилятор.
Современная технология программирования — компонентный подход, который предполагает построение программного обеспечения из отдельных компонентов — физически отдельно существующих частей программного обеспечения, которые взаимодействуют между собой через стандартизованные двоичные интерфейсы. В отличие от обычных объектов объекты-компоненты можно собрать в динамически вызываемые библиотеки или исполняемые файлы, распространять в двоичном виде (без исходных текстов) и использовать в любом языке программирования, поддерживающем соответствующую технологию. На сегодня рынок объектов стал реальностью. Это позволяет программистам создавать продукты, хотя бы частично состоящие из повторно использованных частей, т.е. использовать технологию, хорошо зарекомендовавшую себя в области проектирования аппаратуры.
Компонентный подход лежит в основе технологий, разработанных на базе COM (Component Object Model — компонентная модель объектов), и технологии создания распределенных приложений CORBA (Common Object Request Broker Architecture — общая архитектура с посредником обработки запросов объектов). Эти технологии используют сходные принципы и различаются лишь особенностями их реализации.
Технология СОМ фирмы Microsoft является развитием технологии OLE (Object Linking and Embedding — связывание и внедрение объектов), которая использовалась в ранних версиях Windows для создания составных документов. Технология СОМ определяет общую парадигму взаимодействия программ любых типов: библиотек, приложений, операционной системы, т. е. позволяет одной части программного обеспечения использовать функции (службы), предоставляемые другой, независимо от того, функционируют ли эти части в пределах одного процесса, в разных процессах на одном компьютере или на разных компьютерах. Модификация СОМ, обеспечивающая передачу вызовов между компьютерами, называется DCOM (Distributed COM — распределенная СОМ).
Таковы, вкратце, основные этапы изменения технологий программирования. Поскольку программное обеспечение на сегодняшний день используется в самых различных устройствах и сферах деятельности человека, то можно прогнозировать дальнейшее совершенствование технологий программирования.
Обсудим далее то, что, в конечном итоге, является "кирпичиками", строительным материалом любой программы — подпрограммы и варианты их реализации на примере языка Pascal — процедуры и функции.
При решении новых задач можно попытаться воспользоваться ранее написанными программами. Алгоритм, ранее разработанный и целиком используемый в составе других алгоритмов, называется вспомогательным. Применение вспомогательных алгоритмов позволяет разбить задачу на части, структурировать ее.
Вся программа условно может быть разделена на две части: основную и вспомогательную. В основной части производится простейшая обработка информации, организуется обращение к разным подпрограммам. Вспомогательный алгоритм тоже может вызывать другие вспомогательные, длина такой цепочки вызовов теоретически не ограничена. Вспомогательными и основными алгоритмы являются не сами по себе, а по отношению друг к другу.
При использовании вспомогательных алгоритмов необходимо учитывать способ передачи значений исходных данных для них и получения результата от них. Аргументы вспомогательного алгоритма — это переменные, в которых должны быть помещены исходные данные для решения соответствующей подзадачи. Результаты вспомогательного алгоритма — это также переменные, где содержатся результаты решения этих подзадач, а также результатом может быть конкретное действие, которое совершает компьютер под действием подпрограммы.
Подпрограммы могут быть двух видов: подпрограмма без параметров и подпрограмма с параметрами. Обращение к подпрограмме может быть организовано из любого места основной программы или другой подпрограммы сколько угодно раз.
При работе с подпрограммами важными являются понятия формальных и фактических параметров. Формальные параметры — это идентификаторы входных данных для подпрограммы. Если формальные параметры получают конкретные значения, то они называются фактическими. Формальные параметры могут получить конкретные значения только в той программе, где производится обращение к данному модулю-подпрограмме. Тип и порядок записи, а также семантическое (смысловое) наполнение фактических параметров должны быть такими же, как и формальных параметров. В противном случае результат работы программы будет непредсказуемым. Из этого следует, что фактические параметры используются при обращении к подпрограмме из основной, а формальные параметры — только в самой подпрограмме.
Подпрограмма с параметрами используется для записи многократно повторяющихся действий при разных исходных данных. Подпрограммы с параметрами можно разделить на два типа: подпрограммы-функции и просто подпрограммы с параметрами (их называют процедурами).
При составлении подпрограмм с параметрами надо соблюдать следующие правила:
Пример 1. Используем алгоритм нахождения наибольшего общего делителя двух натуральных чисел в качестве вспомогательного при решении задачи: составить программу вычитания дробей (a, b, c, d — натуральные числа). Результат представить в виде обыкновенной несократимой дроби.
Program Sub;
Var A, B, C, D, G, E, F : Integer;
Procedure Nod(M, N : Integer; Var K : Integer);
Begin
While M <> N Do
If M > N Then M := M - N Else N := N - M;
K := M
End;
Begin
Write('Введите числители и знаменатели дробей:');
ReadLn(A, B, C, D);
E := A * D - B * C;
F := B * D;
If E = 0 Then WriteLn(E)
Else
Begin
Nod(Abs(E), F, G);
E := E Div G;
F := F Div G;
WriteLn('Ответ: ', E, '/', F)
End
End.
Как видно из примера, объявление и тело подпрограмм находится в разделе описаний. В заголовке подпрограммы содержится список формальных параметров с указанием их типа, которые условно можно разделить на входные и выходные (перед ними стоит служебное Var). При обращении к процедуре указывается ее имя и список фактических параметров. Формальные и фактические параметры должны соответствовать по количеству и по типу.
Вызов процедуры осуществляется следующим образом:
<Идентификатор (имя) процедуры>(<список фактических параметров>);
Например,
Nod(Abs(E), F, G);
По способу передачи фактических значений в подпрограмму в Turbo Pascal выделяют параметры-переменные, параметры-значения, параметры-константы. Есть и другие способы, которые менее актуальны
Функция (в отличие от процедуры) всегда возвращает единственное значение.
Покажем, как изменится подпрограмма из примера, если ее записать в виде функции.
Function Nod(M, N : Integer) : Integer;
Begin
While M <> N Do
If M > N Then M := M - N Else N := N - M;
Nod := M
End;
Итак, после списка параметров указывается тип значения функции, а в теле функции хотя бы один раз встречается присваивание переменной, имя которой совпадает с именем функции, соответствующего значения.
Вызов функции будет следующим:
G := Nod(Abs(E), F);
Вообще, вызов функции может присутствовать в выражении, стоящем: в правой части оператора присваивания, в процедуре вывода, в качестве фактического параметра в вызове другой подпрограммы и т.д.
При решении задач целесообразно проанализировать условие, записать решение в крупных блоках (не являющихся операторами Pascal), детализировать каждый из блоков (записав в виде блоков, возможно, по-прежнему не операторов Pascal), и т.д., продолжать до тех пор, пока каждый из блоков не будет реализован с помощью операторов языка.
Пример 2. Дано натуральное число n. Переставить местами первую и последнюю цифры этого числа.
Program Integ;
Var N : Integer;
Begin
Write('Введите натуральное число: ');
ReadLn(N);
If Possible(N)
Then WriteLn('Невозможно переставить цифры, возникнет переполнение')
Else Begin
Change(N);
WriteLn('Ответ: ', N)
End;
End.
Можно заметить, что необходимо детализировать логическую функцию Possible, которая диагностирует, возможна ли перестановка, и процедуру Change, которая эту перестановку (в случае, если она возможна) выполняет.
Function Possible(N : Integer) : Boolean;
Begin
If Number(N) < 5
Then Possible := False
Else Possible := (N Mod 10 > 3) Or
(N Mod 10 = 3) And
(N Mod 10000 Div 10 * 10 + N Div 10000 > MaxInt Mod 10000)
End;
Здесь необходимо детализировать функцию Number, возвращающую количество цифр в записи натурального числа (т.к. функция Impossible содержит ее вызов, то в разделе описаний функция Number должна ей предшествовать).
Function Number(N : Integer) : Integer;
Var Vsp : Integer;
Begin
Vsp := 0;
While N > 0 Do
Begin
Vsp := Vsp + 1; N := N Div 10
End;
Number := Vsp
End;
Наконец, последняя процедура.
Procedure Change(Var N : Integer);
Var Kol, P, S, R : Integer;
Begin
Kol := Number(N);
P := N Mod 10; {последняя цифра}
If Kol > 1 Then
S := N Div Round(Exp((Kol - 1) * Ln(10)))
Else S := 0; {первая цифра}
R := N Mod Round(Exp((Kol - 1) * Ln(10))) Div 10;
N := P * Round(Exp((Kol - 1) * Ln(10))) + R * 10 + S
End;
Возможны также подпрограммы, которые вызывают сами себя. Они называются рекурсивными. Создание таких подпрограмм является красивым приемом программирования, но не всегда целесообразно из-за чрезмерного расхода памяти ЭВМ.
Пример 3. Найти максимальную цифру в записи данного натурального числа.
Program MaxDigit;
Type NaturLong = 1..(High(LongInt));
Digit = 0..9;
Var A : LongInt;
Function Maximum(N : LongInt) : Digit;
Begin
If N < 10
Then Maximum := N
Else If N Mod 10 > Maximum(N Div 10)
Then Maximum := N mod 10
Else Maximum := Maximum(N Div 10)
End;
Begin
Write('Введите натуральное число: ');
ReadLn(A);
WriteLn('Максимальная цифра равна ', Maximum(A))
End.
При создании функции Maximum было использовано следующее соображение: если число состоит из одной цифры, то она является максимальной, иначе если последняя цифра не является максимальной, то ее следует искать среди других цифр числа. При написании рекурсивного алгоритма следует позаботиться о граничном условии, когда цепочка рекурсивных вызовов обрывается и начинается ее обратное "раскручивание". В нашем примере это условие N < 10.
В структурном языке программирования любой программный объект (константа, переменная, тип и др.) должен быть описан перед использованием в программе. Иначе говоря, описание объекта должно предшествовать его первому появлению в других фрагментах программы. Это правило относится и к подпрограммам.
На рисунке схематически показана структура взаимного расположения описаний подпрограмм в некоторой условной программе. Попробуем, используя эту схему, разобраться в вопросе об области действия описаний подпрограмм.
Любая подпрограмма может использоваться лишь в пределах области действия ее описания (а описанные в ней объекты — лишь внутри этой подпрограммы). Например, область действия подпрограмм А и В — основная программа. Поэтому из основной программы можно обратиться к подпрограммам А и В. В свою очередь, в подпрограмме В могут быть обращения к подпрограмме А; а из А нельзя обратиться к В, поскольку описание А предшествует описанию В. Подпрограммы А1 и А2 локализованы в подпрограмме А и могут использоваться только в ней; из А2 можно обратиться к А1, но нельзя наоборот.
Из подпрограммы В1 можно обратиться к А, поскольку ее описание является глобальным по отношению к В1, но нельзя обратиться к А1, поскольку область действия описания А1 не распространяется на блок подпрограммы В.
Из подпрограммы В22 можно обратиться только к В21, В1, А.
Таким образом, можно заметить, что все внешние описания по отношению к той или иной подпрограмме носят глобальный характер. Все, что объявляется внутри подпрограммы, локализовано. Понятие "локальный-глобальный" является относительным, поскольку одно и то же описание по отношению к разным подпрограммам (основной программе) может являться и локальным, и глобальным.
Рассмотрим решение поставленной задачи в двух разных почтовых клиентах.
Outlook Express
Для того чтобы такое распределение было возможно, необходимо существование тех папок, по которым предполагается "раскладывать" письма (или нужно создать такие папки в процессе формирования правила сортировки почты).
Необходимо выбрать меню Сообщение -> Создать правило из сообщения...
Далее в диалоговом окне Создать правило для почты (см. рис.) указать, что сортировка почты осуществляется по полю Тема, в качестве действия указать Переместить в заданную папку, далее — описать правило.
Описание правила включает:
1) ввод ключевых слов
2) выбор папки, куда будут помещаться указанные сообщения
Последнее — задание названия для правила (либо можно согласиться с предлагаемым по умолчанию).
Таким образом, почтовый клиент будет автоматически сортировать часть почты. Аналогично можно сортировать почту по отправителю и т.д.
Служба mail.ru
В персональных настройках можно установить фильтры.
Выбрать Добавить фильтр в список фильтров. Настроить фильтр
Пример. Перед въездом в город стоят пять флагштоков. На флагштоках можно поднимать флаги желтого, зеленого и красного цвета. Какое количество различных сигналов можно подать при помощи этих флагштоков при условии, что не обязательно поднимать флаг на каждом из флагштоков?
Решение. При условии, что не обязательно поднимать флаг на каждом из флагштоков, для каждого флагштока есть 4 возможности: нет флага, желтый флаг, зеленый флаг, красный флаг. Тогда общее количество комбинаций получается следующим: 4×4×4×4×4=1024.
Варианты заданий
В качестве задач в этом разделе можно предлагать любые простейшие задачи из комбинаторики.
© Е.А. Ерёмин, А.П. Шестаков, 2006-07