И технологии программирования 2 страница

6.5. Структурированные банные и алгоритмы их обработки

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

Массивом называется упорядоченная совокупность однотипных величин, имеющих общее имя, элементы которой адресуются (различаются) порядковыми номерами (индексами). В качестве иллюстрации можно представить шкаф, содержащий множество пронумерованных ящиков (совокупность - «Ящик № 1», «Ящик № 2», «Ящик № 3» и т.д.; «Ящик» - общее имя всех ее элементов). Доступ к содержимому конкретного ящика (элементу массива) осуществляется после выбора ящика по его номеру (индексу). Элементы массива в памяти компьютера хранятся по соседству, одиночные элементы простого типа такого расположения данных в памяти не предполагают. Массивы различаются количеством индексов, определяющих их элементы.

Одномерный массив (шкаф ящиков в один ряд) предполагает наличие у каждого элемента только одного индекса. Примерами одномерных массивов служат арифметическая (а) и геометрическая {b₁.) последовательности, определяющие конечные ряды чисел. Количество элементов массива называют размерностью. При определении одномерного массива его размерность записывается в круглых скобках, рядом с его именем. Например, если сказано: «задан массив А(10)», это означает, что даны элементы: а_п а₂,..., а_т. Рассмотрим алгоритмы обработки элементов одномерных массивов.

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

Рис. 6.15. Ввод элементов одномерного массива А(10)

Пример 6.9.

Рассмотрим алгоритм вычисления среднего арифметического положительных элементов числового массива А(10).

Среднее арифметическое есть отношение суммы к числу ее слагаемых, т.е.

Алгоритм решения задачи (рис. 6.16) будет содержать подсчет суммы (обозначим ее S), включающей положительные элементы массива (а.> 0), и количества (обозначим N) ее слагаемых.

Псевдокод:

1. Повторить 10 раз (для i = 1, 10, 1).
1.1. Ввод a_t

2. Начальное значение суммы: S = 0.

3. Начальное значение счетчика: N = 0.

4. Повторить 10 раз (для /= 1, 10, 1):

4.1. ЕСЛИ а > 0, ТО S = S + а.; N = N + 1.

5. ЕСЛИ N > 0, ТО вычисление среднего арифметического
SA = S/N; вывод SA.

ИНАЧЕ: вывод «Положительных элементов в массиве нет».

6. Конец.

Рис. 6.16. Блок-схема задачи «подсчета среднего арифметического положительных элементов массива» (пример 6.9)

Пример 6.10.

В заданном числовом массиве А(10) найти наибольший элемент и его индекс, при условии, что такой элемент в массиве существует, и единственный.

Обозначим индекс наибольшего элемента т. Будем считать, что первый элемент массива является наибольшим (т = 1). Сравним поочередно наибольший с остальными элементами массива. Если оказывается, что текущий элемент массива а. (тот, с которым идет сравнение) больше выбранного нами наибольшего а, то считаем его наибольшим (т = i) (рис. 6.17).

Рис 6.17. Алгоритм поиска наибольшего элемента массива и его индекса (пример 6.10)

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

индекса а_г_> первый индекс / определяет номер строки, в которой находится элемент (координата по горизонтали), а второй j — номер столбца (координата по вертикали). Двумерный массив характеризуется двумя размерностями N и М, определяющими число строк и столбцов соответственно (рис. 6.18).

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

Рис. 6Л8. Матрица A(NxM)

самым определяется циклическая конструкция, реализующая вложение циклов. Внешний цикл определяет номер вводимой строки (/), внутренний — номер элемента по столбцу (/'). На рис. 6.19 представлен алгоритм ввода матрицы A(NxM).

Рис. 6.19. Алгоритм ввода матрицы

A(NxM)

Пример 6.11.

Задана матрица символов Х(100х100), представляющая собой карту ночного неба; звездам на карте соответствуют символы «*». Определить: сколько звезд на карте?

Алгоритм решения задачи достаточно прост, необходимо перебрать все элементы матрицы и посчитать, сколько среди них символов «*». Обозначим К переменную - счетчик. На рис. 6.20 представлена блок-схема решения этой задачи.

Рис. 6.20. Алгоритм примера 6.11

6.6. Языки программирования

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

Писать программы в машинных кодах очень сложно, причем с ростом размера программы эта задача усложняется. В компьютерах первого поколения использовались программы, написанные в машинных кодах, причем для каждого компьютера существовал свой собственный машинный код. Числовая кодировка команд, адресов ячеек и обрабатываемых данных, зависимость вида программы от ее места в памяти не давали возможность следить за смыслом программы. Это во многом ограничивало область применения компьютеров первого поколения. В тот период (начало 50-х гг.) средства программирования и программное обеспечение только зарождались и были еще не развиты. Для того чтобы сделать программу читабельной и иметь возможность следить за ее смысловой структурой, придумали символический язык ассемблер, близкий к машинному (конец 50-х — начало 60-х гг.), в котором появилось, понятие переменной. Ассемблер стал первым полноценным языком программирования. Благодаря этому заметно уменьшилось время разработки и возросла надежность программ. Для записи кодов операций и обрабатываемой информации в ассемблере используются стандартные обозначения, позволяющие записывать числа и текст в общепринятом виде, для кодов команд приняты мнемонические обозначения. Для обозначения величин, размещаемых в памяти, можно применять имена. После ввода программы ассемблер сам заменяет символические имена на адреса памяти, а символические коды команд на числовые. Использование ассемблера сделало процесс программирование более наглядным. Дальнейшее развитие этой идеи привело к созданию языков программирования высокого уровня, в которых длинные и сложные последовательности машинных кодов были заменены одним единственным обозначающим их словом — операторы.

6,6.1, Понятие «язык программирования»

Сегодня практически все программы создаются с помощью языков программирования. Теоретически программу можно написать и на естественном языке (говорят: программирование на метаязыке), но из-за неоднозначности естественного языка автоматически перевести такую программу в машинный код пока невозможно.

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

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

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

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

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

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

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

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

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

6.6,2, Компиляторы и интерпретаторы

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

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

Компиляторы полностью обрабатывают весь текст программы (его называют исходным кодом или source code). Они осуществляют поиск синтаксических ошибок, выполняют семантический анализ и только затем, если текст программы в точности соответствует правилам языка, его автоматически переводят (транслируют) на машинный язык (говорят: генерируют объектный код или object code). Нередко при этом выполняется оптимизация с помощью набора методов, позволяющих повысить быстродействие программы. Сгенерированный объектный код обрабатывается специальной программой — сборщиком или редактором связей, который производит связывание объектного и машинного кодов. Текст программы преобразуется в готовый к исполнению ЕХЕ-файл {исполнимый код), его можно сохранить в памяти компьютера или на диске. Этот файл имеет самостоятельное значение и может работать под управлением операционной системы. Его можно перенести на другие компьютеры с процессором, поддерживающим соответствующий машинный код.

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

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

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

6.6.3. Системы программирования

Процесс создания программы включает:

• Составление исходного кода программы (рис. 6.21) на языке программирования.

• Этап трансляции, необходимый для создания объектного кода
программы.

• Построение загрузочного модуля, готового к исполнению.

Все перечисленные выше действия требуют наличия специальных программных средств.

Рис. 6.21. Процесс создания программы, готовой к исполнению

Совокупность этих программных средств входит в состав системы программирования:

• Текстовый редактор (необходимый для создания и редактирования исходного кода программы на языке программирования).

• Компилятор.

• Редактор связей.

• Отладчик.

• Библиотеки функций.

• Справочная система.

6,6.4. Классификация и обзор языков программирования

Современное состояние языков программирования можно представить в виде следующей классификации (рис. 6.22).

. 6.22. Классификация языков программирования

Процедурное программирование

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

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

Одним из первых процедурных языков программирования высоко го уровня стал Фортран (FORmula TRANslation), созданный в начале 50-х гг. в США фирмой IBM. Первая публикация о нем появилась в 1954 г. Основное назначение языка — программирование научно-технических задач. Объектами языка являются целые и вещественные числа и числовые переменные. Выражения в нем формируются с помощью четырех арифметических действий: возведения в степень, логических операций И, ИЛИ, НЕ, операций отношения и круглых скобок. Основные операторы Фортрана — ввод, вывод, присваивание, условный и безусловный переход, цикл, вызов подпрограмм. Долгие годы он был одним из самых распространенных языков в мире. За это время накоплена огромная библиотека программ, написанных на Фортране. И сейчас ведутся работы над очередным стандартом Фортрана. В 2000 г. была реализована версия Фортран F2k, имеется стандартная версия HPF (High Performance Fortran) для параллельных суперкомпьютеров. Многие средства Фортрана использованы в языках PL-1 и Бейсик.

Кобол (СОттоп business Oriented ianguage - общепринятый деловой язык) — язык программирования, ориентированный на решение задач обработки данных. Широко используется для решения учетно-экономических и управленческих задач. Разработан в США в 1958-1960 гг. Программа на Коболе имеет вид ряда предложений на английском языке и напоминает обычный текст. Группы последовательно записанных операторов объединяются в предложения, предложения - в параграфы, параграфы - в секции. Программист присваивает параграфам и секциям имена (метки), что облегчает непосредственное обращение к нужному участку программы. В СССР был принят русский вариант языка. 8 Коболе были реализованы мощные средства работы с большими объемами данных, хранящимися на различных внешних носителях. На этом языке создано много приложений, некоторые из них активно эксплуатируются и сейчас. Достаточно сказать, что одной из высокооплачиваемых категорией граждан в США являются программисты на Коболе.

Алгол (ALGOnthmic L anguage) разработан группой зарубежных специалистов в I960 г., явился результатом международного сотрудничества конца 50-х гг. (Алгол-60). Алгол предназначался для записи алгоритмов, построенных в виде последовательности процедур, применяемых при решении поставленных задач. Специалисты-практики воспринимали этот язык неоднозначно, но тем не менее, он как признанный международный язык сыграл большую роль в становлении основных понятий программирования и для обучения программистов. В нем впервые введены понятия «блочная структура программы», «динамическое распределение памяти». Внутри блока в Алголе можно вводить локальные обозначения, которые не зависят от остальной части программы. Несмотря на свое интернациональное происхождение, Алгол-60 получил меньшее распространение, чем Фортран. Например, не на всех зарубежных ЭВМ имелись трансляторы с Алгола-60. В 1968 г. в результате дальнейшего развития и усовершенствования Алгола-60 была создана версия Алгол-68. Это многоцелевой универсальный расширенный язык программирования. Последнее свойство позволяло с помощью одной и той же программы транслятора осуществлять трансляцию с различных расширенных версий языка без дополнительных затрат на приспособление этого языка к различным категориям пользователей, на получение проблемно-ориентированных диалектов языка. По своим возможностям Алгол-68 и сегодня опережает многие языки программирования, однако из-за отсутствия эффективных компьютеров для него не удалось своевременно создать хорошие компиляторы. В нашей стране в те годы под руководством академика Андрея Петровича Ершова был создан транслятор Альфа, который представлял достаточно удачную русифицированную версию Алгола.

В середине 60-х гг. сотрудники математического факультета Дар-тмутского колледжа Томас Курц и Джон Кемени создали специализированный язык программирования, который состоял из простых английских слов. Новый язык назвали универсальным символическим кодом для начинающих (Beginners All-purpose symbolic /nstruction Code) или сокращенно BASIC {Бейсик). 1964 г, считают годом рождения этого языка. Он получил самое широкое распространение при работе на персональных компьютерах в режиме интерактивного диалога. Популярность Бейсика объясняется как простотой его освоения, так и наличием достаточно мощных универсальных средств, пригодных для решения научных, технических и экономических задач, а также задач бытового характера, игровых и т.д. Согласно концепциям, заложенным в Бейсике, в нем широко распространены различные правила умолчания, что считается плохим тоном в большинстве языков программирования подобного типа. Возникло множество версий языка, зачастую мало совместимых друг с другом. Однако, зная одну из версий, можно без особого труда освоить любую другую. Бейсик активно поглощает многие концепции и новинки из других языков. Первоначально интерактивный режим осуществлялся с использованием интерпретатора, в настоящее время для этого языка имеются также и компиляторы.

В начале 60-х гг. каждый из существующих языков программирования был ориентирован на разные классы задач, но в той или иной мере привязан к конкретной архитектуре ЭВМ. Были предприняты попытки преодолеть этот недостаток путем создания универсального языка программирования. ПЛ/1 (PL/1 — -Programming Language One) - первый многоцелевой универсальный язык, разработан в США фирмой IBM в 1963—1966 гг. Это один из наиболее распространенных универсальных языков, он хорошо приспособлен для решения задач в области вычислительной техники: исследования и планирования вычислительных процессов, моделирования, решения логических задач и исследования логических схем, разработки систем математического обеспечения. При разработке PL/1 были широко использованы основные понятия и средства языков Фортран, Алгол-60, Кобол. PL/1 — богатый и гибкий язык, дает возможность производить вставки, исправлять текст программы в процессе ее отладки. Язык получил широкое распространение, трансляторы с него имеются для многих типов компьютеров. Компания IBM и сегодня продолжает поддерживать этот язык.

Паскаль (Pascal) является одним из наиболее популярных процедурных языков программирования, особенно.для персональных компьютеров. Созданный как учебный язык программирования в 1968—1971 гг Никлаусом Виртом в Высшей технической школе (ЕТН) в Цюрихе (Швейцария), он был назван в честь французского математика и философа Блеза Паскаля (1623—1662). Целью работы Н. Вирта было создание языка, который

• строился бы на небольшом количестве базовых понятий;

• имел простой синтаксис;

• допускал перевод программ в машинный код простым компилятором.

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

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

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

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

Период с конца 60-х до начала 80-х гг. характеризуется бурным ростом числа различных языков программирования, сопровождавшим, как это ни парадоксально, кризис программного обеспечения. Этот кризис особенно остро переживало военное ведомство США. В январе 1975 г. Пентагон решил навести порядок среди бесчисленного множества трансляторов и создал комитет для разработки одного универсального языка. На конкурсной основе комитет рассмотрел сотни проектов и выяснил, что ни один из существующих языков не может удовлетворить их требованиям, для окончательного рассмотрения было оставлено два проекта. В мае 1979 г. был объявлен победитель — группа ученых во главе с Жаном Ихбиа. Победивший язык назвали АДА, в честь Ады Лавлейс, дочери великого поэта Байрона. Она в юности была увлечена идеями Чарльза Бэббиджа и помогала ему составлять описание машины, а в начале 40-х гг. XIX в. разработала, первую в мире программу для вычислительной машины. Язык АДА — прямой наследник Паскаля. Он предназначен для создания и длительного сопровождения больших программных систем, управления процессами в реальном масштабе времени. В языке четко выражена модульность его конструкций, причем обеспечивается удобство организации разнообразных связей между модулями. Важным его достоинством является возможность параллельного программирования ветвей программы, которые затем могут реализоваться на многопроцессорных компьютерах. Язык АДА сложен для изучения.

Язык программирования С (Си) был разработан в лаборатории Bell для реализации операционной системы UNIX в начале 70-х гг. и не рассматривался как массовый. Он планировался для замены Ассемблера, чтобы иметь возможность создавать столь же эффективные и компактные программы, и в то же время не зависеть от конкретного типа процессора. В С сочетаются достоинства современных высокоуровневых языков в части управляющих конструкций и структур данных с возможностями прямого доступа к аппаратным средствам компьютера. Синтаксис языка С обеспечивает краткость программы, его компиляторы генерируют эффективный объектный код. Одна из наиболее существенных особенностей С состоит в том, что различия между выражениями и операторами нивелируются, это приближает его к функциональным языкам. Например, выражение может обладать побочным эффектом присваивания, а также может использоваться в качестве оператора. Нет четкого различия между процедурами и функциями, более того, понятие процедуры вообще не вводится. Синтаксис языка затрудняет программирование и восприятие составленных программ. Отсутствует строгая типизация данных, что предоставляет дополнительные возможности программисту, но не способствует созданию надежных программ. Язык С приобрел большую популярность среди системных и прикладных программистов. В настоящее время этот язык реализован для большинства компьютерных платформ.

Функциональное программирование

Суть функционального (аппликативного) программирования определена А. П. Ершовым как «способ составления программ, в которых единственным действием является вызов функции, единственным способом расчленения программы на части является введение имени функции, а единственным правилом композиции - оператор суперпозиции функций. Никаких ячеек памяти, ни операторов присваивания, ни циклов, ни, тем более, блок-схем, ни передачи управления».

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

• классы констант, которыми могут манипулировать функции;

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