Приложения к практическим ОАиП



ПРИЛОЖЕНИЕ 1

Алгоритмом называется точное описание, определяющее последовательность действий исполнителя, направленных на решение поставленной задачи.

Формы записи алгоритмов

На практике наиболее распространены следующие формы представления алгоритмов: словесная, графическая (блок-схемы), псевдокод и программа.

Словесный способ записи алгоритмов представляет собой описание алгоритма на естественном языке.

Пример. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.

Алгоритм может быть следующим:

1. задать два числа;

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

3. определить большее из чисел;

4. заменить большее из чисел разностью большего и меньшего из чисел;

5. повторить алгоритм с шага 2.

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

Словесный способ не имеет широкого распространения по следующим причинам:

— такие описания строго не формализуемы;

— страдают многословностью записей;

— допускают неоднозначность толкования отдельных предписаний.

Графический способ (или блок-схема) — описание структуры алгоритма с помощью последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. В таблице приведены наиболее часто употребляемые символы.

Название символа

Обозначение и пример заполнения

Пояснение

Процесс

Вычислительное действие или последовательность действий

Решение

Проверка условий

Модификация

Начало цикла

Предопределенный процесс

Вычисления по подпрограмме, стандартной подпрограмме

Ввод-вывод

Ввод-вывод в общем виде

Пуск-останов

Начало, конец алгоритма, вход и выход в подпрограмму

Документ

Вывод результатов на печать

Блок «процесс» применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения данных. Для улучшения наглядности схемы несколько отдельных блоков обработки можно объединять в один блок. Представление отдельных операций достаточно свободно.

Блок «решение» используется для обозначения переходов управления по условию. В каждом блоке «решение» должны быть указаны вопрос, условие или сравнение, которые он определяет.

Блок «модификация» используется для организации циклических конструкций. (Слово модификация означает видоизменение, преобразование). Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения.

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

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

Псевдокод занимает промежуточное место между естественным и формальным языками.

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

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

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

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

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

Программа — описание структуры алгоритма на языке алгоритмического программирования.

Основные алгоритмические конструкции

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

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

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

Линейный алгоритм Разветвляющийся алгоритм

Действие 1

Действие 2

Условие

Да

Нет

Действие 1

Действие 2

Условие

Да

Нет

Действие 1

Действие 2

Действие 1

Действие 2

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

Параметры

цикла

Параметры

цикла

условие

условие

Тело цикла

Тело цикла

нет

да

нет

Параметры

цикла

Параметры

цикла

условие

условие

Тело цикла

Тело цикла

нет

да

нет

Примеры составления блок-схемы алгоритма

Пример 1. Составить схему алгоритма вычисления значения:

Для построения блок – схемы алгоритма опишем последовательность действий, необходимых для решения данной задачи:

начало

ввод чисел a,b

вычисление х

вычисление z

вывод результата

конец

Исходя из этого, составляем блок-схему алгоритма согласно ГОСТ, используя соответствующие блоки.

Пример 2. Составить схему алгоритма вычисления значения: x=a+b при a>b, x=a*b, при a<=b.

ПРИЛОЖЕНИЕ 2

Основные элементы языка Pascal

Алфавит языка состоит из множества символов, включающих в себя буквы, цифры и специальные символы.

Латинские буквы: от А до Z (прописные) и от а до z (строчные), символ “подчеркивания”, который в языке считается буквой.

Цифры: арабские от 0 до 9 и шестнадцатеричные (первые 10 цифр от 0 до 9 — арабские, остальные шесть — латинские буквы: А, B, C, D, E, F).

Специальные символы: + — * / = , . : ; < > [ ] ( ) { } ‘, $, пары <> <= >= := (* *) (. .), пробел (символы (. .) соответствуют символам [ ], несколько пробелов считаются одним).

К спецсимволам относятся также служебные слова — abs, and, array, begin, case, const, dir, do, downto, else, end, for, function, goto, if, int, label, mod, not, of, or, procedure, program, repeat, shr, then, to, type, var, while, with и др. Смысл зарезервированных слов фиксирован строго. При этом набор зарезервированных слов может меняться от версии к версии.

Идентификатор — это последовательность букв, цифр и знаков подчеркивания, начинающихся не с цифры. Под идентификатором мы будем понимать ячейку памяти ЭВМ, которая имеет свое имя и в которой хранится информация. В Паскале строчные и прописные буквы в идентификаторах и служебных словах не различаются. Идентификаторы могут иметь произвольную длину, но значащими являются только первые 63 символа. Хорошим стилем является осмысленный выбор имени идентификатора. Зарезервированные слова не могут использоваться в качестве идентификаторов.

Комментарии заключаются либо в фигурные скобки { комментарий 1 }, либо в символы (* комментарий 2 *) и могут занимать любое количество строк. Последовательность из трех символов (*) начинает комментарий до конца строки. Текст комментария игнорируется при компиляции, если это не директивы компилятора, которые имеют вид {$ }.

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

В качестве констант могут использоваться целые, вещественные, шестнадцатеричные числа, логические константы, символы, строки символов, множества:

а) целые числа записываются без дробной части со знаком или без него;

б) вещественные числа записываются со знаком или без него, с фиксированной или плавающей точкой (например, +3.14 или -19е-5);

в) логическая константа — либо false либо true (ложь или истина);

г) символьная константа — любой символ, заключенный в апострофы (например, ‘<>‘, ‘Y’);

д) строковая константа — любая последовательность символов, заключенная в апострофы (например, ‘это моя строка’, ‘ «‘).

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

Переменными называются параметры программы, которые могут менять свое значение в процессе ее выполнения. Все без исключения переменные должны быть описаны в разделе программы, начинающемся со слова VAR. Затем следуют конструкции вида:

список идентификаторов переменных: тип1;

список идентификаторов переменных: тип2;

В списке имена переменных перечисляются через запятую. Кроме базовых типов Турбо Паскаля здесь можно использовать свои типы (описанные ранее в разделе Type).

Арифметические операции, функции, выражения

В Паскале определены следующие операции:

Унарные: not (отрицание);

Мультипликативные: * (умножение), / (деление), div (деление нацело), mod (остаток от целочисленного деления), and (логическое “И”);

Аддитивные: + (сложение), — (вычитание), or (логическое “ИЛИ”);

Отношения: = (равно), <> (не равно), < (меньше), > (больше), <= (меньше или равно), >= (больше или равно).

Примечание: в Паскале нет операции возведения в степень. Вместо этого для возведения в целую степень можно использовать операцию умножения, а в дробную – выражение, использующее операцию логарифмирования и потенцирования: xy=ey*lnx, что на языке Паскаль соответствует выражению exp(y*ln(x)) с использованием двух стандартных функций exp(<выражение>) и ln(<выражение>).

Стандартные функции Паскаля

Для вычисления наиболее распространенных математических функций в Турбо-Паскале предусмотрены следующие стандартные функции:

Обращение

Функция

Pi

Число π

Sin(x)

Синус х (х в радианах)

Cos(x)

Косинус х (х в радианах)

Arctan(x)

Арктангенс х (х в радианах)

Exp(x)

еx – экспонента

Ln(x)

Натуральный логарифм x

Sqr(x)

Квадрат числа х

Sqrt(x)

Квадратный корень из числа х

Abs(x)

Абсолютная величина числа х

Trunc(x)

Ближайшее целое, не превышающее х по модулю

Frac(x)

Дробная часть числа х

Int(x)

Целая часть числа х

Round(x)

Округление числа до ближайшего целого

Succ(x)

Определение следующего по порядку элемента из списка

Pred(x)

Определение предыдущего элемента из списка

Random

Псевдослучайное число в интервале [0; 1)

Random(x)

Псевдослучайное число в интервале [0; х)

.

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

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

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

вычисления в круглых скобках;

вычисление значений функций;

унарные операции ( not,+,- );

операции типа умножения ( *,/,div,mod,and );



Страницы: Первая | 1 | 2 | 3 | ... | Вперед → | Последняя | Весь текст




map