Способы описания алгоритмов
Алгоритмы и их свойства
Основы программирования
Алгоритм - это определённая последовательность команд, при выполнении которых можно получить определенный результат. Алгоритм может быть некоторой последовательностью вычислений, а может - последовательность действий нематематического характера.
Для любого алгоритма справедливы следующие свойства алгоритма.
1. Дискретность - свойство алгоритма, при котором его исполнение разбивается на отдельные элементарные действия, число которых конечно.
2. Понятность - каждое элементарное действие должно быть понятно исполнителю.
3. Детерминированность - каждое элементарное действие должно выполниться только строго определенным образом, и никак иначе.
4. Массовость - применимость данного алгоритма к целому классу задач.
5. Результативность - любой алгоритм обязательно должен приводить к результату.
Алгоритм может быть записан различными способами: на естественном языке в виде описания; в виде графических блок-схем; на специальном алгоритмическом языке.
Сначала два определения:
· Правила, определяющие структуру текста, называются синтаксисом языка.
· Правила, управляющие смыслом текста, называются семантикой языка.
2.2.1. Метаязык Бэкуса-Наура (язык БНФ)
Для описания синтаксиса алгоритмического языка требуется, в свою очередь, соответствующий язык. Такой язык назовем метаязыком (над'языком). Для этой цели не подходят естественные языки из-за их многозначности, и поэтому используются специальные, так называемые формальные языки. Наиболее распространенными являются язык металингвистических формул Бэкуса-Наура (БНФ) и язык синтаксических диаграмм Н. Вирта.
Язык БНФ похож на математические формулы и поэтому его называют языком метаформул. В левой части метаформулы указывается понятие, а в правой – множество значений этого понятия. Все понятия (метапеременные) обычно заключаются в угловые скобки < >.
Например, понятия: <Число> или <Арифметическое выражение>.
Левая и правая часть соединяются знаком ::= (метасимвол) – "это есть".
Все возможные значения метапеременной разделяются вертикальной чертой, | - (либо, или).
Пример: <Цифра> ::= 0|1|2|3|4|5|6|7|8|9
Определим выражения из двух переменных, А и В. Для этого напишем определение синтаксиса на языке БНФ:
<переменная>::=A|B
<выражение>::=<переменная>|<переменная> + <переменная >| <переменная> - <переменная>
В соответствии с этим определением синтаксиса выражения могут иметь следующий вид:
A, B, A+B, A+A, B+A, B+B, A-A, A-B, B-A, B-B
Другой пример иллюстрирует описание синтаксиса для представления двоичных кодов, то есть любых непустых последовательностей нулей и единиц:
<двоичная цифра>::= 0 | 1
<двоичный код>::= <двоичная цифра>|<двоичный код> <двоичная цифра>
Для задания синтаксических конструкций произвольной длины используются два метасимвола "{" и "}". Заключенная в эти скобки конструкция может повториться нуль или более раз.
<двоичный код>::= <двоичная цифра>|{< двоичная цифра >}
Может использоваться также метапеременная < пусто > .
Нотация БНФ широко используется в описании синтаксиса компиляторов и интерпретаторов.
2.2.2. Синтаксическая диаграмма Н. Вирта
Используется для графического изображения структуры синтаксических конструкций. Основной элемент диаграммы: основной символ или понятие языка.
Из каждого элемента выходит одна или несколько стрелок, указывающих на элементы, непосредственно следующих за данным элементом.
Например, определение переменной может быть выполнено следующим образом:
В свою очередь, арифметическое выражение определяется следующей синтаксической диаграммой:
Таким образом, данная диаграмма позволяет описать следующее множество арифметических выражений:
A, B, A+B, A+A, B+A, B+B, A-A, A-B, B-A, B-B.
С помощью синтаксической диаграммы удобно задавать и конструкции произвольной длины, например, определить такое понятие, как двоичный код:
![]() |
Еще один пример показывает так называемое рекурсивное определение, когда определяемый элемент выражается через самого себя. Например, необходимо отобразить понятие, под которым подразумевается буква T, заключенная произвольное количество раз в круглые скобки:
(T), ((T)), (((T)))
В БНФ такое определение выглядит таким образом:
<слово>::=(T)|(<слово>)
Синтаксическая диаграмма:
|
|
Метаязык БНФ более строг и точен, язык синтаксических диаграмм более нагляден. Например, идентификатор переменной, используемый в языках программирования, должен начинаться обязательно с буквы, и может состоять из латинских букв и цифр:
<Идентификатор>::= <Буква>|<Идентификатор><Цифра>| <Идентификатор><Буква>
2.2.3. Графические блок-схемы
Еще один, очень распространенный способ описания алгоритмов - это использование графических блок-схем. Он обладает высокой наглядностью, но для сложных алгоритмов довольно громоздок. Тем не менее, этот способ широко используется для описания алгоритмов. Смотрите рис. 2.4.1.
2.3. Язык программирования высокого уровня C++
Язык C был разработан в 1972 году сотрудником Bell Laboratories Денисом Ричи для использования в разработанной им совместно с Кеном Томпсоном операционной системой Unix. На языке С написан компилятор этого языка, а также операционная система Unix для мини-ЭВМ PDP-11. Этот язык получил развитие в виде созданного фирмой Borland для семейства микропроцессоров 8086, 8088 и операционной системы MS DOS языка программирования под названием "Turbo-C".
Затем в начале 80-х годов также сотрудник Bell Laboratories Бьерн Страуструп (см. фото) на основе языка С разработал значительно более мощный язык С++. Этот язык реализует объектно-ориентированный подход к программированию. В конце ХХ века С++ приобрел статус стандартного языка программирования.
В начале XXI века появился еще один преемник языка С – это C# (произносится: си шарп). Музыкальный знак диез указывает на повышение тона. Этот язык предложен фирмой Microsoft как конкурент языка Java и представлен как язык компонентной сборки. Его дальнейшая судьба прояснится со временем.
В настоящее время язык С++ является мощным и эффективным средством разработки разнообразного программного обеспечения.
2.3.1. Основные принципы языка С++
Язык программирования C++ создан на основе нескольких базовых принципов, которые в настоящее время характерны для современных языков.
1. Используется структурное программирование – это метод проектирования программ в виде последовательной структуры функционально законченных блоков, исполняемых один за другим.
2. Реализован принцип проектирования: "Сверху – вниз". Это значит, что сначала проект разбивается на несколько простых задач, решаемых отдельно, т.е. для каждой задачи создается отдельный программный модуль. Затем следует сборка модулей в единый программный продукт.
3.Применяются концепции объектно-ориентированного программирования. Сущность их состоит в следующем:
· Использование классов – типов, в которых объединяются структуры данных и методы их обработки с ограничением доступа к данным класса. Эта концепция называется инкапсуляцией. Конкретные переменные типа "класс" называются объектами.
· Наследование - это механизм создания новых классов, использующих свойства и методы предыдущих классов.
· Использование сходных методов для разных классов и объектов называется полиморфизмом.
4. В язык С++ встроена возможность расширения базовых конструкций языка за счет использования большого количества внешних библиотек.
5. Предусмотрены способы переносимости программ с небольшими изменениями на другую операционную или аппаратную среду.
Основное назначение языка С++ - это системное программирование. Поэтому считается, что это относительно низкоуровневый язык. По объему и скорости выполнения программы, написанные на С++, приближаются к программам, написанным на ассемблере.
2.3.2. Структура программы на языке С++
Приведем два определения:
· Базисные элементы языка называются лексемами: for, if, while, sizeof, far, const, ...
· Слова, используемые для именования любых объектов в программе, называются идентификаторами.
Программа на С++ состоит из директив препроцессора, объявлений глобальных переменных, одной главной функции {main()} и совокупности неглавных функций. Пример программы:
/* Заголовки и комментарии */
/* директивы препроцессора */
#include <stdio.h>
#include <iostream.h>
#include <conio.h>
#include <math.h>
#define PI 3.14159
/* глобальные переменные */
int Count;
// ---------- Неглавная функция ----------------
int Mult(int X, int Y) { return X*Y;}
// ---------- Главная функция ----------------
void main()
{ int A,B;// Локальные переменные
A=2; B=3;// Операторы
Count=Mult(A,B)/(A+B);// Операторы
prinf("Count = %i\n", Count);
}
Функции, вызываемые из функции main(), имеют ту же структуру, что и главная функция. Препроцессор, который входит в состав компилятора, выполняет дополнительные действия над текстом программы, определяемые директивой '#'.В частности, директива #include <имя библиотеки> включает в текст программы прототипы библиотечных функций. Чтобы включить содержимое из файла, находящегося на диске, необходимо вызов записать следующим образом:
#include "mylib.cpp"
Директива компилятора #define <stroka1> <stroka2> в тексте программы все встреченные включения <stroka1>заменяет на <stroka2>.
Система программирования Borland C++ 3.1., реализованная в виде интегрированной среды, состоит из следующих компонентов:
· Компилятор BIN\BC.exe
· Редактор текста
· Редактор связей (компоновщик, сборщик)
· Библиотеки различного назначения
· Файлы документации *.doc
2.3.3. Типы данных языка С++
В математике мы различаем переменные в соответствии с их характеристиками, т.е. вещественные, целые, логические, множества и т.д. Программа, являясь моделью явлений внешнего мира, представляет его характеристики, выражая их в виде типизированных данных.
C++ является языком с сильной типизацией, т.е. все данные, получаемые извне, должны принадлежать заранее известному типу. В нем имеются и стандартные (предопределенные) типы, и существует возможность создания собственных типов данных, наиболее подходящих для конкретных практических приложений.
Например, подсчет количества каких-либо объектов в реальном мире возвращает данные целого типа, а операции измерения (т.е. сравнения с эталоном) – данные вещественного типа. В то же время потоки текстовой информации формируют данные символьного типа, а реакции на события – данные логического типа.
Рассмотрим более подробно типы данных, применяемых в практике программирования на языке C++.