Материал: Основы алгоритмизации и программирования вычислительных процессов. Кононов А.Д., Кононов А.А

Контрольные вопросы и упражнения

1.Перечислить этапы подготовки и решения задачи на ЭВМ.

2.Охарактеризовать каждый из перечисленных этапов.

3.Кто выполняет этап постановки задачи?

4.В чем заключается построение математической модели задачи?

5.Что должно учитываться при выборе численного метода решений?

6.В чем заключается трансляция программы? Отладка программы?

Занятие 2. Неформальное программирование. Способы описания схем алгоритмов

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

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

Если алгоритм представляет собой последовательность инструкций, которые могут быть выполнены на ЭВМ (непосредственно или после автоматической обработки – трансляции, состоящей в приведении алгоритма к исполнимому в ЭВМ виду), то такой алгоритм называется программой. Устройство ЭВМ, которое выполняет инструкции программы, называется центральным процессором (ЦП); с ним непосредственно связано одно из устройств ЭВМ, именуемое оперативной памятью (ОП). ЦП и ОП, вместе с устройствами обмена информацией с окружающим миром (ввода исходных данных и текста программы и вывода результатов), образуют вычислительный комплекс ЭВМ – вычислитель. Таким образом, вычислитель это устройство, которое исполняет алгоритм. Вычислители бывают узкоспециализированными (выполняющими

6

однотипные операции) и универсальными (могут перестраиваться на выполнение того или иного алгоритма). ОП состоит из элементов – ячеек памяти, каждая из которых используется для запоминания числа или цифрового кода.

Ячейка памяти имеет следующие свойства:

а) в ней значение может сохраняться до выключения ЭВМ; б) если в ячейку не заносилось значение, она имеет неопределенное со-

стояние, воспринимаемое как некоторое случайное значение; в) занесение в ячейку нового значения приводит к автоматическому сти-

ранию прежнего; г) хранимое в ячейке значение может многократно использоваться в вы-

числениях.

Контрольные вопросы и упражнения

1.Дать определение алгоритмического процесса.

2.Дать определение программы.

3.Перечислить устройства, входящие в состав компьютера, и выполняемые ими функции.

4.Дать определение центрального процессора, оперативной памяти, вычислителя.

5.Назвать свойства ячейки памяти.

Способы описания схем алгоритмов Алгоритм решения задачи можно описать различными способами: с по-

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

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

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

Пример 1. Например, для алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух положительных чисел N и M (которому более двух тысяч лет), описание с помощью словесного способа будет иметь следующий вид:

Этап 1. Положить X, равным N, и Y, равным M. Перейти к этапу 2.

Этап 2. Проверить: X равно Y? Если Да, то перейти к этапу 6, иначе - перейти к этапу 3.

7

Этап 3. Проверить: Х больше, чем Y? Если Да, то перейти к этапу 5, ин а- че перейти к этапу 4.

Этап 4. Произвести обмен значениями ячеек Х и Y. Перейти к этапу 5. Этап 5. Определить разность значений Х и Y. Затем положить Х, равным

Y, и Y, равным значению полученного остатка. Перейти к этапу 2.

Этап 6. Принять Х или Y за искомое значение НОД и прекратить процесс вычисления.

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

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

Пример 2. Требуется решить квадратное уравнение ax2 +bx + c = 0 в области действительных чисел. Математической моделью этой задачи является известная формула корней квадратного уравнения:

На основании этой формулы запишем алгоритм:

1.Задать значения a,b,c

2.Вычислить дискриминант d = b2 − 4ac

3.Сравнить дискриминант с нулем, если он больше нуля, то вычислить корни по формуле

и перейти к пункту 4, иначе сообщить: «В области действительных чисел уравнение решений не имеет»

4. Записать результат: «Корни уравнения x1 и x2 ».

Пример 3. Формульно-словесная запись вычисления выражения

будет иметь следующий вид:

Этап 1. Если x>0, то перейти к этапу 2, иначе перейти к этапу 3. Этап 2. Положить y = x . Перейти к этапу 4.

8

Этап 3. Положить y = 2x . Перейти к этапу 4.

Этап 4. Принять значение y за искомый результат и прекратить процесс вычисления.

Пример 4. В этом примере формульно-словесный способ записи алгоритма Евклида нахождения D=НОД(N,M) двух конечных положительных чисел N и M (N>M) может быть записан в виде:

1)разделим N на M, получим остаток

N=Mq1+R1,

если R1=0, то конец: D=M, иначе 2) разделим M на R1

M=R1q2+R2,

если R2=0, то конец: D= R1, иначе 3) разделим R1 на R2

и т.д.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Здесь qi – частные, а Ri – остатки на каждом i-ом этапе деления. Остатки – целые положительные числа, они уменьшаются до значения, равного нулю на каком-то k-ом этапе. Это описание алгоритма Евклида понятно человеку, но недоступно ЭВМ, так как содержит «и т. д.».

Запишем этот алгоритм более формально. Суть алгоритма в том, что ка ж- дый следующий шаг отличается от предыдущего тем, что делитель становится делимым, а остаток – делителем и мы приходим к следующему словесному описанию алгоритма Евклида:

1)Возьмем в качестве Делимого N, в качестве Делителя M.

2)Разделим Делимое на Делитель, получим Остаток.

3)Если Остаток равен нулю, то конец: перейдем к пункту 4, иначе возьмем в качестве Делимого Делитель, в качестве Делителя Остаток, перейдем

кпункту 2.

4)Результат – последний Делитель.

Вэтой записи алгоритма компьютеру не нужно ничего «домысливать», так как отсутствуют многоточие и «и т. д.».

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

Переменная – это ячейка памяти вычислителя вместе с ее содержимым,

которое называется значением переменной. Действия, которые записаны в тексте программы как действия над переменными, фактически выполняются над

9

их значениями.

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

Теперь алгоритм Евклида может быть записан в виде:

1)Ввод (Делимое, Делитель)

2)Остаток:= МОD (Делимое, Делитель)

3)Если Остаток = 0, то перейти к п.4, иначе { Делимое := Делитель, Делитель := Остаток, Перейти к п.2 }

4)Вывод (Делитель).

В последней форме алгоритма Евклида использованы обозначения: := операция присваивания;

MOD (A,B) – операция вычисления целочисленного остатка от деления А

на В.

Вновь переходя к словесно-формульному способу описания алгоритма, заменим слово «Делимое» на буквенное обозначение N, «Делитель» на M, «Остаток» на R. Тогда получим:

1)Ввод (N,M)

2)R := MOD (N,M)

3)Если R = 0, то перейти к п.4, иначе { N:=M, M := R, перейти к п.2 }

4)Вывод (М).

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

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

10