Способы описания алгоритмов

Алгоритмы и их свойства

Основы программирования

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

Для любого алгоритма справедливы следующие свойства алгоритма.

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)|(<слово>)

Синтаксическая диаграмма:

(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++.

Дата добавления: 2014-11-29