Файл: Основные структуры алгоритмов: сравнительный анализ.pdf

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

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

Со всеми этими (а также некоторыми другими) задачами с успехом справляется Mathcad:

• математические выражения и текст вводятся с помощью формульного редактора Mathcad, который по возможностям и простоте использования не уступает, к примеру, редактору формул, встроенному в Microsoft Word;
• математические расчеты производятся немедленно, в соответствии с введенными формулами;
• графики различных типов (по выбору пользователя) с богатыми возможностями форматирования вставляются непосредственно в документы;
• возможен ввод и вывод данных в файлы различных форматов;
• документы могут быть распечатаны непосредственно в Mathcad в том виде, который пользователь видит на экране компьютера, или сохранены в формате RTF для последующего редактирования в более мощных текстовых редакторах (например Microsoft Word);
• возможно полноценное сохранение документов Mathcad 11 в формате Web-страниц (генерация вспомогательных графических файлов происходит автоматически);
• имеется опция объединения разрабатываемых Вами документов в электронные книги, которые, с одной стороны, позволяют в удобном виде хранить математическую информацию, а с другой — являются полноценными Mathcad-программами, способными осуществлять расчеты;
• символьные вычисления позволяют осуществлять аналитические преобразования, а также мгновенно получать разнообразную справочную математическую информацию.

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

Глава 2. Классификация алгоритмов

Различают три типа базовых структур:

• Следование
• Развилка
• Цикл

Рис. 2.1. Структура следования

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

Структура Развилка обеспечивает выбор одной из двух альтернатив: если < условие 1 > то

< действие 1 >

иначе

< действие 2 >

все

Существует сокращенная форма структуры Развилка, которая позволяет выполнить действие или пропустить его:

если < условие > то < действие >

все

Обобщением структуры Развилка является Множественный выбор:

если Var = Const1 то < действие 1 >

если Var = Const2 то < действие 2 >

если Var = ConstN то < действие N >

все

В зависимости от значения переменной Var выполняется одно из указанных действий, например, если Var = Const3, то выполняется < действие 3 >.

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

• цикл «от до»
• цикл «пока»
• цикл «до»

Цикл «от до» управляет повторением выполнения действия с помощью переменной цикла:

цикл от I:= N1 до N2

< действие >

кц

Здесь I - переменная цикла, N1, N2 - начальное и конечное значения переменной цикла, вычисляются один раз при входе в цикл. Переменная цикла пробегает все следующие друг за другом в порядке возрастания значения от начального до конечного. Изменение значения переменной цикла происходит автоматически после каждого выполнения действия, указанного внутри цикла. В зависимости от соотношения N1 и N2 цикл может не выполниться ни разу (N1>N2) или выполниться (N2-N1+1) раз.

В цикле «пока» управление внутри цикла осуществляется с помощью логического условия:

цикл пока < условие>

< действие >

кц

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

Третий тип структуры цикл «до» имеет вид:

цикл

< действие > до < условие>

кц

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

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

В зависимости от применяемых базовых структур различают следующие типы алгоритмов:

• линейные
• разветвляющиеся
• циклические.

2.1 Линейная алгоритмическая структура. Типовые примеры

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

Покажем общую структуру линейного алгоритма в виде блок-схемы.

начало

Обработка данных

Ввод данных

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

конец

Рис. 2.2. Блок схема

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

Для реализации процесса обработки данных используется оператор присваивания.

Результат вычислений помещается в область S оперативной памяти. Чтобы вывести результат из памяти на экран монитора необходимо использовать оператор вывода.

Операторы ввода данных:

• INPUT - оператор ввода данных с клавиатуры. Данные задаются в виде переменных. Переменная – это величина, значение которой может меняться в процессе выполнения программы. Для обозначения переменной используются их имена (идентификаторы) – последовательность до 40 латинских букв и цифр, начинающаяся с буквы. Данные могут быть следующих основных типов:
• целые INTEGER (Y%) – 2 байта в памяти (от -32768 до 32767),
• длинные целые LONG (Y&) – 4 байта (от -2³¹ до 2³¹-1),
• вещественные SINGLE (Y) – 6 знаков после , -4 байта (от -3.4Е+38 до 3.4Е+38),
• вещественные удвоенной точности DOUBLE (Y#) -16 знаков после ,– 8 байт (от -Е+308 до Е+308),
• символьные STRING (Y$) – последовательность символов до 32767 символов длиной.

Например: INPUT a,b или INPUT “Введите два числа”;a,b

• DATA, READ – операторы ввода данных из блока памяти. Например: DATA 3,4 : READ a,b

Оператор присваивания может быть использован как для ввода данных (Например: a=3 : b=4), так для вычисления выражений. (Например: S=a*b). Оператор присваивания вычисляет выражение, расположенное справа от символа присваивания (=) и результат присваивается переменной, расположенной слева от символа присваивания. При записи арифметического выражения используются арифметические операции и функции. Приоритет выполнения арифметических операций сохраняется. Функции можно использовать стандартные (встроенные) COS(X), SQR(X) … и задаваемые самим пользователем. (Например: Y=3*SQR(X)^2)

Для вывода данных используется оператор PRINT.

Например: PRINT S или PRINT “Площадь”;S или PRINT a,b,S

Для окончания программы используется оператор END. В начале программы можно использовать оператор очистки экрана – CLS.

Пример линейной программы вычисления площади прямоугольника и ее алгоритм в виде блок-схемы:

CLS

INPUT “Введите две стороны прямоугольника”; a,b

S = a * b

PRINT “Площадь”; S

END

2.2. Разветвляющая алгоритмическая структура. Основные операторы циклов. Типовые примеры

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

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

начало

Ввод a,b,c

D=b*b-4*a*c

d>0

X₁=(-b+SQR(d))/(2*a)

Корней нет

Вывод Х₁, Х₂

конец

X₂=(-b-SQR(d))/(2*a)

да

нет

Рис. 2.3. Разветвляющийся алгоритм

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

Для описания разветвляющегося алгоритма существуют операторы:

1. условный

блочной структуры:

IF условие THEN

блок действий 1

ELSE

блок действий 2

ENDIF

линейной структуры:

IF условие THEN блок 1 ELSE блок 2

Обе структуры могут быть использованы как в полной форме так и в усеченной – без блока ELSE.

При работе условного оператора сначала проверяется выполнение условия. Если условие выполняется (истинное), то реализуется блок 1, в противном случае – блок 2. Условие – это логическое выражение, использующее операции сравнения (=, <, > <=, >=, <>) и логические операции (AND, OR).

Программа решения квадратного уравнения с использованием условного оператора имеет вид:

CLS : INPUT A,B,C : D=B^2-4*A*C

IF D>0 THEN

X1=(-b+SQR(d))/(2*a) : X2=(-b-SQR(d))/(2*a) : PRINT X1,X2

ELSE

PRINT ”Решенией нет”

ENDIF

1. выбора (выражением может быть список через запятую 1,3,4 диапазон значений 1 TO 9; операция сравнения IS >=).

SELECT CASE выражение

CASE условие 1

блок операторов 1

CASE условие 2

блок операторов 2

CASE ELSE

блок операторов n

END SELECT

CLS : INPUT A,B,C : D=B^4*A*C

SELECT CASE D

CASE IS >0

X1=(-b+SQR(d))/(2*a)

X2=(-b-SQR(d))/(2*a) : PRINT X1,X2

CASE ELSE

PRINT ”Решенией нет”

END SELECT

END

2.3 Циклические алгоритмические структуры. Основные операторы ветвления. Типовые примеры

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

Циклы бывают с определённым количеством, неопределённым числом вычислений.

I = I_Н , I_K , h

тело цикла

условие

тело цикла

тело цикла

условие

да

да

нет

нет

I – параметр цикла

I_Н – начальное значение параметра

I_K – конечное значение параметра

h – шаг изменения параметра (приращение)

Рис. 2.4. Циклический алгоритм

Оператор цикла с параметром:

FOR I = I_Н TO I_K STEP h

тело цикла

NEXT I

Оператор цикла с предусловием:

DO WHILE условие продолжения вычислений (UNTIL условие прекращения вычислений)

тело цикла

LOOP

Оператор цикла с постусловием:

DO

тело цикла