Записи алгоритмов на языках программирования

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

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

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

алгоритма это решает проблему или выполняет задачу.

АЛГОРИТМ — это рецепт. Ведущий к решению данной задачи; набор команд относительно некоторых объектов (данных) — с определенным порядком выполнения. Эти команды выполняются устройством. Которое в ответ на сигналы. Представляющие команды. Реагирует на их реализацию. Устройство может быть представлено человеком. Компьютером или другим устройством.
(источник: PWN Encyclopedia)

Алгоритмы выражаются многими способами: на естественном языке. Графически с помощью диаграммы или в так называемом псевдокоде (языке для выражения алгоритмов. Независимом от существующих. Доступных языков программирования).

Представьте себе. Что человек хочет купить компьютер и ему нужно настроить его так. Чтобы вычислить его цену (добавив цены его частей).
Простейшее решение. Реализующее вышеуказанную задачу. Показано ниже:

  1. Выберите процессор из прайс - листа и сохраните его цену.
  2. Выберите модули оперативной памяти из прайс-листа и сохраните их цену.
  3. Выберите материнскую плату из прайс-листа и сохраните ее цену.
  4. Выберите видеокарту из прайс-листа и сохраните ее цену.
  5. Выберите жесткий диск из прайс-листа и сохраните его цену.
  6. Выберите CDROM или DVD-привод из прайс-листа и сохраните его цену.
  7. Выберите звуковую карту из прайс-листа и сохраните ее цену.
  8. Подберите другие необходимые аксессуары и сохраните их цены.
  9. Суммируйте все цены.

Изображение - alg 1
Это решение закодировано на естественном языке. Графически этот алгоритм можно представить так. Как показано на рисунке.

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

Этот алгоритм понятен мужчине. Его можно наносить с помощью ручки и листа бумаги.
Теперь возникает вопрос: как задачу расчета цены может выполнить компьютер?

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

Однако с самого начала мы сталкиваемся с некоторыми фундаментальными проблемами: что на самом деле означает формула

Так как программа основана на алгоритме. То и будет выполняться компьютером его инструкции должны быть сформулированы в терминах компьютерных действий.

Заметьте также. Что обычно алгоритм обрабатывает некоторые входные данные (предоставлено пользователем) для получения выходных данных в результате.
При этом должно быть указано следующее: какие данные и когда должны подаваться в программу. И как они должны обрабатываться компьютером.
Есть 3 возможности (по крайней мере):

  • пользователь подает цены. Программа подсчитывает их сумму
  • пользователь предоставляет профили компонентов. Программа ищет их цены (например. Ищет в Интернете) и суммирует их
  • пользователь определяет критерии выбора оборудования. Программа — на основе этих критериев — подбирает конкретные устройства и суммирует их цены

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

1. Спросите пользователя о цене процессора 2. Спросите пользователя о цене материнской платы ... н-1. Суммируйте данные цены вверх n. Отображение результата пользователю 

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

Отметим, что приведенный выше простой алгоритм имеет достаточно общий вид. Его перевод на конкретный язык программирования требует принятия многих решений, например:

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

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

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

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

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

1. Спросите пользователя о цене процессора. 2. Если указанная цена не является числом. Сообщите пользователю об ошибке и перейдите к шагу 1. 3. Сохраните заданную цену процессора (для дальнейшего использования) 4. Спросите пользователя о цене материнской платы. 5. Если указанная цена не является числом. Сообщите пользователю об ошибке и перейдите к шагу 4. 6. Сохраните заданную цену материнской платы (для дальнейшего использования) .. другие компоненты ... другие компоненты n-1. Вычислите сумму составляющих n. Отображение результата 

В блок-схеме решения представлены ромбом.
Пример: блок-схема алгоритма расчета налога.

Изображение - алгоритм 2

Алгоритмы обычно пишутся в псевдокоде — формализованной (до некоторой степени) форме естественного языка. Независимой от любого языка программирования. Псевдокод гораздо ближе к языку программирования. Чем естественный язык. И его легче преобразовать в программу. Написанную на каком-то определенном языке программирования. Различные справочники по программированию представляют различные формы псевдокода. Можно легко определить свою собственную версию.
Псевдокод использует переменные — символическое представление данных (подробнее о переменных будет рассказано в следующей лекции; пока будем рассматривать их как переменные в математических формулах).
Операции над переменными кодируются с помощью операторов — символов математических операций: сложения. Вычитания, умножения. Деления и др. (подробнее об этом в следующей лекции).
Псевдокод также использует слова и выражения. Точно определяющие смысл фрагментов алгоритмов (действий. Инструкций). Например принятие решения может быть записано таким образом:

если (условие), то

или

если (условие), то
иначе

и итерационные циклы (т. е. повторное выполнение фрагментов алгоритма)

выполняйте до тех пор. Пока (условие) …

выполните изменение значения переменной i от p до l...

Тогда как ввод и вывод данных может быть выражен с помощью слов: чтение, запись.

Применяя символы +. — i * для выражения операций сложения. Вычитания и умножения. Скобки (как в математике) для группировки операций и специальные слова для выражения действий и решений. Алгоритм расчета налога можно записать следующим образом:

читать доход еслито налог = 17048,44 + 0,4 * (доход - 74048) иначе еслито налог = 6541,24 + 0,3 * (доход - 37024) еще налог = 0,19 * доход - 493,32 написать налог 

Такая нотация этого алгоритма демонстрирует две проблемы.

Во-первых, ошибка во входных данных изменяет последовательность шагов. Выполняемых алгоритмом. И вызывает возврат к инструкции считывания входных данных. В псевдокоде такое действие записывается как переход к определенному фрагменту алгоритма (перейти к …), обозначаемому меткой (метки-это слова. Заканчивающиеся двоеточием ‘:’).

если (условие). То {
действие 1
действие 2
}

Если условие выполнено. То выполняются действия. Сгруппированные внутри фигурных скобок.

dataInput1: напишите читать CPUprice если (CPUprice - это не число), то { напишите перейти к dataInput1 } dataInput2: напишите читать MBprice если (MBprice - это не число), то { напишите перейти к dataInput2 } ... результат = сумма цен результат записи 

Однако такая нотация приводит к тому. Что алгоритмы (и программы) плохо читаемы. Их логика сложна и подвержена ошибкам.
Вот почему большинство языков программирования больше не используют инструкцию go to (goto). Вместо этого применяются итерационные циклы. По этой причине блок-схемы также потеряли популярность (оказывается. Что блок-схемы не всегда можно перевести на языки без инструкции
Таким образом. Алгоритм расчета компьютерной цены должен быть выражен в другой форме. Давайте используем циклы итераций и введем булеву (логическую) переменную с именем dataRequired с 2 возможными значениями yes и no.

dataRequired = да выполнить до (dataRequired) { написать читать CPUprice если (CPUprice не является числом), то напишите else dataRequired = no } dataRequired = да выполнить до (dataRequired) { написать читать MBprice если (MBprice не является числом), то напишите else dataRequired = no } ... результат = сумма цен результат записи 

В начале значение переменной dataRequired равно yes, а условие в execute until выполняется. Поэтому начинается выполнение инструкций. Сгруппированных между фигурными скобками. Если считанные данные (CPUprice) не являются числом. То отображается сообщение Значение переменной dataRequired тогда не изменяется. И действия. Сгруппированные между фигурными скобками. Выполняются снова (поскольку условие в execute until все еще выполняется). Напротив, если CPUprice является числом. Переменная dataRequired получает значение no, и в этом случае условие в execute until больше не выполняется. И действия между фигурными скобками не выполняются.

Другая проблема. С которой мы сталкиваемся в этом алгоритме. — повторение подобных (почти идентичных) действий. Рассмотрим чтение цены процессора. Материнской платы и других компонентов — все эти операции выглядят одинаково. По этой причине мы могли бы изолировать эти действия и записать их в виде так называемой процедуры или функции Записанные один раз. Они могут быть выполнены многократно для различных компонентов компьютера.
Это означает. Что задача расчета цены компьютера делится на две подзадачи:

  • ввод и проверка данных
  • фактические расчеты

Каждая из этих проблем может быть решена отдельно. Концентрируясь на особенностях. Характерных для ее контекста.
Этот способ программирования называется структурным программированием.

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

Подводя итог:

  • Программы создаются для решения проблем или реализации каких-то задач.
  • Перед написанием программы. Реализующей какую-либо задачу. Должен быть разработан алгоритм ее решения.
  • Алгоритм-это рецепт. Набор команд. Выполняемых над данными. Описание преобразования входных данных в выходные.
  • Программа-это запись алгоритма и данных на заданном языке программирования.
  • Для выполнения программы ее представление на языке программирования должно быть переведено на машинный язык. Понятный процессору. Эта работа выполняется специальными программами. Называемыми переводчиками. Компиляторами или интерпретаторами.

Обратите внимание. Что программы не только отражают шаги (команды. Действия) алгоритмов. Но и представляют обработанные данные. Эти данные могут быть представлены в виде отдельных копий или сгруппированы в наборы (так или иначе связанные и/или упорядоченные). В таком случае можно говорить о структурах данных.

Таким образом. Можно привести еще одно определение программы (Н. Вирт):

ПРОГРАММА представляет собой конкретную формулировку абстрактного алгоритма. Основанного на конкретном представлении структуры данных.

Оба определения непротиворечивы. Первая, цитируемая в начале лекции (

Текст программы (ее исходный код) написан на языке программирования.
Каждый язык программирования имеет свой алфавит — набор символов (букв и цифр). Из которых строятся символы языка (последовательности символов). Синтаксические правила определите допустимые способы построения символов и допустимый порядок их появления в программе. Семантика определяет значение символов.

Например, в языке программирования. Алфавит которого строится из букв. Цифр и специальных символов. Имена переменных строятся из букв и цифр. Некоторые последовательности символов. Обозначающие языковые инструкции. Зарезервированы (Указывается способ соединения символов (например, формула

Существует множество (десятки тысяч) языков программирования. Их можно классифицировать по различным критериям.
Несомненно, самым важным является логическая структура языка и искусство создания программ с его использованием.
Императивные языки требуют спецификации последовательности шагов. Реализующих заданную задачу . Тогда как декларативные языки описывают отношения между данными в терминах функций (функциональные языки) или правил (реляционные языки, языки логического программирования), и результате выполнения программы получается путем применения к указанным особые отношения Объектно-ориентированного программирования состоит в объединении данных и операций над этими данными. Что дает возможность создавать и использовать в программах новые типы данных лучше отражает домен конкретной проблемы. Процедурного программирования (иногда ассоциируется с императивное Программирование) разделяет данные и функции. Не поставляет простые и адекватные способы отражения домен проблемы в структуры данных он использует.

Языки изображений

Примерами процедурных языков являются алгол. FORTRAN, PL/I. C. Объектно-ориентированными языками являются Smalltalk. Java, C++ и C#. Наиболее известным функциональным языком является Haskell. А языком логического программирования-Prolog.

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

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

В скомпилированных языках текст программы (исходный код) переводится в двоичный (промежуточный) код конкретной программой. Называемой компилятором. Другая (в большинстве случаев) программа. Обычно называемая linker, генерирует из промежуточного кода двоичный исполняемый файл программы (который готов к запуску) и сохраняет его на жестком диске в виде исполняемого файла (например. С расширением Именно так работают языки В других случаях компилятор производит символьный код. Который выполняется посредством интерпретации программой. Называемой интерпретатором. Язык Java ведет себя так.

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

Исходный или промежуточный код интерпретируемых языков считывается и выполняется специальной программой . Называемой интерпретатором, которая генерирует (на лету) инструкции ЦП. Соответствующие инструкциям. Найденным в источнике.
Примерами интерпретируемых языков являются: REXX, ObjectREXX, Perl, PHP.

Подводя итог: процесс программирования можно было бы изобразить с помощью следующего алгоритма:

Имиджевое программирование