Основные алгоритмические конструкции
Наиболее понятно структуру алгоритма можно представить с помощью блок-схемы, в которой используются геометрические фигуры (блоки), соединенные между собой стрелками, указывающими последовательность выполнения действий. Приняты определенные стандарты графических изображений блоков. Например, команду обработки информации помещают в блок, имеющий вид прямоугольника, проверку условий - в ромб, команды ввода или вывода - в параллелограмм, а овалом обозначают начало и конец алгоритма.
Структурной элементарной единицей алгоритма является простая команда, обозначающая один элементарный шаг переработки или отображения информации. Простая команда на языке схем изображается в виде функционального блока.
 | Данный блок имеет один вход и один выход. Из простых команд и проверки условий образуются составные команды, имеющие более сложную структуру и тоже один вход и один выход. Структурный подход к разработке алгоритмов определяет использование только базовых алгоритмических структур (конструкций): следование, ветвление, повторение, которые должны быть оформлены стандартным образом. |
 | Рассмотрим основные структуры алгоритма. Команда следования состоит только из простых команд. На рисунке простые команды имеют условное обозначение S1 и S2. Из команд следования образуются линейные алгоритмы. Примером линейного алгоритма будет нахождение суммы двух чисел, введенных с клавиатуры. |
 | Команда ветвления - это составная команда алгоритма, в которой в зависимости от условия Р выполняется или одно S1, или другое S2 действие. Из команд следования и команд ветвления составляются разветвляющиеся алгоритмы (алгоритмы ветвления). Примером разветвляющегося алгоритма будет нахождение большего из двух чисел, введенных с клавиатуры. |
 | Команда ветвления может быть полной и неполной формы. Неполная форма команды ветвления используется тогда, когда необходимо выполнять действие S только в случае соблюдения условия P. Если условие P не соблюдается, то команда ветвления завершает свою работу без выполнения действия. Примером команды ветвления неполной формы будет уменьшение в два раза только четного числа. |
 | Команда повторения - это составная команда алгоритма, в которой в зависимости от условия Р возможно многократное выполнение действия S. Из команд следования и команд повторения составляются циклические алгоритмы (алгоритмы повторения). На рисунке представлена команда повторения с предусловием. Называется она так потому, что вначале проверяется условие, а уже затем выполняется действие. Причем действие выполняется, пока условие соблюдается. Пример циклического алгоритма может быть следующий. Пока с клавиатуры вводятся положительные числа, алгоритм выполняет нахождение их суммы. |
 | Команда повторения с предусловием не является единственно возможной. Разновидностью команды повторения с предусловием является команда повторения с параметром. Она используется тогда, когда известно количество повторений действия. В блок-схеме команды повторения с параметром условие записывается не в ромбе, а в шестиугольнике. Примером циклического алгоритма с параметром будет нахождение суммы первых 20 натуральных чисел. В команде повторения с постусловием вначале выполняется действие S и лишь затем, проверяется условие P. Причем действие повторяется до тех пор, пока условие не соблюдается. Примером команды повторения с постусловием будет уменьшение положительного числа до тех пор, пока оно неотрицательное. Как только число становится отрицательным, команда повторения заканчивает свою работу. С помощью соединения только этих элементарных конструкций (последовательно или вложением) можно "собрать" алгоритм любой степени сложности. |
Каждая указанная конструкция может быть без изменений в структуре реализована на любом языке программирования, например, на Паскале и Бейсике. Поэтому необходимо грамотно составить алгоритм с помощью блок-схемы, а уже затем, зная, как записываются команды на конкретном языке программирования, набрать программу на компьютере и получить результат, запустив ее на исполнение.
Линейный алгоритм
Приведем пример записи алгоритма в виде блок-схемы, псевдокодов и на языке Паскаль. Ручное тестирование и подбор системы тестов выполняются аналогично предыдущему заданию.
Разветвляющийся алгоритм
Пример записи разветвляющегося алгоритма для нахождения наибольшего из двух чисел.
Циклический алгоритм
Рассмотрим алгоритм нахождения суммы первых натуральных нечетных чисел до n. Представим запись алгоритма тремя способами: в виде блок-схемы, школьного алгоритмического языка и на языке программирования Pascal.
Блок-схема состоит из следующих базовых структур: две составные команды (команда следования и команда повторения с предусловием), далее простая команда. Все команды соединены последовательно. Конструкции оформлены стандартным образом, поэтому их легко распознать и перевести на язык программирования. Каждая конструкция имеет один вход и один выход. Пунктирные стрелки в таблице отражают последовательность выполнения технологической цепочки. После записи алгоритма в виде блок-схемы каждая команда переводится на школьный алгоритмический язык, а уже затем на язык программирования.
Запишем алгоритм вычисления суммы первых n натуральных чисел. Для этого воспользуемся циклом с параметром, поскольку заранее известно сколько раз будет выполняться команда нахождения суммы. Во всех звеньях цепочки поменяем цикл "пока" на цикл "для" и приведем пример перевода алгоритма с языка блок-схем на школьный алгоритмический язык и на язык программирования Pascal.
Рассмотрим нахождение количества натуральных чисел, сумма которых не больше заданной. Для этого воспользуемся командой повторения с постусловием.
Вопросы для самоконтроля
1. Понятие алгоритма. Свойства алгоритма. Пример алгоритма. Понятие "переменная".
2. Оператор присваивания. Примеры.
3. Стили программирования (логический, функциональный).
4. Понятие подпрограммы, модуля и объекта
5. Что такое переменная? Правила наименования переменных в Паскале. Примеры.
6. Оператор присваивания. Запись выражений в Паскале. Примеры. Объяснить, как действует оператор x:=x+1;
7. Операторы ввода и вывода в Паскале. Примеры. Форматированный вывод.
8. Условный оператор (if). Пример. Сравнить с оператором case.
9. Оператор выбора. Пример. Сравнить с оператором if.
10. Логические выражения. Операции or, and и not. Примеры. Таблица истинности.
11. Числовые типы переменных в языке Паскаль. Правила преобразования типов. Примеры.
12. Логический тип данных. Пример использования в программе. Символьный тип данных. Пример. Функции chr и ord, succ и pred.
13. Массивы. Определение. Индексы массивов. Объявления массивов. Обращения к элементам массива. Одномерные и двумерные массивы. Примеры. Сходство и различие массивов и строк.
14. Процедуры. Определение. Зачем нужны процедуры? Примеры. Правила описания процедур. Сравнить процедуры и функции.
ТУРБО ПАСКАЛЬ – ЯЗЫК ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ
Системы программирования
При наличии десятков тысяч прикладных программ часто приходится сталкиваться с ситуацией, когда существующие программы не удовлетворяют или делают что-то недостаточно быстро или неэффективно. В этой ситуации единственный выход – написание собственной программы.
По природе своей компьютер может выполнять только простейшие операции, которые можно водить одну за другой в его память прямо в машинных кодах. Изнурительная монотонность такой работы привела когда-то первых программистов к единственному решению- созданию ассемблеров, т.е. средств, упрощающих подготовку машинных кодов программ пользователей за счет написания их в некоторых мнемонических обозначениях с последующим автоматическим переводом. Дальнейшее развитие этих идей привело к созданию языков программирования высокого уровня, в которых длинные и сложные последовательности машинных операций были заменены одни единственным обозначающим их словом – оператор.
Специальные программы обеспечивают опосредование, «понимание» вычислительной машиной других языков программирования путем перевода текстов, составленных на этих языках, в тексты на машинном языке.
Под системой программирования понимают совокупность языка программирования и виртуальной машины, обеспечивающей выполнение реальной машинной программы, составленной на этом языке.
Языком программирования называют систему обозначений для точного описания алгоритмов на ЭВМ. Эти языки являются искусственными языками со строго определенным синтаксисом (строение предложений и правила сочетания слов) и семантикой (смысловое значение слов и оборотов речи), поэтому они не допускают свободного толкования конструкций, характерного для естественного языка (языка общения между людьми).
Виртуальная машина – это программный комплекс, связывающий входной язык ЭВМ с другим, машинным языком.
Виртуальная машина содержит транслятор и/или интерпретатор и может включать библиотеки подпрограмм, отладчик, компоновщик и другие сервисные средства.
Трансляторпредставляет собой программу, осуществляющую перевод текстов с одного языка на другой. В системе программирования транслятор переводит программу с входного языка этой системы на машинный язык реальной ЭВМ (н которой функционирует данная система программирования или будет функционировать разработанная программа) либо на промежуточный язык программирования, уже реализованный или подлежащий реализации. Одной из разновидностей транслятора является компилятор, обеспечивающий перевод программ с языка высокого уровня (приближенного к человеку) на язык более низкого уровня (близкий к ЭВМ), или машинозависимый язык. Другая разновидность транслятора – ассемблер, осуществляющий перевод программ с языка низкого уровня (языка Ассемблер) на машинный язык, имеющий примерно тот же уровень. Некоторые трансляторы служат для переноса программ с одной машины на другую. Программа, подающаяся на вход транслятора, называется исходной, а результат трансляции – объектной программой.
Диаметрально противоположными характеристиками обладает альтернативное средство реализации языка – интерпретатор. Интерпретатор представляет собой программный продукт, выполняющий предъявленную программу путем одновременного ее анализа и реализации предписанных ею действий. При использовании интерпретатора отсутствует разделение на две стадии (перевод и выполнение) и, более того, отсутствует явный перевод программы даже по частям перед очередным этапом выполнения. В действительности же распознается очередная конструкция программы и интерпретатором выполняются определенные ею действия. После этого процессы анализа и реализации предписанных действий циклически повторяются.
Возможны и смешанные стратегии реализации языков программирования, например, трансляция на промежуточный язык с последующей интерпретацией промежуточной программы.
Программа на языке программирования состоит из последовательности операторов (инструкций), задающих те или иные действия. Основным является оператор присваивания, служащий для изменения содержимого области памяти.
Выполнение программы сводится к последовательному выполнению операторов с целью преобразования исходного состояния памяти (т.е. значений переменных) в заключительное. Таким образом, с точки зрения программиста имеется программа и память, причем первая последовательно обновляет содержание последней.
Одним из важнейших классификационных признаков процедурных языков является их уровень. Уровень языка программирования определяется семантической (смысловой) емкостью его конструкций и его ориентацией на программиста-человека. Язык программирования (частично) ликвидирует семантический разрыв между методами решения задач машиной и человеком. Языки программирования, не зависящие от особенностей конкретной машины и ориентированные на широкий круг пользователей, считаются языками высокого уровня (по отношению к уровню машинных команд ЭВМ). Чем выше язык ориентирован на программиста, тем выше его уровень.
Двоичный язык является не чем иным, как непосредственно машинным языком. В настоящее время такие языки программирования не применяются.
Шестнадцатеричный язык обеспечивает некоторое упрощение записи программы на машинном языке путем представления четырех двоичных цифр одной шестнадцатеричной. Это язык используется в качестве дополнения к языкам высокого уровня, таким как Паскаль или СИ, для программирования критичных к времени выполнения фрагментов алгоритмов.
Язык Ассемблера – это язык, предназначенный для представления в удобочитаемой форме программ, записанных на машинном языке. Он позволяет программисту пользоваться мнемоническими кодами операций, по своему усмотрению присваивать символические имена регистрам ЭВМ и ячейкам памяти, а также задавать наиболее удобные в том или ином контексте схемы адресации. Кроме того, язык Ассемблера обеспечивает представление констант в различных системах счисления (например, в десятичной или шестнадцатеричной).
Язык Макроассемблера является расширением языка ассемблер за счет включения макросредств и предоставляет средства определения и использования новых, более мощных команд как последовательностей базовых инструкций, что несколько повышает его уровень.
Языки ассемблер и Макроассемблер применяются системными программистами-профессионалами с целью использования всех возможностей оборудования ЭВМ и получения эффективной, как по времени выполнения, так и по потребному объему памяти. программы.
Приведем краткий перечень наиболее распространенных языков программирования высокого уровня, которые имеют преимущественное распространение в настоящее время, причем имеют по несколько версий.
Бейсик представляет собой простой язык программирования, разработанный в 1964 году для использования новичками. Работа в среде Бейсик первоначально велась только в режиме интерактивной (диалоговой) интерпретации. В настоящее время имеются и компиляторы с этого языка. В этом языке широко используются разного рода умолчания, что считается плохим тоном в большинстве современных языков. Несмотря на это, Бейсик очень популярен, в особенности на ПЭВМ. Существует множество его диалектов. Бейсик является одним из наиболее динамичных языков. Не без оснований это язык иногда сравнивают с питоном, заглатывающим и переваривающим все новое, что появляется в других языках программирования. Уровень Бейсика нельзя определить однозначно. Современные диалекты весьма развиты и мало чем напоминают своего предка.
Язык Фортран был разработан в 1956 году, затем появились новые его версии Фортран-II , Фортран-IV, Фортран-66, Фортран-77, Фортран-8х, Фортран-88. В сове время этот язык был поистине «рабочей лошадью» научных работников и широко используется в настоящее время, несмотря на его ограниченность и корявость. Он предоставляет пользователям большие возможности для обработки числовых данных, особенно комплексных чисел. Еще в версии Фортран-II впервые была реализована идея раздельной компиляции модулей, что дало возможность создавать библиотеки научных подпрограмм.
Язык программирования СИ первоначально разработан в 70-х годах. В настоящее время в СИ сочетаются достоинства современных высокоуровневых языков и возможность доступа к аппаратным средствам машины на уровне, который обычно ассоциируется с языком Ассемблера. Си имеет синтаксис, обеспечивающий чрезвычайную краткость программ, а компиляторы, вследствие особенностей языка, способны генерировать быстрые и эффективные программы на машинном коде.
Язык программирования APLсоздан в 1969 год. К числу его основных преимуществ относятся богатый набор мощных операторов, позволяющих работать с многомерными массивами как единым целым, а также предоставление пользователю возможности определять собственные операторы. Основное его назначение – обработка массивов.
FORTH – гибкий и достаточно простой язык, разработанный в 1971 году. Важная его особенность – открытость (расширяемость). Программист может добавлять новые операции, типы данных и операторы. Последнее достигается путем связывания любой строки программы с заданным программистом словом, которое затем может использоваться наравне со стандартными операторами. Однако расширение языка ведет к снижению эффективности.