Занятие 7.
|
Наконец-то, уважаемый подписчик, в нашем распоряжении имеется достаточно материала для того, чтобы научиться записывать некоторые разновидности простейших линейных алгоритмов. Для этого мы предварительно определим понятие линейного алгоритма, перечислим их разновидности, а также изучим комады, их которых они строятся. ПОСТРОЕНИЕ ЛИНЕЙНЫХ АЛГОРИТМОВ НА АЯ 1. Общие представления о линейных алгоритмах. Любой алгоритм характеризуется способом регулирования последовательности выполнения своих команд. По этому признаку алгоритмы распределяются на три вида: линейные, разветвляющиеся и циклические. Линейным алгоритмом называется такой алгоритм, значения результатов которого можно получить посредством однократного выполнения каждой из последовательности его команд. Сразу отметим, что линейный алгоритм в чистом виде – явление достаточно редкое. Чаще всего мы будем иметь дело с линейными фрагментами алгоритмов. Из определения линейного алгоритма следует, что он может быть построен только из простых команд (см. правило “Команды алгоритма” из четвёртого занятия). Поэтому здесь мы будем использовать исключительно команды присваивания и команды обращения к алгоритмам-процедурам. Я глубоко убеждён, что научить основам алгоритмизации можно только посредством демонстрации алгоритмов решения специально подобранных элементарных задач с сопутствующим глубоким их разбором. Будем называть такие алгоритмы базовыми. Для удобства изучения базовые линейные алгоритмы распределим на такие группы: · алгоритмы с результатами числового типа; · алгоритмы с результатами логического типа. В свою очередь, среди базовых линейных алгоритмов с результатами числового типа выделим: · алгоритмы, использующие арифметику вещественных чисел; · алгоритмы, использующие арифметику целых чисел. Главная особенность базовых алгоритмов состоит в том, что ими практически исчерпывается весь арсенал элементов алгоритмизации. Одни базовые алгоритмы демонстрируют определённые специфические приёмы и методы решения задач, другие решают, так называемые, основные задачи. Отметим, что алгоритмы решения основных задач – это те, которые наиболее популярны и чаще других могут быть использованы в качестве вспомогательных при решении более сложных задач. Основное условие возможности построения линейного алгоритма: для данной задачи построение линейного алгоритма её решения считается возможным, если такой алгоритм может быть выполнен при любых допустимых значениях его аргументов, определённых условием самой задачи. 2. Команда присваивания. Команда присваивания предназначена для вычисления некоторого значения с последующей его передачей (присваиванием) указанной переменной. Общая форма записи команды присваивания такова: <имя переменной> := <выражение>, где служебное слово “:=” называется знаком присваивания. Команда читается так: “присвоить переменной <имя> значение выражения ...”. Такое прочтение соответствует правилу выполнения команды: сначала вычисляется значение выражения, а потом полученное значение присваивается указанной переменной. Знак присваивания делит команду на две части. В левой части может находиться любая переменная, в правой части может стоять любое выражение. При этом обязательно должны соблюдаться условия, которые называются условиями совместимости по присваиванию: · тип переменной должен совпадать с типом выражения; · переменной вещественного типа можно присвоить значение любого числового типа; · переменная и выражение могут иметь любой целочисленный тип. При невнимательном отношении к последнему из условий совместимости по присваиванию могут возникать как синтаксические, так и семантические (смысловые) ошибки. Синтаксическая ошибка – это нарушение правил записи алгоритма на АЯ. Семантические ошибки могут приводить или к невозможности выполнения отдельных команд алгоритма, или к ошибочным результатам выполнения алгоритма в целом. Приведём примеры использования переменных x: нат и y: цел в некотором алгоритме: · команда присваивания x := –100 содержит синтаксическую ошибку, поскольку переменной x натурального типа невозможно присвоить отрицательное значение; · последовательность команд присваивания y := 101; x := y – 100 является правильной и синтаксически, и семантически; действительно, переменной целого типа y вполне допустимо присвоение значения 101, а выполнение второй из команд присваивания даёт допустимое значение для натуральной переменной x; · последовательность команд присваивания y := 1; x := y – 100 является правильной синтаксически, но ошибочной семантически; действительно, в результате попытки выполнения второй команды присваивания обнаруживается невозможность присвоения отрицательного значения –99 натуральной переменной x. И наконец. Не следует путать знак присваивания “:=” со знаком “=”. Знак “:=” указывает исполнителю алгоритма на необходимость выполнения вполне определённого “физического” действия (присвоения переменной значения выражения). В то же время знак “=” никаких реальных действий не предусматривает и используется исключительно для сравнения величин. Более того, если с математической точки зрения запись A=A+1 является бессмысленной, то запись вида A := A+1 в алгоритмах встречается чрезвычайно часто. Смысл её состоит в том, что значение переменной A необходимо увеличить на единицу. Команда присваивания – важнейшей команда АЯ! Действительно, если мы считаем, что алгоритм описывает процесс преобразования значений аргументов в значения результатов, то единственным средством реализации таких преобразований может быть только команда присваивания. Команды обращения к алгоритмам-процедурам мы с вами, уважаемый подписчик, рассмотрим в следующий раз. 3. Пример построения линейного алгоритма. Алгоритм L-1. “Вычисление функции”. Для произвольных заданных значений переменных x и a построить алгоритм вычисления значения функции
алг ЗначФункции ( a, x: вещ ): вещ дано произвольные значения a, x надо значение функции нач n, m: вещ n := 2 + a * a m := n + Sin(x) n := n * Sin(2) / Cos(2) ЗначФункции := Sqrt(m) / n – Ln(m) / Ln(10) кон Алгоритм ЗначФункции (Значение Функции) демонстрирует основные приёмы алгоритмизации вычисления выражений, используя арифметику вещественных чисел. При построении линейного алгоритма вычисления выражения важно предварительно убедиться в возможности этого. Поскольку условие задачи говорит о допустимости произвольных значений исходных данных, то необходимо сначала исследовать, всегда ли будут возможны соответствующие вычисления. Несложный анализ показывает, что при любых a и x под корнем никогда не появится отрицательное значение, знаменатель всегда будет отличен от нуля, а под знаком логарифма будут только положительные значения. Именно поэтому для решения данной задачи возможно построение линейного алгоритма. Ну, а поскольку результатом вычисления должно быть единственное вещественное значение, то целесообразно оформить алгоритм в виде функции. При внимательном рассмотрении заданного выражения обращает на себя внимание наличие совпадающих фрагментов: трижды встречается фрагмент a2 + 2 и дважды – фрагмент sin x + a2 + 2. Поэтому целесообразно вычисление указанных фрагментов выполнить отдельно. Это, с одной стороны, позволит избежать повторения одних и тех же вычислений, а с другой стороны, сократит текст алгоритма. Для этого используются промежуточные переменные n и m. Переменной n присваивается значение фрагмента a2 + 2. Переменной m присваивается значение фрагмента sin x + a2 + 2. Обратите внимание, что переменная m получает своё значение с использованием ранее вычисленной переменной n. Так удаётся сократить количество вычислений. Теперь при вычислении всего выражения в целом переменная m нам понадобится дважды (для извлечения квадратного корня и вычисления логарифма). А вот переменная n нам понадобится всего один раз (в знаменателе). Последнее даёт нам возможность выполнить, так называемое, переназначение переменной n. Используем переназначение вот для чего. В целях упрощения целесообразно записать вычисление знаменателя отдельно. Поэтому третья команда алгоритма присваивает переменной n значение знаменателя выражения, используя при этом предыдущее её значение. Так нам удалось избежать использования лишней промежуточной переменной. Последняя команда алгоритма вычисляет окончательное значение функции с использованием переменных n и m. При этом выражение для вычисления оказывается весьма простым, не смотря на то, что исходное выражение было достаточно сложным и громоздким. Таким образом, здесь продемонстрирован ещё один приём, часто используемый при алгоритмизации вычислений: разбиение большого, сложного и громоздкого выражения на отдельно вычисляемые части через использование промежуточных переменных. Возможные возражения в таких случаях могут быть связаны с использованием “лишних” переменных. Однако более важными здесь оказываются преимущества упрощения и уменьшения вероятности допустить ошибку. Уважаемый подписчик! Чтобы получить более подробное изложение материала занятия №7 “Построение линейных алгоритмов на АЯ”, перейдите по ссылке http://a-morgun.narod.ru/a06-01/a0006-0001-0005.html. Там вы найдёте подробный разбор примеров построения и других линейных алгоритмов, использующих арифметику вещественных чисел. При необходимости задать вопрос, проконсультироваться, уточнить или обсудить что-либо обращайтесь через Гостевую книгу моего персонального сайта http://a-morgun.narod.ru С уважением, Александр. |
.| В избранное | ||
