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

Содержание:

ВВЕДЕНИЕ

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

Пособие состоит из шести глав.

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

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

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

ГЛАВА I. Основы алгоритмизации

• 1. 1.1 Понятие алгоритма

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

Порядок действий считается алгоритмом в том случае, если он обладает определенными свойствами.

• 1. 1.2 Свойства алгоритма

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

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

• Результативность. Алгоритм должен приводить к решению задачи или сообщению, что задача решений не имеет за конечное число шагов.

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

• Массовость. Алгоритм разрабатывается в общем виде так, чтобы его можно было применять для класса задач, различающихся только исходными данными. При этом исходные данные выбираются из некоторой области, которая называется областью применяемости алгоритма. Например, для решения квадратного уравнения ax 2 +bx+c=0, коэффициенты действительные числа, а ≠ 0, и а, в, с – различные

• 1. 1.3 Способы записи алгоритмов

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

а) Словесно-формульный способ. Например, требуется решить квадратное уравнение ax 2 +bx+c=0 в области действительных чисел.

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

1.4 Правила построения алгоритмов на языке блок-схем

1. Блок-схема строится сверху вниз.
2. В любой блок-схеме имеется один элемент, соответствующий началу, и один элемент, соответствующий концу.
3. Должен быть хотя бы один путь из начала блок-схемы к любому элементу.
4. Должен быть хотя бы один путь от каждого элемента блок-схемы в конец блок-схемы.

в) Операторный способ (алгоритмический язык). Алгоритм – это задание для исполнителя. Исполнитель выполняет алгоритм, т. е. делает то, что написано в алгоритме. Если исполнитель точно выполнит то, что написано в алгоритме, то он получит результат.

Человек, автоматическое устройство, компьютер – это разные исполнители алгоритмов. Для того чтобы компьютер мог выполнить алгоритм, его надо написать на понятном компьютеру языке. Компьютер понимает машинный язык. Например, равенство х = у на машинном языке имеет вид: 111101110011110111110101.

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

Для того чтобы человек и компьютер понимали друг друга, разработаны специальные языки для записей алгоритмов – алгоритмические языки. Самые известные алгоритмические языки – это Бейсик (Basic), Паскаль (Pascal), Фортран (Fortran).

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

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

Например, можно написать программу решения квадратного уравнения ax ² +bx+c=0 на компьютере. На алгоритмическом языке Бейсик эта программа будет выглядеть так:

REM РЕШЕНИЕ КВАДРАТНОГО УРАВНЕНИЯ

INPUT “введите а,b,c“; А,B,C

D=B-2 - 4*A*C

IF D<0 THEN “РЕШЕНИЙ НЕТ”

Y1=(-B+SQR(D))/(2*A):Y2=(-B-SQR(D))/(2*A)

PRINT “КОРНИ УРАВНЕНИЯ” ;Y1,Y2

1.4. Типы алгоритмов

Алгоритмы бывают линейные, разветвляющиеся и циклические.

Линейный алгоритм – это алгоритм, в котором действия выполняются только один раз и строго в том порядке, в котором они записаны.

Линейные алгоритмы в математике – это, например, вычисление площадей фигур.

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

В блок-схемах разветвляющихся алгоритмов всегда есть логический блок.

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

Выполняется циклический алгоритм так: сначала проверяется условие, если условие верно (истина), то выполняется тело цикла (действия или группа операторов) и, далее, изменяются значения параметра цикла и снова проверяется условие и т. д. На каком-то шаге условие не выполнится (ложь) и тогда происходит выход из цикла и продолжается выполнение программы.

ГЛАВА II. Простейшие конструкции языка программирования QBasic

2.1. Алфавит языка

Язык программирования Qbasic (как и любой другой язык) образуют три его составляющие: алфавит, синтаксис и семантика.

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

Синтаксис – это правила построения фраз, позволяющие определить, правильно или неправильно написана та или иная фраза.

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

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

Алфавит языка включает:

• буквы латинского алфавита от A до Z (строчные и прописные)

• арабские цифры: 0 1 2 … 9

• знаки арифметических операций: + – * / ^ \

• специальные символы объявления типа: % # ! $ &

• круглые скобки ( ) кавычки “ ” апостроф ’ , подчеркивание _

• знаки отношений: < > = < > < = > =

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

2.2. Константы

Константы – это данные, не изменяющиеся в процессе решения задачи. В Qbasic используются числовые и текстовые константы.

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

Целые константы – это последовательность цифр, перед которой может стоять знак + или – . Например: –567, +29, 29.

Вещественные константы – это числа, имеющие целую и дробную части. Бывают две формы записи вещественных констант: основная и экспоненциальная формы записи. В основной форме записи с фиксированной точкой целая часть числа отделяется от дробной части десятичной точкой, например, -1.012, 3.14159. В экспоненциальной форме записи с «плавающей» точкой число записывается в виде: mE± p, где m – мантисса (число в основной форме), Е – основание 10, р – порядок числа (целая константа, содержащая не более двух цифр).

Например: 2.4Е-05, -2.9Е+07.

Чтобы перейти от экспоненциальной формы к основной, нужно m (мантиссу) умножить на 10 в степени р (порядок).

Например: 2.4Е-5 = 2.4·10-5 = 0.000024, -2,9Е+07 = 2.9·107 = 29000000.

Строковые константы – это набор любых символов длиной, не превышающей 255 символов. Строковая константа заключается в двойные кавычки. Например: “ТАБЛИЦА”, “ALFA_2”,“ Решений нет”.

2.3 Переменные

Переменные – это величины, значения которых могут изменяться в процессе выполнения программы, обозначаются именем (идентификатором). Имя переменной представляется последовательностью не более чем 40 латинских букв и цифр, начинающейся обязательно с буквы и заканчивающейся суффиксом, определяющим тип переменной. Символы типов: % – целый; ! – вещественный; $ – строковый. Если символ типа отсутствует, то переменная по умолчанию считается вещественной. Например: переменные SUM, a, B12, Max, S!, P!, B! – вещественного типа; Z%, D%, A% – целого типа; F$, S$, G$ – строкового типа.

Различают простые переменные и переменные с индексом. Простая переменная определяется только именем. Переменная с индексом является элементом массива, определяется именем и индексами, которые задают 23 местоположение элемента в массиве. Индексы записываются в скобках через запятую после имени переменной. Например: Х(10), А(5,6).

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

2.4. Функции

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

2.5. Выражения

Различают выражения арифметические, логические, строковые.

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

1. вычисление функции;
2. возведение в степень;
3. деление и умножение;
4. деление нацело и определение остатка (операция по модулю MOD);
5. сложение и вычитание.

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

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

Деление нацело (целочисленное деление). Целочисленное деление обозначается наклонной чертой \ . Перед делением компоненты действий округляются до целых чисел, а в частном отбрасывается остаток.

Например: 14 \ 2 = 2, 25.68 \ 7 = 3.

Операция по модулю MOD. Результат вычисления по модулю – целое число, являющееся остатком от деления нацело.

Например: 11 MOD 4 = 3 (11\ 4 = 2 остаток 3)

25.68 MOD 6.87 = 5 (26 \ 7 = 3 остаток 5)

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

1. Все символы выражения записываются в одну сторону. Запрещены многоэтажные выражения и верхние и нижние индексы.
2. Два знака арифметических операций не должны располагаться рядом. Знак умножения опускать нельзя.
3. Операции в арифметическом выражении выполняются в порядке старшинства, т. е.:
4. операции внутри скобок;
5. вычисление встроенных функций;
6. возведение в степень;
7. умножение и деление;
8. целочисленное деление;
9. деление по модулю;
10. сложение и вычитание.

Операции равного старшинства выполняются по порядку слева направо. Исключение: А ^B^C = A^(B^C).

Логическое выражение служит для установления отношения между двумя числовыми или строковыми значениями. Результатом вычисления логического выражения является значение «Истина» или «Ложь».

ГЛАВА III. ЯЗЫКИ ПРОГРАММИРОВАНИЯ

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

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

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

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

Персональные компьютеры IBM используют машинный язык микропроцессоров семейства 8086, т.к. их аппаратная часть основывается именно на данных микропроцессорах.

Можно писать программы непосредственно на машинном языке, хотя это и сложно. На заре компьютеризации(в начале 1950-х г.г.), машинный язык был единственным языком, большего человек к тому времени не придумал. Для спасения программистов от сурового машинного языка программирования, были созданы языки высокого уровня (т.е. немашинные языки), которые стали своеобразным связующим мостом между человеком и машинным языком компьютера. Языки высокого уровня работают через трансляционные программы, которые вводят «исходный код» (гибрид английских слов и математических выражений, который считывает машина), и в конечном итоге заставляет компьютер выполнять соответствующие команды, которые даются на машинном языке. Существует два основных вида трансляторов:

· интерпретаторы, которые сканируют и проверяют исходный код в один шаг;

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

3.1. Интерпретаторы

Одно, часто упоминаемое преимущество интерпретаторной реализации состоит в том, что она допускает «непосредственный режим». Непосредственный режим позволяет вам задавать компьютеру задачу вроде PRINT 3.14159*3/2.1 и возвращает вам ответ, как только вы нажмете клавишу ENTER (это позволяет использовать компьютер стоимостью 3000 долларов в качестве калькулятора стоимостью 10 долларов). Кроме того, интерпретаторы имеют специальные атрибуты, которые упрощают отладку. Можно, например, прервать обработку интерпретаторной программы, отобразить содержимое определенных переменных, бегло просмотреть программу, а затем продолжить исполнение.

Больше всего программистам нравится в интерпретаторах возможность получения быстрого ответа. Здесь нет необходимости в компилировании, так как интерпретатор всегда готов для вмешательства в вашу программу. Введите RUN и результат вашего самого последнего изменения оказывается на экране.

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

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

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

3.2. Компиляторы

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

3.3 Эволюция и классификация языков программирования

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

— высокое качество создаваемых программ (компактность и скорость выполнения);

— возможность использования конкретных аппаратных ресурсов;

— предсказуемость объектного кода и заказов памяти;

— для составления эффективных программ необходимо знать систему команд и особенности функционирования данной ЭВМ;

— трудоемкость процесса составления программ ( особенно на машинных языках и ЯСК), плохо защищенного от появления ошибок;

— низкая скорость программирования;

— невозможность непосредственного использования программ, составленных на этих языках, на ЭВМ других типов.

Машинно-ориентированные языки по степени автоматического программирования подразделяются на классы.

Машинный язык. Отдельный компьютер имеет свой определенный Машинный язык (далее МЯ), ему предписывают выполнение указываемых операций над определяемыми ими операндами, поэтому МЯ является командным. Однако, некоторые семейства ЭВМ (например, ЕС ЭВМ, IBM/370/ и др.) имеют единый МЯ для ЭВМ разной мощности. В команде любого из них сообщается информация о местонахождении операндов и типе выполняемой операции.

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

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

Использование символических адресов – первый шаг к созданию ЯСК. Команды ЭВМ вместо истинных (физических) адресов содержат символические адреса. По результатам составленной программы определяется требуемое количество ячеек для хранения исходных промежуточных и результирующих значений. Назначение адресов, выполняемое отдельно от составления программы в символических адресах, может проводиться менее квалифицированным программистом или специальной программой, что в значительной степени облегчает труд программиста.

Автокоды. Есть также языки, включающие в себя все возможности ЯСК, посредством расширенного введения макрокоманд — они называются Автокоды.

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

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

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

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

Макрос. Язык, являющийся средством для замены последовательности символов описывающих выполнение требуемых действий ЭВМ на более сжатую форму — называется Макрос (средство замены).

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

Макрос одинаково может работать, как с программами, так и с данными.

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

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

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

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

Проблемных языков очень много, например:

Фортран, Алгол – языки, созданные для решения математических задач;

Simula, Слэнг — для моделирования;

Лисп, Снобол – для работы со списочными структурами.

Универсальные языки. Универсальные языки были созданы для широкого круга задач: коммерческих, научных, моделирования и т.д. Первый универсальный язык был разработан фирмой IBM, ставший в последовательности языков Пл/1. Второй по мощности универсальный язык называется Алгол-68. Он позволяет работать с символами, разрядами, числами с фиксированной и плавающей запятой. Пл/1 имеет развитую систему операторов для управления форматами, для работы с полями переменной длины, с данными организованными в сложные структуры, и для эффективного использования каналов связи. Язык учитывает включенные во многие машины возможности прерывания и имеет соответствующие операторы. Предусмотрена возможность параллельного выполнение участков программ.

Программы в Пл/1 компилируются с помощью автоматических процедур. Язык использует многие свойства Фортрана, Алгола, Кобола. Однако он допускает не только динамическое, но и управляемое и статистическое распределения памяти.

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

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

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

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

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

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

Табличные методы легко осваиваются специалистами любых профессий.

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

ГЛАВА IV. Технология объектно-ориентированного программирования

4.1. Объектно-ориентированный подход

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

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

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

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

Объектно-ориентированное программирование (object-oriented programming) - это технология реализации программ, основанная на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определенного класса, а классы образуют иерархию наследования.

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

4.2. Основные понятия объектно-ориентированного программирования

Понятие объектно-ориентированного программирования определяет три основные концепции, при соблюдении которых программа будет объектно-ориентированной:

• объектно-ориентированное программирование использует в качестве базовых элементов классы, порождающие объекты;

• в процессе выполнения программы может одновременно использоваться несколько объектов, порожденных от одного класса (экземпляров реализации класса);

• классы организованы иерархически (иерархия означает «быть частью»).

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

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

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

Объект, как логическая единица, содержит следующие данные и операции (методы с кодом алгоритма) в отдельном участке памяти:

• поля объекта (или атрибуты исходных данных), значения которых определяют текущее состояние объекта;

• методы объекта, которые реализуют действия (выполнение алгоритмов) в ответ на их вызов в виде преданного сообщения;

• свойства — часть методов, которые определят поведение объекта, то есть его реакцию на внешние воздействия.

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

Объекты в программах воспроизводят все оттенки явлений реального мира: «рождаются» и «умирают»; меняют свое состояние; запускают и останавливают процессы; «убивают» и «возрождают» другие объекты.

4.3. Принципы объектно-ориентированного программирования: инкапсуляция, наследование и полиморфизм

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

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

Принцип инкапсуляции использовался в технологии модульного программирования. В модуле в явной форме введена инкапсуляция путем разделения его на секции интерфейса и реализации.

В объектно-ориентированном программировании принцип инкапсуляции используется для изоляции класса от остальных частей программы, чтобы сделать его самодостаточным для решения конкретной задачи. Например, класс TForm в среде Delphi содержит (инкапсулирует в себе) все необходимое для создания Windows-окна, класс ТМето представляет собой полнофункциональный текстовый редактор, класс TTimer обеспечивает работу программы с таймером и т. д.

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

type

TMyClass = class

IntField: Integer;

function MyFunc(a: Integer): Integer;

procedure MyProc; end;

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

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

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

Принцип наследования оперирует с понятиями «предок - потомок» и предусматривает расширение набора свойств наследника за счет принятия всех свойств предка.

Любой класс может быть порожден от другого класса. Для этого при его объявлении указывается имя класса-родителя:

TChildCIass = class (TParentClass )

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

Все классы в Object Pascal порождены от единственного родителя - класса TObject. Этот класс не имеет полей и свойств, но включает в себя методы самого общего назначения, обеспечивающие весь жизненный цикл любых объектов - от их создания до уничтожения. Поэтому программист не может создать класс, который не был бы дочерним классом TObject. Следующие два объявления идентичны.

TaClass = class(TObject) <==> TaClass = class

Принцип наследования приводит к созданию ветвящегося дерева классов. Каждый потомок дополняет возможности своего родителя новыми и передает их своим потомкам. Например, класс TPersistent обогащает возможности своего родителя TObject тем, что он умеет сохранять данные в файле и получать их из него, в результате это умеют делать и все его потомки. Класс TComponent, в свою очередь, умеет взаимодействовать со средой разработчика и передает это умение своим потомкам. TControl не только способен работать с файлами и средой разработчика, но он еще умеет создавать и обслуживать видимые на экране изображения, а его потомок TWinControl может создавать Windows-окна и т. д.

В Object Pascal возможно только так называемое одиночное наследование, но в реальном мире у потомка два родителя, поэтому в ряде языков (например, в C++) предусмотрен механизм множественного наследования. Множественное наследование более логично с точки зрения моделирования реального мира, однако, оно усложняет реализацию языков программирования.

Полиморфизм. Одним из базовых понятий технологии объектно-ориентированного программирования является полиморфизм. Этот термин имеет греческое происхождение и приблизительно означает «много форм» (poly — много, morphos — форма).

Полиморфизм - это средство для придания различных значений одному и тому же событию в зависимости от типа обрабатываемых данных. Этот принцип определяет различные формы реализации одноименного действия.

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

Почему авторы выбрали язык программирования Qbasic, ведь в настоящее время существует большое количество алгоритмических языков, которым присущи как общие, так и отличительные черты. Это и Фортран, и Паскаль и др.

Бейсик (BASIC) – это сокращение английских слов Beginners Allpurpouse Symbolic Instraction Code, что в переводе означает «многоцелевой язык символических инструкций для начинающих». Он был разработан профессорами Дартмутского колледжа (США) Т. Куртцем и Дж. Кемени в 1965 году для обучения студентов, незнакомых с вычислительной техникой. Этот язык, благодаря простоте, стал очень популярным. Особенно его популярность повысилась с появлением персональных компьютеров, где он стал одним из основных языков программирования.

Существует множество версий языка Бейсик, более сорока, и все они имеют особенности. Это и Qbasic, и Visual Basic, и др. Но в каждой из них можно выделить общее, в котором отражены характерные (стандартные) грамматика, синтаксис и семантика языка. Наиболее популярной версией для обучения программированию является Qbasic, благодаря удобному интерфейсу и представлению пользователю ряда сервисных возможностей, присущих современным системам программирования. На примере Qbasic можно наглядно увидеть те характерные особенности, которые присущи программированию на алгоритмических языках вообще. Поэтому тексты представленных в учебном пособии программ отлажены именно в нем.

БИБЛИОГРАФИЯ

1. Бобровский С.И. Программирование на языке Qbasic для школьников и студентов / С.И. Бобровский. – М.: изд-во Инфорком-Пресс, ТехБук(Десс), 2000. – 207с.

2. Златопольский Д.М. Сборник задач по программированию / Д.М. Златопольский. – 2-е изд., перераб. и доп. – СПб.: БХВ-Петербург, 2007. – 240с.: ил.

3. Ляхович В.Ф. Основы информатики / В.Ф. Ляхович. – Ростов н/Д. : «Феникс», 2000. – 608с.

4. Михайлов В.Ю. Современный Бейсик для IBM PC. Среда, язык, программирование / В.Ю. Михайлов, В.М. Степанников. – М.: изд-во МАИ, 1993. – 288с. : ил.

5. Ставнистый Н.Н. Qbasic в математике. Решение задач с помощью компьютера / Н.Н. Ставнистый. – М:. Солон-Р, 2001. – 143с.

6. Березин Б.И., Березин С.Б. Начальный курс С и С++. - М.: Диалог - Мифи,1997. - 288 с.