Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ ПРОГРАММ).pdf

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

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

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

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

Исполнение: язык программирования может использовать специальные конструкции для определения и манипулирования структурами данных и управления процессом вычислений.

Всё множество языков программирования можно разделить на две группы: языки низкого уровня и языки высокого уровня:

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

Трансляторы

Процедурно-ориентированные

Объектно-ориентированные

Ассемблеры

Язык машинных команд

Высокого уровня

Низкого уровня

К языкам низкого уровня относятся языки ассемблера (от англ. to assemble – собирать, компоновать). В языке ассемблера используются символьные обозначения команд, которые легко понятны и быстро запоминаются. Вместо последовательности двоичных кодов команд записываются их символьные обозначения, а вместо двоичных адресов данных, используемых при выполнении команды, - символьные имена этих данных, выбранные программистом. Иногда язык ассемблера называют мнемокодом или автокодом.

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

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

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

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

2.3 Реализация основных алгоритмических структур на языке программирования

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

Для первых компьютеров программисты писали програм­мы в двоичных кодах, т. е. на машинном языке. Каждая команда машинного языка задает некоторое элементарное действие центрального процессора.

Важным этапом в развитии программирования явилась разработка языков программирования высокого уровня (ЯПВУ) — специальных искусственных языков, прибли­женных к обычному разговорному языку (английскому). Примеры таких языков: FORTRAN, Basic, Pascal, С. Боль­шинство языков высокого уровня универсальны, т. е. пред­назначены для решения широкого круга задач.

Первая цель создания ЯПВУ — облегчить создание про­грамм. Вторая цель — сделать программы переносимыми, т. е. уменьшить количество труда по адаптации программ для новых типов компьютеров.

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

Компилятор — это программа, автоматически преобразу­ющая (компилирующая) исходный код ЯПВУ в машинный код и создающая таким образом исполняемый файл. Он мо­жет быть запущен на исполнение операционной системой. В ОС Microsoft такие файлы могут иметь расширения ехе, com, dll.

Интерпретатор — это программа, преобразующая код ЯПВУ в машинный код шаг за шагом, т. е. каждая коман­да преобразуется интерпретатором и сразу выполняется компьютером, затем интерпретатор преобразует следую­щую команду, компьютер ее выполняет и т. д. (интерпретатор — «синхронный переводчик»). Недостаток интерпрета­торов — низкая скорость выполнения программ. Примеры: интерпретаторы языков Basic и Java Script. Для языка Basic в настоящее время существуют как интерпретаторы, так и компиляторы.

ГЛАВА III. ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ ПРОГРАММ

3.1 Линейные программы

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

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

Для каждой переменной задается ее имя и тип, например:

var number : integer; х, у : real; option : char;

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

Тип переменных выбирается исходя из диапазона и требуемой точности представления данных.

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

const number : integer = 100; x : real = 0.02; option : char = 'ю';

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

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

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

Далее приведены операции ПАСКАЛЯ, упорядоченные по убыванию приоритетов.

1. Унарная операция not, унарный минус -, взятие адреса @.

2. Операции типа умножения:* / div mod and shl shr.

3. Операции типа сложения: + - or xor.

4. Операции отношения: = о < > <= >= in.

Функции, используемые в выражении, вычисляются в первую

очередь.

Примеры выражений:

t + sin (х)/2 * х —результат имеет вещественный тип; а <= Ь + 2 —результат имеет логический тип;

(х > 0) and (у < 0) —результат имеет логический тип.

Структура программы

Программа на ПАСКАЛЕ состоит из необязательного заголовка, разделов описании и раздела операторов:

program имя; {заголовок) разделы описаний begin раздел операторов end. (* программа заканчивается точкой *)

Программа может содержать комментарии, заключенные в фигурные скобки {} или в скобки вида (* *).

3.2 Программы с использованием ветвлений

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

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

Простым условием (отношением) называется выражение, составленное из двух арифметических выражений или двух текстовых величин (иначе их еще называют операндами), связанных одним из знаков: 

< - меньше, чем...

> - больше, чем...

<= - меньше, чем... или равно

>= - больше, чем или равно

<> - не равно

= - равно

В общем случае полная форма конструкции условного оператора имеет вид:

if  <логическое выражение>  then  <оператор 1> else    <оператор 2>

Условный оператор работает по следующему алгоритму:

Сначала вычисляется значение логического выражения, расположенного за служебным словом IF. Если его результат истина, выполняется <оператор 1>, расположенный после слова THEN, а действия после ELSE пропускаются; если результат ложь, то, наоборот, действия после слова THEN пропускаются, а после ELSE выполняется <оператор 2>.

Задача.

Вывести на экран большее из двух данных чисел.

Var
    x, y : integer; {вводимые числа}

Begin
    writeln('Введите 2 числа '); {вводим два целых числа через пробел}
    readln(x,y);

    if x>y
      then
          writeln (x)  {если х больше y, то выводим х}

      else
          writeln (y)  {иначе выводим y}
     End.

Можно также использовать и сокращенную (неполную) форму записи условного оператора.
 Эта форма  используется тогда, когда в случае невыполнения условия ничего делать не надо.

Неполная форма условного оператора имеет следующий вид:

if  <логическое выражение> 
  then

      <оператор>

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

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

Если в качестве оператора должна выполниться серия операторов, то  они заключаются в операторные скобки begin-end. Конструкция Begin ... End называется составным оператором.

if  <логическое выражение>
  then

      begin

         оператор 1;
         оператор 2;
         ...
      end
  else   
      begin

        оператор 1;
        оператор 2;
         ...
      end;

Составной оператор - объединение нескольких операторов в одну группу. Группа операторов внутри составного оператора заключается в операторные скобки (begin-end).

begin