Козенко С.Л. Алгоритмизация инженерных задач

Подождите немного. Документ загружается.

АЛГОРИТМИЗАЦИЯ

ИНЖЕНЕРНЫХ

ЗАДАЧ

Методические указания

Санкт"Петербург

2005

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

высшего профессионального образования

САНКТ"ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

Составитель С. Л. Козенко

Рецензент канд. техн. наук С. В. Беззатеев

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

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

вычислительных задач. Рассмотрены примеры составления схем алго"

ритмов, приведены пояснения.

Предназначены для студентов всех специальностей 1"го факульте"

та, изучающих дисциплины «Алгоритмизация инженерных задач»,

«Информатика», а также могут быть полезны студентам других спе"

циальностей для изучения дисциплин со схожей тематикой.

Подготовлены кафедрой компьютерных систем автоматизации и

рекомендованы к изданию редакционно"издательским советом Санкт"

Петербургского государственного университета аэрокосмического при"

боростроения

Редактор Г. Д. Бакастова

Компьютерная верстка А. Н. Колешко

Сдано в набор 15.03.05. Подписано к печати 20.04.05. Формат 60´ 84 1/16.

Бумага офсетная. Печать офсетная. Усл. печ. л.2,67. Усл. кр."отт. 2,79. Уч. "изд. л. 2,55.

Тираж 400 экз. Заказ №

Редакционно"издательский отдел

Отдел электронных публикаций и библиографии библиотеки

Отдел оперативной полиграфии

СПбГУАП

190000, Санкт"Петербург, ул. Б. Морская, 67

ПРЕДИСЛОВИЕ

Усложнение научных и инженерных задач способствует стреми"

тельному росту процесса автоматизации их решения, так как ско"

рость и требуемая точность вычислений всецело зависят как от кор"

ректности используемых моделей и методов решения задач, так и от

эффективности их реализации.

В настоящее время применение средств вычислительной техники

как инструмента для решения инженерных задач требует углублен"

ных знаний в различных областях человеческой деятельности. Час"

то на практике необходимо преобразовать исходную задачу с учетом

дискретного характера машинных вычислений и представить про"

цесс ее решения на ЭВМ в виде последовательности шагов. Такой

подход должен выработать у будущего специалиста «алгоритмичес"

кое мышление», на основе которого дальнейший процесс разработки

программ не вызывает затруднений.

Решение любой задачи на ЭВМ содержит следующие этапы обра"

ботки.

1. Постановка задачи – формулирование задачи, определение кон"

кретной цели ее решения и результатов, которые должны быть полу"

чены, выработка критериев оценки этих результатов.

2. Формализация задачи – выбор математических методов реше"

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

3. Алгоритмизация – разработка алгоритма решения задачи, т. е.

представление процесса ее решения в виде шагов, этапов.

4. Программирование (кодирование алгоритма) – перевод алго"

ритма решения задачи на язык ЭВМ.

5. Отладка программы – выявление возможных синтаксических

или семантических (смысловых) ошибок и их устранение. На этом

этапе разрабатываются также тестовые примеры с целью проверки

работоспособности программы.

6. Получение результатов и их анализ –результаты должны быть

проанализированы на предмет их достоверности и возможности ис"

пользования в практической или научной деятельности. Если резуль"

таты не удовлетворяют поставленным требованиям, то осуществля"

ется проверка правильности выполнения предыдущих этапов. Та"

ким образом, процесс решения инженерных задач на ЭВМ носит обыч"

но итерационный характер.

Следует отметить, что процесс алгоритмизации представляет со"

бой некий компромисс между игрой воображения и умением быстро

находить эффективное решение, что делает этот процесс творческой

работой. Поэтому каждый занимающийся машинными вычислени"

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

дачи. Однако в таком процессе важно «не заблудиться» и стараться

отыскать «золотую середину». Кроме того, необходимо помнить, что

«велосипед» уже изобретен, и следует при решении вычислительных

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

При анализе различных вариантов схем алгоритмов решения од"

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

новными критериями:

– сходимость алгоритма к решению;

– минимально возможное число шагов;

– минимально возможное число используемых обозначений

(имен): в будущей программе это скажется на объеме используемой

памяти;

– «понятность» вводимых обозначений и действий – с этой целью

желательно использовать так называемые мнемонические имена;

– корректность выбранных методов и способов решения.

Целью методических указаний является обучение студента основ"

ным правилам и приемам составления схем алгоритмов решения вы"

числительных задач. Схема алгоритма позволяет наглядно предста"

вить пошаговое решение поставленной задачи на ЭВМ и является

универсальным средством, не зависящим от языка программирова"

ния.

В методических указаниях приведены схемы алгоритмов реше"

ния типовых вычислительных задач.

Для более детального освоения методов и приемов, используемых

на этапе алгоритмизации задач, можно воспользоваться работой [1].

Кроме того, в работах [2,3] приведены примеры схем алгоритмов ре"

шения некоторых типовых вычислительных задач и их реализация

на языке Паскаль.

1. ВВЕДЕНИЕ В АЛГОРИТМИЗАЦИЮ ЗАДАЧ

1.1. Основные понятия и определения

Алгоритмизация задачи представляет собой процесс составления

алгоритма ее решения. Алгоритм – строго определенная процедура,

гарантирующая получение результата за конечное число шагов.

Все многообразие вычислительных алгоритмов включает в себя в

виде фрагментов три типовых вычислительных процесса:

1) линейный процесс – последовательность операций, выполня"

емых одна за другой;

2) ветвящийся процесс – выполнение операций по одному из

возможных направлений (ветвей алгоритма) в зависимости от неко"

торого условия;

3) циклический процесс – многократное выполнение некото"

рого набора операций, составляющих тело цикла, в соответствии с

заданным правилом.

С целью наглядного представления вычислительного процесса

решения задачи используются схемы алгоритмов, которые состав"

ляются в соответствии с требованиями «Единой системы программ"

ной документации» (ЕСПД): ГОСТ 19.701"90. Схемы алгоритмов,

программ, данных и систем.

Основные символы (геометрические фигуры), применяемые в схемах

алгоритмов, приведены на рис. 1.1. В схеме алгоритма каждый символ

может иметь порядковый номер, который записывается слева над сим"

волом. Нумерация производится слева направо и сверху вниз.

Ниже приведены примеры построения схем алгоритмов ветвяще"

гося и циклического вычислительных процессов.

Пример 1.1

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

, если ,

2 в остальных случаях

ax ab

Исходные данные: a, b, x.

Решение задачи показано на рис. 1.2.

Рис.1.1. Графическое представление алгоритмов

Рис. 1.2. Схема алгоритма вычисления значения y (пример 1.1)

Пример 1.2

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

sin( )/ .

Spkk12

Исходные данные: p, n

Решение задачи показано на рис. 1.3.

Рис. 1.3. Схема алгоритма вычисления значения суммы (пример 1.2)

1.2. Алгоритм поиска экстремума среди нескольких величин

Задача поиска экстремального значения среди нескольких вели"

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

а) на основе предположений с последующими проверками;

б) сравнением значений элементов каждой пары.

Пример 1.3

Составить схему алгоритма нахождения максимального значения

среди трех величин: a, b, c.

Решение задачи на основе предположений с последующими про"

верками приведено на рис. 1.4, а при помощи сравнения значений

элементов каждой пары – на рис. 1.5.

Рис. 1.4. Схема алгоритма нахождения максимального значения

на основе предположений с последующими проверками

Анализируя схемы алгоритмов, приведенные на рис. 1.4 и 1.5,

можно отметить, что алгоритм нахождения максимального значе"

ния на основе сравнения значений элементов каждой пары более эф"

фективен, так как требует меньшего числа действий и шагов их реа"

лизующих.

Кроме того, возможны и другие способы решения приведенной за"

дачи, например с так называемыми «объединенными проверками».

Студенту предлагается самостоятельно составить схему алгоритма

решения и провести его оценку.

Аналогично решается задача поиска минимального значения сре"

ди нескольких величин.

2. АЛГОРИТМЫ ОБРАБОТКИ

ЧИСЛОВЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Пусть задана последовательность a

, ..., a

k–1

, ...,a

, ..., где

– общий член последовательности. Любые операции с такой пос"

ледовательностью возможны лишь при выполнении условия сходи"

мости (критерий Коши): если для каждого сколь угодно малого по"

ложительного числа e существует такой номер N, что из m > N и n > N

следует | a

– a

| < e, то последовательность считается сходящейся.

Проверку этого условия можно не делать, если операции проводятся

с конечным числом членов последовательности.

В выражение для a

могут входить различные функции: степен"

ные, показательные, тригонометрические, логарифмические, а так"

же факториалы. Для заданных значений аргументов функций, вхо"

дящих в a

, можно вычислить числовые значения членов последова"

тельности. В этом случае говорят о числовой последовательности.

При вычислении степенных функций и факториалов с ростом k резко

Рис. 1.5. Схема алгоритма нахождения максимального значения на основе

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

возрастает расход машинного времени и уменьшается точность вы"

числений. В этих случаях используются рекуррентные соотно"

шения, позволяющие найти очередной член числовой последователь"

ности a

или его компоненты через a

k–1

= f(a

k–1

), k = 2..N. (2.1)

Рекуррентная зависимость (2.1) используется также при вычис"

лении значения суммы (произведения) членов последовательности.

Действительно, частичные суммы членов последовательности

= a

...,

= a

+ a

+...+ a

k–1

+ a

можно представить рекуррентной формулой

= S

k–1

+ a

(аналогично для произведения – P

= P

k–1

´ a

Особенностью вычислений по рекуррентной формуле (2.1) явля"

ется то, что для получения значения a

достаточно знать только вы"

численное на предыдущем шаге значение a

k–1

. Таким образом, дости"

гается экономия памяти ЭВМ, так как результат каждого шага вы"

числений по формуле (2.1) заносится в одну и ту же ячейку памяти,

при этом предыдущее значение (a

k–1

) стирается. Аналогичные рас"

суждения можно привести для вычисления S

и P

Следует иметь в виду, что перед вычислениями по рекуррентным

формулам необходимо определить a

, S

или P

Пример 2.1

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

L из N членов последовательности, общий член которой

(1) sin()

kk k

где k = 1..N, x = x

+(i–1)h, i = 1..M. Исходными являются значения

параметров: N, M, L, x

, h, p.

Решение. Для получения рекуррентной зависимости (2.1) мож"

но воспользоваться отношением:

12 2

12(1)

(1) sin() ( 1)! sin()

!( 1) sin ( )

kk k

xp k xp

kxp

111

Таким образом, согласно (1.1):

sin( )