close

Вход

Забыли?

вход по аккаунту

?

Kozenko1

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное
образовательное учреждение высшего образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
С. Л. Козенко
АЛГОРИТМИЗАЦИЯ
ВЫЧИСЛИТЕЛЬНЫХ
ЗАДАЧ
Учебное пособие
Санкт-Петербург
2016
ПРЕДИСЛОВИЕ
УДК 004.021
ББК 22.12
К59
Рецензенты:
кандидат технических наук, доцент А. В. Макарчук;
декан ОИФ ГУМРФ им. адм. С. О. Макарова В. А. Мирошниченко;
кандидат технических наук, доцент В. Г. Нефедов
Утверждено
редакционно-издательским советом университета
в качестве учебного пособия
Козенко, С. Л.
К59 Алгоритмизация вычислительных задач: учеб. пособие /
С. Л. Козенко. – СПб.: ГУАП, 2016. – 75 с.
ISBN 978-5-8088-1161-4
Приводятся основные правила и примеры составления схем алгоритмов решения типовых вычислительных задач, применяемых при
реализации любых информационных процессов. Предназначены для
студентов, обучающихся по дисциплинам «Информатика» и «Основы
программирования», преподаваемым на кафедре «Прикладная математика». Могут быть полезны для студентов других направлений и
специальностей. Приведенные материалы соответствуют ФГОС и рабочим программам соответствующих дисциплин.
Подготовлены к публикации кафедрой «Прикладная математика» и рекомендованы к изданию редакционно-издательским советом
Санкт-Петербургского государственного университета аэрокосмического приборостроения.
УДК 004.021
ББК 22.12
ISBN 978-5-8088-1161-4
©
©
Козенко С. Л., 2016
Санкт-Петербургский государственный
университет аэрокосмического
приборостроения, 2016
Решение инженерных и научных задач зависит от корректности
используемых моделей и методов решения, а так же от эффективности их реализации.
В настоящее время применение средств вычислительной техники как инструмента автоматизации информационных процессов
требует углубленных знаний в различных областях человеческой
деятельности. Часто на практике необходимо преобразовать исходную задачу с учетом дискретного характера машинных вычислений
и представить процесс ее решения на ЭВМ в виде последовательности шагов. Такой подход должен выработать у будущего специалиста «алгоритмическое мышление», на основе которого дальнейший
процесс разработки программ не должен вызывать затруднений.
Решение любой задачи на ЭВМ состоит из следующих этапов.
1. Постановка задачи – формулирование задачи, определение
конкретной цели ее решения и результатов, которые должны быть
получены, выработка критериев оценки этих результатов.
2. Формализация задачи – выбор математических, алгоритмических, эвристических и иных методов решения задачи с учетом
их применимости для машинных вычислений.
3. Алгоритмизация – разработка алгоритма решения задачи, то
есть представление процесса ее решения в виде шагов, этапов.
4. Программирование (кодирование алгоритма) – перевод алгоритма решения задачи на язык ЭВМ в соответствии с используемой
системой программирования.
5. Отладка программы – выявление возможных синтаксических или семантических (смысловых) ошибок и их устранение. На
этом этапе разрабатываются также тестовые примеры с целью проверки корректности программы (верификация программы).
6. Получение результатов и их анализ – полученные результаты должны быть проанализированы на предмет их достоверности и
возможности использования в практической или научной деятельности. Если результаты не удовлетворяют поставленным требованиям, то осуществляется проверка правильности выполнения предыдущих этапов. Таким образом, процесс решения любой задачи
на ЭВМ носит обычно итерационный характер.
Следует отметить, что алгоритмизация задачи является неким
компромиссом между игрой воображения и умением быстро находить эффективное решение, что делает этот процесс творческой
работой. Поэтому каждый, занимающийся машинными вычисле3
ниями, может всегда предложить свой уникальный способ ее решения. Однако в таком процессе важно «не заблудиться» и стараться
отыскать «золотую середину». Кроме того, необходимо помнить,
что «велосипед» уже кто-то изобрел до Вас и пользоваться общеизвестными правилами и приемами, используемыми при решении
вычислительных задач.
Для анализа различных вариантов схем алгоритмов решения
одной и той же задачи следует руководствоваться следующими основными критериями:
– корректность выбранных методов и способов решения;
– сходимость алгоритма к конечному результату;
– минимально возможное число шагов реализации способа решения задачи;
– минимально возможное число используемых обозначений
(имен) – в будущей программе это скажется на объеме используемой памяти;
– «понятность» вводимых обозначений и действий – с этой целью желательно использовать так называемые мнемонические
имена;
Целью учебного пособия является обучение студента основным
правилам и приемам составления схем алгоритмов решения вычислительных задач. Схема алгоритма позволяет наглядно представить решение поставленной задачи на ЭВМ в виде элементарных
действий и является универсальным средством.
В учебном пособии приведены схемы алгоритмов решения типовых вычислительных задач. Кроме этого, для проверки корректности предложенных схем алгоритмов решения некоторых задач
в Приложении приведены примеры программных кодов и «скриншоты» результатов решения соответствующих задач.
Для более детального освоения методов и приемов, используемых на этапе алгоритмизации задач, можно воспользоваться работой [1]. Также в работах [2–6] приведены примеры схем алгоритмов решения некоторых типовых вычислительных задач.
1. ВВЕДЕНИЕ В АЛГОРИТМИЗАЦИЮ ЗАДАЧ
1.1. Основные понятия и определения
Алгоритмизация задачи представляет собой процесс составления алгоритма ее решения. Алгоритм – строго определенная процедура, гарантирующая получение результата за конечное число
шагов.
Все многообразие вычислительных алгоритмов можно представить в виде фрагментов следующих основных четырех типовых вычислительных процессов:
1) линейный процесс – последовательность операций, выполняемых по принципу «одна за другой»;
2) ветвящийся процесс – выполнение операций по одному из
возможных направлений (ветвей алгоритма) в зависимости от некоторого условия;
3) циклический процесс – многократное выполнение некоторого
набора операций, составляющих «тело» цикла, в соответствии с некоторым условием;
4) итерационный процесс – повторное выполнение некоторого
набора операций в соответствии с заданным правилом.
С целью наглядного представления вычислительного процесса
решения задачи используются схемы алгоритмов, которые составляются в соответствии с требованиями «Единой системы программной документации» (ЕСПД): ГОСТ 19.701-90. Схемы алгоритмов,
программ, данных и систем.
Рассмотрим некоторые основные символы (геометрические фигуры), используемые для графического представления схем алгоритмов (табл. 1.1).
Таблица 1.1
Символ
Наименование
символа
Терминатор
Данные
4
Выполняемые функции
Начало/конец схемы алгоритма
Ввод данных или вывод результатов (носитель данных не
определен)
5
Окончание табл. 1.1
Символ
Наименование
символа
Выполняемые функции
Процесс
Обработка данных любого вида
Решение
Переключение вычислительного процесса на одну из ветвей
алгоритма после вычисления
условия, определенного внутри
этого символа. Результаты вычисления условия указываются
рядом с линиями, выходящими
из вершин символа
Граница
цикла
Символ, состоящий из двух
частей, отображает начало и
конец цикла. Обе части символа
имеют один и тот же идентификатор. Условия инициализации,
изменения, завершения цикла
помещаются внутри символа
в начале или в конце, в зависимости от операции, проверяющей
условие
Предопределен- Использование процесса, состояный
щего из операций, определенных
процесс
в другом блоке
Линия
Соединитель
_____
6
Комментарий
Отображает поток данных или
управления. Направления потоков справа налево и снизу вверх
обозначаются стрелками
Используется для обрыва линии
потока данных и продолжения ее
в другом месте. Соответствующие
символы-соединители должны
содержать внутри себя одно и то
же уникальное обозначение
Используется для пояснения некоторых операций или их групп
Каждый символ может содержать порядковый номер для ссылки на него. Номер символа в схеме алгоритма указывается в его левой верхней части.
Пример 1.1
Составить схему алгоритма вычисления значения y:
a + x , åñëè a < b
y = 
b − 2x, èíà÷å
Исходные данные: a, b, x.
Решение задачи представлено на рис. 1.1.
В схеме алгоритма, приведенной на рис. 1.1, использованы следующие обозначения:
– a, b, x – исходные данные;
– y – значение искомой величины.
В дальнейшем обозначения «Схема алгоритма» и «Комментарии» применяться не будут с целью упрощения представляемого
материала.
Схема алгоритма
1
Начало схемы алгоритма
Начало
2
Вывод («ДК»)
3
Ввод (a, b, x)
4
a<b
Комментарии
«ДК» – диалоговый комментарий
для пояснения, какие значения
необходимо вводить
Ввод исходных данных
Да
Нет
5
y= b–2*x
6
y = a+x
Проверка условия (значения логического выражения): «Верно ли
условие ?». Результаты проверки:
«Да» или «Нет» и соответствующие им ветви алгоритма
6
Вывод (y)
7
Конец
Вывод результата
Конец схемы алгоритма
Рис. 1.1. Схема алгоритма вычисления значения y
(пример 1.1)
7
Пример 1.2
Составить схему алгоритма вычисления значения некоторой
суммы:
=
S
n
∑ sin( p + k) / k .
k =1
Исходные данные: p, n.
Решение задачи представлено на рис. 1.2.
Начало
Начало схемы алгоритма
Вывод («ДК»)
Вывод диалогового комментария
Ввод (p, n)
Ввод исходных данных
S=0
Начальное значение суммы
(обнуление сумматора)
k=1…n
S=S+sin(p+k)/k
k
Заголовок цикла с параметром k
в) на основе объединенных проверок.
Пример 1.3
Составить схему алгоритма нахождения максимального значения среди трех величин: a, b, c.
Решение задачи на основе предположений с последующими проверками (а) приведено на рис. 1.3, а при сравнении значений элементов каждой пары (б) – на рис. 1.4.
В схеме алгоритма, приведенной на рис. 1.3, использованы следующие обозначения:
– a, b, c – исходные данные;
– max – значение искомой величины.
В схеме алгоритма, приведенной на рис. 1.4, использованы те
же обозначения, что и в схеме алгоритма, приведенной на рис. 1.3.
Анализируя схемы алгоритмов, приведенные на рис. 1.3 и 1.4,
можно отметить, что алгоритм нахождения максимального значения на основе сравнения значений элементов каждой пары более
эффективен, так как требует меньшего числа действий и шагов их
Тело цикла (суммирование)
Начало
Начало схемы алгоритма
Вывод («ДК»)
Вывод диалогового комментария
Ввод (a, b, c)
Ввод исходных данных
Окончание цикла по параметру k
Вывод (S)
Вывод результата
Конец
Конец схемы алгоритма
Рис. 1.2. Схема алгоритма вычисления значения суммы
(пример 1.2)
b>max
Нет
В схеме алгоритма, приведенной на рис. 1.2, использованы следующие обозначения:
– p, n – исходные данные;
– S – значение искомой величины.
c >max
Нет
1.2. Поиск экстремальных значений среди
нескольких величин
Задача поиска экстремальных значений может быть реализована следующими способами:
а) на основе предположений с последующими проверками;
б) сравнением значений элементов каждой пары;
8
Предположение, что значение a является максимальным
max = a
Вывод (max)
Конец
Да
max = b
Да
Сравнение значений остальных
элементов с предполагаемым максимальным значением и выбор максимального из них
max = c
Вывод результата
Конец схемы алгоритма
Рис. 1.3. Схема алгоритма нахождения максимального значения
на основе предположений с последующими проверками
9
Вывод («ДК»)
Вывод диалогового комментария
Ввод (a, b, c)
Ввод исходных данных
Нет
Нет
max=c
Да
a>b
b>c
a>c
Да
Нет
max=b
2. АЛГОРИТМЫ ОБРАБОТКИ ЧИСЛОВЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Начало схемы алгоритма
Начало
Да
Сравнение значений элементов каждой пары
и выбор из них максимального значения
max=a
max=c
Вывод (max)
Вывод результата
Конец
Конец схемы алгоритма
Рис. 1.4. Схема алгоритма нахождения максимального значения
на основе сравнения значений элементов каждой пары
реализующих. С другой стороны, алгоритм на основе предположений с последующими проверками более компактен.
Кроме того, возможны и другие способы решения приведенной
задачи, например, с так называемыми «объединенными проверками». Студенту предлагается самостоятельно составить схему алгоритма решения задачи и провести его оценку.
Аналогично решается задача поиска минимального значения
среди нескольких величин.
Пусть задана последовательность a1, a2,..., ak–1, ak,..., aN,..., где
ak – общий член последовательности. Любые операции с такой последовательностью возможны лишь при выполнении условия сходимости (критерий Коши): если для каждого сколь угодно малого
положительного числа e существует такой номер N, что из m>N и
n>N следует | an – am| < e, то последовательность считается сходящейся. Проверку этого условия можно не делать, если операции
проводятся с конечным числом членов последовательности.
В выражение общего члена последовательности ak могут входить различные функции: степенные, показательные, тригонометрические, логарифмические, а также факториалы. Для заданных
значений аргументов функций, входящих в формулу ak, можно
вычислить числовые значения членов последовательности. В этом
случае говорят о числовой последовательности. При вычислении
степенных функций и факториалов с ростом k возрастает расход
машинного времени и уменьшается точность вычислений. В этих
случаях используются рекуррентные соотношения, позволяющие
найти очередной член числовой последовательности ak на основе
предыдущего значения ak–1:
ak = f(ak–1), k = 2...N. (2.1)
Рекуррентная зависимость (2.1) также используется при вычислении значения суммы (произведения) членов последовательности. Действительно, частичные суммы членов последовательности
S1 = a1,
S2 = a1 + a2,
...,
Sk = a1 + a2 + ... + ak–1 + ak
можно представить рекуррентной формулой
Sk = Sk–1 + ak (аналогично для произведения – Pk = Pk–1 × ak).
Особенностью вычислений по рекуррентной формуле (2.1) является то, что для получения значения ak достаточно знать только вычисленное на предыдущем шаге значение ak–1. Таким образом, достигается экономия памяти ЭВМ, так как результат каждого шага
вычислений в соответствии с формулой (2.1) заносится в одну и ту
же ячейку памяти, при этом предыдущее значение (ak–1) стирает-
10
11
ся. Аналогичные рассуждения можно привести для вычисления Sk
и Pk.
Следует иметь в виду, что перед вычислениями по рекуррентным формулам необходимо определить a1, S1 или P1.
Все приведенные рассуждения также действуют для случаев,
когда рекуррентные соотношения можно определить лишь для некоторой части выражения общего члена последовательности ak.
Пример 2.1
Составить схему алгоритма вычисления значения суммы (S)
первых L из N членов последовательности, общий член которой
ak =
Начало
k +1
k
2k
e− pk xk+1
, где k = 1...N,
(k + 1)!
x = x0 + (i–1)h, i = 1...M. Исходными данными являются значения
параметров: x0, h, p, N, M.
Решение. Предварительно необходимо произвести преобразование: ak = 1 + bk и рекуррентную формулу вывести для bk:
bk
e− pk xk+1 (k − 1 + 1)!
e− p x
.
=
=
−
p
k
−
1
k
−
1
+
1
(
)
(
)
bk−1 (k + 1)! e
k +1
x
12
Ввод (x0, h, p,
N, M, L)
Ввод исходных данных
Заголовок цикла по i
Вычисление текущего значения x
ak =p*p*sin(x)
Вычисление значения a1
Вывод (ak)
Вывод значения первого члена
последовательности
S = ak
Занесение в сумматор значения a1
k =2 … N
Заголовок цикла по k
ak =–ak*sin (x)*p*p/k
Вычисление текущего значения ak
Вывод (ak)
Вывод значения очередного члена
последовательности
ak (−1)
Sin (x) p (k − 1)! − Sin(x) p
.
=
=
k
ak−1 k !(−1) Sink−1 (x) p2(k−1)
k
ных позициях), общий член которой: ak = 1 +
Вывод диалогового комментария
x = x0+(i –1)*h
2
Sin(x) p2
Таким образом, согласно (2.1), ak = − ak−1
.
k
Для определения a1 в формулу для общего члена последовательности (2.2) подставим значение k = 1. Получим: a1 = Sin(x) p2.
Схема алгоритма решения задачи приведена на рис. 2.1.
В некоторых задачах рекуррентное соотношение целесообразно
найти только для некоторой компоненты общего члена последовательности.
Пример 2.2
Составить схему алгоритма вычисления значения произведения (Pr) четных членов последовательности (находящихся на чет-
Вывод («ДК»)
i =1… M
(−1)k+1 Sink (x) p2k
, (2.2)
k!
где k = 1...N, x = x0 + (i–1)h, i = 1...M. Исходными данными являются
значения параметров: x0, h, p, N, M, L.
Решение. Для получения рекуррентной зависимости можно воспользоваться отношением:
Начало схемы алгоритма
Да
k≤ L
S = S+ak
k
Нет
Проверка номера члена последовательности
Добавление в сумматор значения ak
Окончание цикла по k
Вывод (S, x)
Вывод значений
i
Окончание цикла по i
Конец
Конец схемы алгоритма
Рис. 2.1. Схема алгоритма вычисления значения суммы первых L из N
членов последовательности
e− p x
Таким образом, согласно (2.1), bk = bk−1
. В этом случае
k +1
e − p x2
b1 =
.
2
Схема алгоритма решения задачи приведена на рис. 2.2.
13
В схеме алгоритма, приведенной на рис. 2.1, использованы следующие обозначения:
– x0, h, p, N, M, L – исходные данные;
Начало
Начало схемы алгоритма
Вывод ( «ДК»)
Вывод диалогового комментария
Ввод (x0, h,
p, N, M)
Ввод исходных данных
i=1… M
Заголовок цикла по i
x=x0+(i–1)*h
Вычисление текущего значения x
bk=e –p*x*x/2
Вычисление значения b 1
ak=1+bk
Вычисление значения a1
Вывод (ak)
Вывод значения первого члена
последовательности
Pr=1
k=2… N
Занесение в накопитель произведения
значения 1 (так как первый член последовательности находится на нечетной позиции)
Заголовок цикла по k
bk=bk*e –p*x/(k+1)
Вычисление значения b k
Вычисление значения ak
ak=1+bk
Вывод значения очередного члена
последовательности
Вывод (ak)
k %2=0
Да
Pr=Pr*ak
Нет
Проверка условия на четность и
добавление в накопитель произведения
значения ak , если условие выполняется
k
Окончание цикла по k
Вывод ( Pr, x)
Вывод результатов
i
Окончание цикла по i
Конец
– i, k – параметры циклов;
– x – текущее значение переменной, используемой для вычисления членов последовательности (задается в виде арифметической
прогрессии);
– ak – обозначение члена последовательности;
– S – значение суммы членов последовательности в соответствии
с условием задачи.
В схеме алгоритма, приведенной на рис. 2.2, использованы следующие обозначения:
– x0, h, p, N, M – исходные данные;
– i, k – параметры циклов;
– x – текущее значение переменной, используемой для вычисления членов последовательности (задается в виде арифметической
прогрессии);
– ak – обозначение члена последовательности;
– bk – обозначение составляющей члена последовательности;
– k%2 – операция нахождения остатка от деления значения k на
2 (в системе программирования C);
– Pr – значение произведения четных членов последовательности в соответствии с условием задачи.
Конец схемы алгоритма
Рис. 2.2 Схема алгоритма вычисления значения произведения
четных членов последовательности
14
15
3. АЛГОРИТМЫ ОБРАБОТКИ МАССИВОВ ДАННЫХ
3.1. Общие понятия
Под массивом будем понимать некоторым образом организованный набор данных (например, чисел), называемых элементами, или компонентами, массива. Элементы массива имеют общее
имя, а их индексы определяют местоположение каждого элемента
в массиве. Количество индексов, используемых для указания положения (координат) элемента в массиве, зависит от размерности
массива. Различают одномерные (векторы в математике), двумерные (матрицы в математике или таблицы) и многомерные массивы.
В дальнейшем будем рассматривать только одномерные и двумерные массивы.
Например,
A = { a1, a2, ..., an } – одномерный массив (вектор) размерностью n,
b11b12b13 …b1n

B = b21b22b23 …b2n – двумерный массив (матрица) размерноb b b …b
 m1 m2 m3 mn
стью m×n (m – число строк, n – число столбцов матрицы).
В общем случае массивы не упорядочены по значениям элементов, но в то же время упорядочены по индексам, что позволяет производить обработку массивов путем организации циклов по индексам.
Рассмотрим примеры схем алгоритмов решения некоторых типовых задач обработки массивов.
3.2. Поиск экстремальных элементов в массиве
К подобным задачам относятся: поиск максимальных и/или
минимальных элементов, а также некоторых функций от этих элементов (например, максимального по модулю элемента) в массивах
различной размерности с указанием или без указания координат
искомых элементов. Следует отметить, что при реализации алгоритмов решения задач обработки массивов данных в среде программирования C, нумерация элементов массивов начинается с нуля.
Учтем этот факт в приводимых примерах. Кроме того, для упрощения некоторых комментариев используем следующие обозначения: «исходный» массив – массив, содержащий исходные данные;
«результирующий» массив – массив, содержащий результаты обработки данных в соответствии с условием задачи.
16
Пример 3.1
Составить схему алгоритма поиска экстремальных по модулю
элементов в одномерном массиве An.
Схема алгоритма решения задачи приведена на рис. 3.1.
Пример 3.2
Составить схему алгоритма поиска экстремальных элементов и
их координат в двумерном массиве Am×n.
Схема алгоритма решения задачи приведена на рис. 3.2.
В схеме алгоритма, приведенной на рис. 3.1, использованы следующие обозначения:
– A – исходный одномерный массив;
Начало
Начало схемы алгоритма
Вывод («ДК»)
Вывод диалогового комментария
i=0… n–1
Ввод значений элементов
массива A
Ввод ( A i)
i
Amax =A 0
Задание начального значения
Amax
Amin =A 0
Задание начального значения
Amin
i=1… n–1
Нет
|A i | > |Amax|
Да
|A i | < |Amin|
Amax= A i
Да
Проверка значений модулей
элементов массива со значениями
Нет модулей Amax и Amin и внесение
необходимых изменений в
соответствии с условием
Amin= A i
i
Вывод ( Amax , Amin )
Конец
Вывод результатов
Конец схемы алгоритма
Рис. 3.1. Схема алгоритма решения примера 3.1
17
1
Начало
Начало схемы алгоритма
2
Вывод («ДК»)
3
i=0… m–1
4
j=0… n–1
5
Ввод ( A ij )
6
j
7
i
8
Amax=A 00
9
Imax=0
10
Jmax=0
11
Amin=A 00
12
Imin=0
13
Jmin=0
14
15
16
20
22
Ввод значений элементов двумерного
массива A m×n
Задание начальных значений
Amax, Imax, Jmax,
Amin, Imin, Jmin
(на основе предположения, что
экстремальные элементы находятся в
позиции с координатами [0,0])
i=0… m–1
Организация циклов для перебора элементов массива A
j=0...n –1
A ij > Amax
Да
18
Вывод диалогового комментария
Amax=Aij
Imax=i
Jmax=j
Нет
17
19
Aij < Amin
Да
Amin=A ij
21
23
Нет
Проверка значения текущего
элемента массива A на «экстремальность» и изменение соответствующих значений
Imin=i
Jmin=j
24
25
j
i
26
Вывод ( Amax , Imax , Jmax,
Amin , Imin, Jmin)
27
Конец
Окончание циклов для перебора элементов массива A
Вывод результатов
Конец схемы алгоритма
Рис. 3.2. Схема алгоритма решения примера 3.2
18
– i – параметр цикла для перебора элементов массива;
– n – размерность массива A;
– Amax, Amin – соответственно максимальное и минимальное
значения элементов массива.
В схеме алгоритма, приведенной на рис. 3.2, использованы следующие обозначения:
– A – исходный двумерный массив;
– i, j – параметры циклов для перебора элементов массива;
– m, n – размерности массива A;
– Amax, Amin – соответственно максимальное и минимальное
значения элементов массива;
– Imax, Jmax, Imin, Jmin – значения координат соответственно
максимального и минимального элементов в массиве.
Пример 3.3
Составить схему алгоритма поиска экстремальных элементов
в k-й строке (l-м столбце) матрицы Am×n.
Решение. Для решения задачи можно воспользоваться схемой
алгоритма, приведенной на рис. 3.2. В этой схеме необходимо сделать следующие изменения:
– между блоками 7 и 8 вставить два блока: «Вывод («ДК»)» и
«Ввод (k)» (для поиска экстремальных элементов в k-й строке) или
«Вывод («ДК»)» и «Ввод (l)» (для поиска экстремальных элементов
в l-м столбце);
– удалить блоки 9, 10, 12, 13, 20, 21, 22, 23;
– удалить блоки 14, 25 (для поиска экстремальных элементов
в k-й строке), или блоки 15, 24 (для поиска экстремальных элементов в l-м столбце);
– в блоках 8, 11 вместо A00 записать Ak0 (для поиска экстремальных элементов в k-й строке) или A0l (для поиска экстремальных
элементов в l-м столбце);
– в блоке 14 (для поиска экстремальных элементов в l-м столбце)
или блоке 15 (для поиска экстремальных элементов в k-й строке)
вместо 0 записать 1;
– в блоках 16, 17, 18, 19 заменить индекс i на k (для поиска экстремальных элементов в строке) или j на l (для поиска экстремальных элементов в столбце);
– в блоке 26 убрать Imax, Jmax, Imin, Jmin. Добавить k (для поиска экстремальных элементов в строке) или l (для поиска экстремальных элементов в столбце).
19
3.3. Вычисление значения суммы (произведения)
элементов массива
Вычисление значения суммы (произведения) элементов массива применяется во многих задачах обработки массивов, а также
в задачах линейной алгебры. Значение суммы S (произведения P)
элементов массива ищется с использованием рекуррентной зависимости (2.1) в виде последовательного накопления частичных сумм
1
Начало
Начало схемы алгоритма
Вывод («ДК»)
Вывод диалогового комментария
2
3
4
5
i=0… m–1
j=0… n–1
Ввод значений элементов двумерного
массива Am×n
Ввод (A ij)
6
j
7
i
8
9
10
S=0
Обнуление сумматора
i=0… m–1
Организация циклов для перебора
элементов массива A
j =0… n–1
11
A ij > 0
12
Да
S=S+A ij
Нет
Сравнение значения текущего
элемента Aij с нулем и добавление его
в сумматор, если его значение положительно
13
i
Окончание циклов по
перебору элементов
массива
Вывод (S)
Вывод результата
Конец
Конец схемы алгоритма
j
14
15
16
Рис. 3.3. Схема алгоритма вычисления значения суммы
положительных элементов матрицы Am×n
20
(произведений) элементов массива. Все рассуждения аналогичны
приведенным в разд.2. Различие состоит лишь в том, что начальное
значение суммы задается равным 0 (для произведения начальное
значение задается равным 1).
Пример 3.4
Составить схему алгоритма вычисления значения суммы положительных элементов матрицы Am×n.
Схема алгоритма решения задачи приведена на рис. 3.3.
Пример 3.5
Составить схему алгоритма вычисления значения произведения
всех элементов одномерного массива Am.
Решение. Для решения задачи можно воспользоваться схемой
алгоритма, приведенной на рис. 3.3. В этой схеме необходимо сделать следующие изменения:
– удалить блоки 4, 6;
– в блоке 5 Aij заменить на Ai;
– в блоке 8 вместо S = 0 записать Pr = 1;
– удалить блоки 10, 11, 13;
– в блоке 12 вместо S = S + Aij записать Pr = Pr*Ai;
– в блоке 15 S заменить на Pr.
В схеме алгоритма, приведенной на рис. 3.3, использованы следующие обозначения:
– A – исходный двумерный массив;
– i, j – параметры циклов для перебора элементов массива;
– m, n – размерность массива A;
– S – значение суммы положительных элементов массива.
3.4. Сортировка (упорядочение) массива
Задача сортировки неупорядоченного массива данных (обычно
одномерного) заключается в перестановке элементов массива в заданном порядке, например, по возрастанию или убыванию значений элементов массива или значений функций от этих элементов.
Существуют несколько методов сортировки массивов. Рассмотрим
два применяемых на практике метода сортировки: метод простого
выбора и метод «пузырька».
Сортировка методом простого выбора. Суть метода сводится
к тому, что в неупорядоченной последовательности ищется экстремальный по значению элемент, точнее его индекс. Найденный экстремальный элемент переставляется с первым элементом неупорядоченной последовательности, и поиск повторяется со следующего
21
элемента. Число шагов описанного процесса – n(n–1)/2, где n – число элементов последовательности.
Главный недостаток метода – отсутствие признака окончания
процесса сортировки. Поэтому, в случае, когда последовательность
уже упорядочена (изначально или по мере прохождения процесса
сортировки), приходится выполнять все n(n–1)/2 шагов.
Пример 3.6
Составить схему алгоритма сортировки одномерного массива An
в порядке убывания значений элементов, используя метод простого
выбора.
Схема алгоритма решения задачи приведена на рис. 3.4.
Сортировка методом «пузырька». Суть метода состоит в следующем. В ходе просмотра элементов неупорядоченной последовательности сравниваются значения двух соседних членов. Если рассматриваемые члены последовательности (элементы массива) расположены в заданном порядке, то они остаются на своих местах, иначе
их меняют местами. Затем переходят к следующей паре, в которой
один элемент из предыдущей пары. Обычно просмотр элементов
начинается с последней пары. В этом случае искомые элементы
продвигаются с конца последовательности в ее начало, что напоминает процесс обменного движения воздушных капель и жидкости
в наклоненном пузырьке (отсюда и название метода). Сортировка
считается законченной, если в ходе просмотра членов последовательности не была произведена ни одна перестановка, иначе процесс повторяется.
По сравнению с методом простого выбора метод «пузырька»
имеет более быструю сходимость за счет наличия признака окончания процесса сортировки, который показывает, были перестановки в парах или нет.
Пример 3.7
Составить схему алгоритма сортировки одномерного массива An
в порядке убывания значений модулей элементов, используя метод
«пузырька».
Схема алгоритма решения задачи приведена на рис. 3.5.
В схеме алгоритма, приведенной на рис. 3.4, использованы следующие обозначения:
– A – исходный одномерный массив;
– i, j – параметры соответствующих циклов;
– n – размерность массива A;
– M – значение координаты максимального элемента массива;
22
Начало
Начало схемы алгоритма
Вывод («ДК»)
Вывод диалогового комментария
i=0… n–1
Ввод значений элементов одномерного
массива An
Ввод ( A i)
i
Открытие цикла по числу шагов
сортировки и определение начального
значения координаты максимального элемента ( M) в неупорядоченной
последовательности
i=0… n–2
M=i
j=i+1… n–1
Aj > AM
Открытие цикла для перебора элементов
Нет
Проверка значения текущего элемента
массива с предполагаемым максимальным значением и изменение значения
M в соответствии с условием
Да
M=j
j
M≠ i
Да
R =A i
Нет
Проверка значений координат предполагаемого максимального элемента
и текущего элемента и перестановка
элементов при выполнении условия
A i =A M
A M =R
i
Вывод («ДК»)
Вывод диалогового комментария
i=0… n–1
Вывод (A i)
Вывод значений упорядоченного
массива
i
Конец
Конец схемы алгоритма
Рис. 3.4. Схема алгоритма сортировки одномерного массива
методом простого выбора
23
1
Начало
Начало схемы алгоритма
2
Вывод («ДК»)
3
Вывод диалогового комментария
i=0… n–1
4
Ввод значений элементов одномерного
массива A n
Ввод (A i)
5
i
Flag =0
Открытие цикла по числу шагов
сортировки и определение начального
значения признака окончания процесса
сортировки Flag (блок 7)
j=n–1… i (–1)
Открытие цикла для перебора соседних
элементов
6
i=1… n–1
7
8
9
|Aj–1|< |Aj |
10 Да
R=A j–1
11
Нет
Сравнение значений соседних элементов массива и их перестановка в случае
их взаимной неупорядоченности (при
этом значение признака окончания
процесса сортировки Flag изменяется
на противоположный – блок 13)
Да
Проверка значения признака окончания процесса сортировки (блок 15) и
окончание процесса сортировки в случае, когда отсутствует неупорядоченность соседних элементов массива
(альтернатива «Да»)
A j–1=A j
– R – значение переменной, используемой для перестановки элементов массива.
В схеме алгоритма, приведенной на рис. 3.5, использованы следующие обозначения:
– A – исходный одномерный массив;
– i, j – параметры соответствующих циклов;
– n – размерность массива A;
– Flag – признак окончания процесса сортировки;
– R – имя переменной, используемой для перестановки элементов массива.
12
A j =R
13
Flag =1
14
j
15
Flag ==0
Нет
16
i
17
Вывод («ДК»)
18
19
20
21
i=0… n–1
Вывод (A i)
Вывод диалогового комментария
Вывод значений элементов
упорядоченного массива
i
Конец
Конец схемы алгоритма
Рис. 3.5. Схема алгоритма сортировки одномерного массива
методом «пузырька»
24
25
4. АЛГОРИТМИЗАЦИЯ ЗАДАЧ
ЛИНЕЙНОЙ АЛГЕБРЫ
4.1. Общие положения
При решении прикладных задач часто возникает необходимость
производить вычисления, связанные с использованием основных
понятий линейной алгебры – матриц и векторов. Понятия «матрица» и «вектор» хорошо известны, поэтому приводить их здесь не
будем. Остановимся лишь на понятиях «матрица-строка» и «матрица-столбец», которые встречаются в некоторых изданиях и употребляются некоторыми математиками.
Пусть задана некоторая матрица размерностью m×n, где m – количество строк, n – количество столбцов. Тогда, при m = 1 говорят о
матрице-строке, а при n = 1 – о матрице-столбце. Примеры обозначений: Q1×n – матрица-строка; Qm×1 – матрица-столбец. В дальнейшем размерность 1 в обозначении таких матриц будем опускать и
считать их векторами.
Как уже отмечалось в разд. 3, в системах программирования для
описания матриц используются двумерные массивы, а для описания векторов – одномерные массивы. В связи с этим предлагаемый
дальнейшему вниманию материал можно считать продолжением
предыдущего раздела.
Рассмотрим типовые задачи линейной алгебры по обработке матриц и векторов.
4.2. Транспонирование матриц
Матрица Qm×n является транспонированной по отношению к матрице Rn×m, если элементы матриц Q и R связаны соотношениями:
qij = rji , i = 1...m, j = 1...n.
Пример 4.1
Составить схему алгоритма поиска матрицы Qm×n, транспонированной по отношению к матрице Rn×m.
Решение. Схема алгоритма решения задачи представлена на
рис. 4.1. Использованы следующие обозначения:
– R – исходный двумерный массив;
– i, j – параметры циклов для перебора элементов массива;
– n, m – размерности массивов R и Q;
– Q – результирующий массив.
26
Начало
Начало схемы алгоритма
Вывод («ДК»)
Вывод диалогового комментария
i =0… n–1
j=0… m–1
Ввод (R ij)
Ввод значений элементов
матрицы R n×m
Q ji =R ij
Операция транспонирования
j
i
Вывод («ДК»)
Вывод диалогового комментария
i=0… m–1
j =0… n–1
Вывод (Q ij)
Вывод значений элементов
транспонированной матрицы Q m×n
j
i
Конец
Конец схемы алгоритма
Рис. 4.1. Схема алгоритма транспонирования
матрицы (пример 4.1)
4.3. Вычисление значения следа
квадратной матрицы
След квадратной матрицы Am×m есть сумма элементов ее главной диагонали:
m
Sled = ∑ aii .
i =1
Пример 4.2
Составить схему алгоритма нахождения следа квадратной матрицы Am×m.
27
Решение. Для решения задачи можно воспользоваться схемой
алгоритма, приведенной на рис. 3.3. В этой схеме необходимо произвести следующие изменения:
– удалить блоки 10, 11, 13;
– в блоке 4 вместо n записать m;
– в блоках 8, 12 и 15 вместо S записать Sled;
– в блоке 12 вместо Aij записать Aii.
– Z – результирующий двумерный массив;
– m, n – размерности массивов.
1
Начало
Начало алгоритма
Вывод («ДК»)
Вывод диалогового комментария
2
3
4
4.4. Сложение матриц и векторов
Суммой двух матриц Qm×n и Rm×n называется матрица Zm×n , элементы которой вычисляются по формулам:
zij = qij + rij, i = 1...m, j = 1...n.
При m = 1 (или n = 1) имеет место частный случай – сложение
векторов. Например,
Пример 4.3
Составить схему алгоритма нахождения матрицы Zm×n как суммы двух матриц: Qm×n и Rm×n.
Решение. Схема алгоритма решения задачи представлена на
рис. 4.2.
Пример 4.4
Составить схему алгоритма нахождения вектора Zm как суммы
двух векторов: Qm и Rm.
Решение. Для решения этой задачи можно воспользоваться схемой алгоритма, представленной на рис. 4.2. В этой схеме необходимо произвести следующие изменения:
– удалить блоки 4, 6, 10, 13, 17 и 19;
– в блоках 5 и 12 вместо Qij записать Qi;
– в блоках 11 и 12 вместо Rij записать Ri;
– в блоках 12 и 18 вместо Zij записать Zi.
В схеме алгоритма, приведенной на рис. 4.2, использованы следующие обозначения:
– Q, R – исходные двумерные массивы;
– i, j – параметры циклов для перебора элементов массива;
28
j=0… n–1
5
Ввод ( Q ij)
6
Ввод значений элементов матрицы
Q m×n
j
7
i
8
Вывод («ДК»)
zi = qi + ri, i = 1...n.
Следует иметь в виду, что решение указанных задач возможно
лишь в случае одинаковой размерности соответствующих матриц
(векторов).
i=0… m–1
9
10
i=0… m–1
j=0… n–1
11
Ввод (R ij)
12
Z ij=Q ij + R ij
13
Вывод диалогового комментария
Ввод значений элементов матрицы
R m×n и сложение соответствующих
значений элементов двух матриц
j
14
i
Вывод диалогового комментария
15
Вывод («ДК»)
16
17
i=0… m–1
j=0… n–1
18
Вывод (Z ij)
19
Вывод значений элементов результирующей матрицы Z
j
20
i
21
Конец
Конец схемы алгоритма
Рис. 4.2. Схема алгоритма сложения двух матриц
29
4.5. Умножение матриц и векторов
Результатом перемножения двух матриц Qm×l и Rl×n является матрица Zm×n, элементы которой вычисляются следующим образом:
l
zij =∑ qik × rkj , i =1...m, j =1...n .
k =1
Начало
Вывод («ДК»)
l
j=0… l–1
i
Вывод («ДК»)
j=0… n–1
б) при n = 1 – умножение матрицы на матрицу-столбец. Результатом является матрица-столбец, элементы которой вычисляются по формуле:
i
в) при m = 1 и n = 1 – умножение матрицы-строки на матрицустолбец. Результатом является скаляр, значение которого вычисляется по формуле
=
z
i=0… m –1
j=0… n–1
Z ij =0
k=0… l–1
Z ij = Z ij + Q ik * R kj
j
∑ qk × rk .
k =1
zij =
qi × rj , i =
1...m, j =
1...n.
Пример 4.5
Составить схему алгоритма умножения двух матриц: Qm×l и Rl×n
(матрица Zm×n).
Решение. Схема алгоритма решения этой задачи приведена на
рис. 4.3.
30
Процедура перемножения двух матриц
k
l
в) при l = 1 – умножение матрицы-столбца на матрицу-строку.
Результатом является матрица размерностью m×n, значения элементов которой вычисляются по формуле
Ввод значений элементов матрицы
R l×n
j
k =1
k =1
Вывод диалогового комментария
i=0… l–1
zj =
∑ qk × rkj , j =1...n .
zi = ∑ qik × rk , i = 1...m .
Ввод значений элементов матрицы
Q m×l
j
Ввод ( R ij )
l
Вывод диалогового комментария
i=0… m –1
Ввод (Q ij )
Заметим, что перемножить можно только те матрицы, у которых число столбцов первой совпадает с числом строк второй (в данном случае – это размерность l). Исходя из этого условия, допустимыми являются следующие частные случаи:
а) при m = 1 – умножение матрицы-строки на матрицу. Результатом является матрица-строка, элементы которой вычисляются
по формуле:
Начало схемы алгоритма
i
Вывод («ДК»)
Вывод диалогового комментария
i=0… m –1
j=0… n–1
Вывод
( Z ij )
Вывод значений элементов матрицы
Z m×n
j
i
Конец
Конец схемы алгоритма
Рис. 4.3. Схема алгоритма умножения двух матриц
31
Следует отметить, что все частные случаи, возникающие из задачи умножения матриц, легко реализовать, опираясь на схему алгоритма, приведенную на рис. 4.3. Внести изменения в эту схему
с целью представления соответствующих решений предлагается
студенту на самостоятельную проработку.
В схеме алгоритма, приведенной на рис. 4.3, использованы следующие обозначения:
– Q, R – исходные двумерные массивы;
– i, j, k – параметры соответствующих циклов;
– Z – результирующий двумерный массив.
32
5. АЛГОРИТМЫ ОБРАБОТКИ МАССИВОВ ДАННЫХ
С ИСПОЛЬЗОВАНИЕМ ПОДПРОЦЕССОВ
Понятие «подпроцесс» при решении вычислительных задач
встречается очень часто и имеет различные трактовки [3, 5, 6].
В нашем случае под термином «подпроцесс» будем понимать конечный набор действий (шагов), направленных на решение подзадачи,
выделенной из главной (основной) задачи. Алгоритмизация задач,
в которых можно выделить одну или несколько подзадач (встречающихся обычно не один раз по ходу решения основной задачи), является полезным занятием для приобретения навыков модульного
принципа программирования).
Рассмотрим на примере два подхода к решению одной и той же
задачи обработки массивов данных.
Пример 5.1
Ввести значения элементов одномерного массива An. Элементы
массива Bn вычисляются по формуле: bi =
1 + sin(2 * i), i =
1...n . Найти значения максимальных элементов в каждом из массивов. Вывести промежуточные и окончательные результаты расчетов.
Решение.
Вариант 1. Составим схему алгоритма решения задачи, последовательно выполняя все указанные требования (рис. 5.1).
Вариант 2. Перед алгоритмизацией задачи проведем ее анализ.
В задаче (основном процессе) можно выделить дважды встречающуюся подзадачу (подпроцесс) нахождения значения максимального
элемента в одномерном массиве. Кроме этого, упомянутые массивы
имеют одинаковую размерность. В этом случае решение подзадачи
можно оформить в виде отдельной схемы алгоритма подпроцесса,
на который необходимо организовать две ссылки (для вычисления
значения максимального элемента соответственно в массиве A и
в массиве B) из основного процесса решения задачи (рис. 5.2).
На рассматриваемом варианте решения задачи следует остановиться подробнее. Во-первых, о введенных обозначениях.
Maximum – имя подпроцесса нахождения значения максимального
элемента в одномерном массиве. Z и n – внутренние имена использующихся в подпроцессе так называемых формальных параметров,
причем Z – это одномерный массив размерностью n. Подпроцесс
Maximum (рис. 5.3) инициируется из основного процесса посредством упоминания имени подпроцесса с указанием так называемых
фактических параметров (рис. 5.2, блок 11 – A и n, блок 13 – B и
n). Zmax – локальный параметр, который может использоваться
33
Начало
Начало схемы алгоритма
Вывод («ДК»)
Вывод диалогового комментария
i=0… n–1
Ввод ( A i )
Вывод диалогового комментария
Вывод («ДК»)
i=0… n–1
Bi =1+sin(2* i)
Вычисление и вывод значений элементов
массива B
Вывод (B i )
Определение начального значения Amax
Amax =A 0
i=1… n–1
Нет
Проверка значения очередного элемента
массива A: является ли он максимальным
или нет
Запись в Amax значения текущего элемента в соответствии с выполнением
условия
Да
Amax =A i
i
Вывод значения Amax
Bmax=B 0
Определение начального значения Bmax
i=1… n–1
Нет
Проверка значения очередного элемента
массива B : является ли он максимальным
или нет
Запись в Bmax значения текущего элемента в соответствии с выполнением
условия
i
Конец
Вывод значения Bmax
Конец схемы алгоритма
Рис. 5.1. Схема алгоритма решения примера 5.1 (вариант 1)
34
i=0… n–1
B i=1+sin (2* i)
i
Amax = Maximum (A, n)
Вывод (Amax )
Bmax =Maximum ( B , n)
Вывод (Bmax )
Вывод (Amax )
Вывод (Bmax)
Вывод диалогового комментария
Вычисление и вывод значений элементов
массива B
Вывод ( B i )
i
Bmax=B i
Ввод значений элементов массива A
i
В ывод («ДК»)
Да
Вывод диалогового комментария
i=0… n–1
i
B i > Bmax
Вывод («ДК»)
Начало схемы алгоритма
Ввод значений элементов массива A
Ввод ( A i )
A i > Amax
Начало
Конец
Инициация подпроцесса Maximum для вычисления значения максимального элемента
в массиве A
Вывод значения максимального элемента в
массиве A
Инициация подпроцесса Maximum для вычисления значения максимального элемента
в массиве B
Вывод значения максимального элемента в
массиве B
Конец схемы алгоритма
δ
Рис. 5.2. Схема алгоритма основного процесса решения
примера 5.1 (вариант 2)
только внутри подпроцесса. Во-вторых, подпроцесс Maximum можно с определенной степенью условности отождествить с понятием
«функция». Функция – это определенная структура в языках программирования, имеющая характерные свойства и использующаяся для реализации модульного принципа программирования.
В схеме алгоритма, приведенной на рис. 5.1, использованы следующие обозначения:
– A – исходный одномерный массив;
– B – одномерный массив, значения элементов которого вычисляются по заданной формуле;
35
– i – параметр цикла для перебора элементов массивов;
– n – размерность массивов A и B;
– Amax, Bmax – искомые значения максимальных элементов соответственно в массивах A и B.
В схеме алгоритма, приведенной на рис. 5.2, использованы следующие обозначения:
– A – исходный одномерный массив;
– B – одномерный массив, значения элементов которого вычисляются по заданной формуле;
– i – параметр цикла для перебора элементов массивов;
– n – размерность массивов A и B;
– Amax, Bmax – искомые значения максимальных элементов соответственно в массивах A и B;
– Maximum – имя подпроцесса поиска максимального значения
в одномерном массиве.
В схеме алгоритма, приведенной на рис. 5.3, использованы следующие обозначения:
– Z – одномерный массив, среди элементов которого ищется
максимальный;
– Zmax – искомое значение максимального элемента в массиве;
– i – параметр цикла для перебора элементов массива;
– n – размерность одномерного массива (глобальный параметр).
1
Начало
Начало схемы алгоритма
Zmax=Z0
Определение начального значения Zmax
2
3
i=1… n–1
4
Z i > Zmax
Да
5
Нет
Проверка значения текущего элемента одно мерного массива, является ли он максимальным, и определение значения Zmax в
соответствии с условием
Zmax=Z i
6
i
7
Возврат Zmax
8
Конец
Возврат искомого значения в основной
процесс
Конец схемы алгоритма
Рис 5.3. Схема алгоритма подпроцесса Maximum (Z, n)
36
В разных системах программирования свойства функций могут
отличаться. Не вдаваясь в подробности (все-таки речь идет лишь
об алгоритмизации, а не о программировании), будем считать, что
при решении примера 5.1 (вариант 2) использована «функция»
с возвратом значения посредством ее имени. В этом случае действие, отображенное в блоке 7 рис. 5.3 (в схеме алгоритма подпроцесса Maximum), является обязательным для корректной работы
«функции».
Рассмотрим пример, иллюстрирующий другие возможности использования подпроцессов.
Пример 5.2
Ввести значения элементов двумерного массива Am×n. Элементы
массива Bm×n вычисляются по формуле:
bij =
sin(i) + cos( j), i =
1...m, j =
1...n .
Найти значения произведений элементов указанных массивов
на скаляр 1.75 (массивы A1 и B1 соответственно). Вывести промежуточные и окончательные результаты расчетов.
Решение. Перед составлением схемы алгоритма решения задачи произведем небольшой анализ. Во-первых, будем использовать
подпроцесс, осуществляющий умножение матрицы на скаляр. Вовторых, подпроцесс условно отождествим с понятием «нетипизированная функция» (это понятие используется в среде программирования C), или «процедура» (для среды программирования Pascal).
Под этим понятием будем понимать подпроцесс, возвращающий
значения, указанные в списке формальных параметров подпроцесса. Имя подпроцесса в этом случае играет роль лишь ссылки на этот
подпроцесс. Схемы алгоритмов основного процесса и подпроцесса
приведены на рис. 5.4 и рис. 5.5 соответственно.
В схеме алгоритма, приведенной на рис. 5.4, использованы следующие обозначения:
– i, j – параметры циклов для перебора элементов массивов;
– m, n – размерности массивов;
– A – исходный двумерный массив;
– B – двумерный массив, элементы которого вычисляются в соответствии с условием задачи;
– A1, B1 – искомые двумерные массивы;
– Umn – имя подпроцесса умножения матрицы на скаляр (подпроцесс инициируется в блоках 15 и 22 с разными фактическими
параметрами).
37
1
6
Начало
2
Вывод («ДК»)
3
i=0… m–1
4
j=0… n–1
5
Ввод (A ij )
Начало схемы алгоритма
Вывод диалогового комментария
Ввод значений элементов массива A
Вывод («ДК»)
9
23
Вывод («ДК»)
24
i=0… m–1
25
j=0… n–1
26
Вывод ( B1ij )
28
29
Вывод диалогового комментария
Z1ij =Z ij *S
Вычисление значений элементов массива Z1
i
Конец
i=0… m–1
10
j=0… n–1
11
B ij =sin(i)+cos (j)
12
Вывод (B ij )
13
j
14
i
15
Umn ( A, 0.75, A1)
16
Вывод («ДК»)
17
i=0… m–1
18
j=0… n–1
19
Вывод (A1ij)
20
j
21
i
22
Umn ( B, 0.75, B1)
27
i=0… m–1
j
i
8
Начало схемы алгоритма
j=0… n–1
j
7
Начало
Вычисление и вывод значений элементов
массива B
Инициация подпроцесса Umn для вычисления значений элементов массива A1
Вывод диалогового комментария
Вывод значений элементов массива A1
Конец схемы алгоритма
Рис. 5.5. Схема алгоритма подпроцесса Umn (Z, S, Z1)
В схеме алгоритма, приведенной на рис. 5.5, использованы следующие обозначения:
– Z, S, Z1 – формальные параметры, где Z – исходная матрица;
S – скаляр; Z1 – результирующая матрица; m и n – размерности
матриц (глобальные параметры);
– i, j – параметры циклов для перебора элементов массивов.
Применение подпроцессов является наиболее предпочтительным, так как позволяет, во-первых, исключить повторяющиеся однотипные действия и, во-вторых, структурировать саму задачу, что
обеспечит в дальнейшем при программировании задачи построение
программы по частям как здания из готовых блоков.
И нициация подпроцесса Umn для вычисления значений элементов массива B1
Вывод диалогового комментария
Вывод значений элементов массива B1
j
i
Конец
Конец схемы алгоритма
Рис. 5.4. Схема алгоритма основного процесса
38
39
6. ОБРАБОТКА СЛОЖНЫХ СТРУКТУР ДАННЫХ
Таблица 6.1
40
i
y
16 10 1998 4 5 5 5 4
Кол-во
баллов
при поступлении
s
Оценки
за сессию
m
Дата
рождения
Aleksandrov_I. S.
Получает
стипендию
Ф.И.О.
Адрес
При решении вычислительных задач часто требуется обрабатывать одновременно данные различных типов, например, числовые,
символьные данные, массивы этих данных и т.п. Описанные в разделах 3,4 и 5 основные положения и примеры обработки массивов
данных, не позволяют осуществить эти процедуры в связи с тем,
что, по определению, массив – это однородная структура, содержащая данные одного типа. В этой ситуации в различных системах
программирования существуют определенные возможности обработки сложных структур данных. Например, в среде программирования Pascal используется понятие «запись» (record), в среде
C для тех же целей введено понятие «структура» (struct – сокр. от
structure). В пособии будем рассматривать использование структур
данных для решения тех или иных задач. При этом будем учитывать тот факт, что решение задач, приводимых в рассматриваемых
примерах, будет осуществляться в среде программирования C.
Каждая из компонент структуры представляет собой «поле», которое имеет определенный тип и соответствующее имя. Для наглядности приведем пример ведомости студенческой группы (табл. 6.1),
содержащей данные различных типов, которую необходимо обработать в соответствии с некоторым условием.
Следует отметить, что каждая из приведенных в табл. 6.1 граф
представляет собой поле общей структуры данных с условным названием Stud. Кроме этого, поле «Дата рождения» (DateR) является вложенной структурой, состоящей из трех полей: Day, Month,
Year – соответственно день, месяц и год рождения студента (условно обозначим тип указанной структуры как Date).
Помимо упомянутых введем следующие обозначения:
– FIO – Фамилия, Имя и Отчество студента – символьный массив (строка символов – табл. 6.1, графа «Ф.И.О.»);
– Pol – пол студента – данное типа «символ» (табл. 6.1, графа
«Пол»);
– Obr – вид учебного заведения, в котором обучался студент перед поступлением в ВУЗ (s – школа, k – колледж; l – лицей) – данное типа «символ» (табл. 6.1, графа «Что окончил»);
– Address – место проживания студента (i – иногородний студент, p – петербуржец) – данное типа «символ» (табл. 6.1, графа
«Адрес»);
Что
окончил
6.1. Общие положения
Пол
Пример ведомости студенческой группы
191
Sergeev_V. A.
m
l
p
n
3
5 1989 3 3 4 4 4
123
Smirnova_E. V.
w
k
p
y
21 11 1997 5 5 5 5 5
199
Petrova_M. S.
w
l
i
y
11 5 1998 5 4 5 4 4
187
Ivanova_V. A.
w
s
i
y
21 6 1998 5 5 5 5 5
197
Sidorov_S. O.
m
l
p
y
7
8 1998 5 5 5 5 5
194
Sumarokov_B. C.
m
k
p
y
17 12 1997 5 5 5 5 5
192
Timofeeva_A. V.
w
s
p
y
21 4 1998 5 5 5 5 5
188
...
...
...
...
...
...
...
...
– Stip – стипендия (y – получает стипендию, n – не получает стипендию) – данное типа «символ» (табл. 6.1, графа «Получает стипендию»);
– DateR – дата рождения студента – вложенная структура (табл.
6.1, графа «Дата рождения»);
– Ocen – оценки знаний студента, полученные в предыдущую
сессию – целочисленный массив (табл. 6.1, графа «Оценки за сессию»);
– KB – количество баллов, набранных при поступлении в ВУЗ –
целочисленное данное (табл. 6.1, графа «Кол-во баллов при поступлении»).
6.2. Примеры работы со сложными структурами данных
Рассмотрим примеры с учетом значений, приведенных в табл. 6.1.
Пример. 6.1
Из списка студенческой группы необходимо отобрать студентокотличниц, которым исполняется 18 лет в текущем году. Использовать модульный принцип программирования [3, 5, 6].
Решение. Решение примера 6.1 приведено на рис. 6.1 и рис. 6.2.
41
Начало
2
Вывод («ДК»)
3
Начало схемы алгоритма
Вывод диалогового комментария
4
5
Sum i =0
6
Ввод (Today.Year)
Ввод значения текущего года
*N=0
Обнуление сумматора (количество
вычисляемых по условию задачи
студентов)
Ввод значений соответствующих полей (см. табл. 6.1)
Обнуление сумматора
Ввод (Ocen j )
Ввод значений элементов массива
оценок
Sum i =Sum i + Ocen j
Вычисление значения суммы оценок,
полученных i-м студентом
8
9
j
10
Ввод (KB)
11
i
12
Otbor (Group , Sum, Group 1, & N)
Вывод («ДК»)
14
15
16
Инициация подпроцесса Otbor для отбора студентов в соответствии с условием примера 6.1
Вывод диалогового комментария
Вывод (Ocen j )
Вывод значений соответствующих полей (см. табл. 6.1)
Вывод значений элементов массива
оценок
j
19
Вывод (KB)
20
Вывод значения KB
i
21
Конец
Pol == ‘w’
Да
Конец схемы алгоритма
Рис. 6.1. Схема алгоритма основного процесса
Нет
Нет
Year+18<=Year
Z1*N =Z i
*N=*N+1
Проверка значения суммы оценок,
полученных i-м студентом
Проверка значения поля «Пол
студента» (полная запись условия –
Zi.Pol == ‘w’)
Проверка значения года
рождения студента (полная запись
условия – Zi.DateR.Year <= Today.Year)
Занесение в результирующий массив
данных о студентах, удовлетворяющих условию, и определение их численности
i
Конец
j=0… 4
17
18
Ввод значения KB
Нет
Да
Да
i=0… N–1
Вывод (FIO, Pol, Obr, Address,
Stip, Day, Month, Year)
i=0… NS–1
Si == 25
j=0… 4
7
42
Вывод диалогового комментария
Вывод («ДК»)
i=0… NS–1
Ввод (FIO, Pol, Obr, Address,
Stip, Day, Month, Year)
13
Начало схемы алгоритма
Начало
1
Конец схемы алгоритма
Рис 6.2. Схема алгоритма подпроцесса Otbor (Z, S, Z1, *N)
В схеме алгоритма, приведенной на рис. 6.1, помимо упомянутых выше использованы следующие обозначения:
– i, j – параметры циклов для перебора элементов массивов;
– NS – количество студентов в группе;
– Otbor – имя подпроцесса, осуществляющего отбор студентов
в соответствии с условием задачи;
– Group – исходный массив типа Stud, каждый элемент которого
является сложной структурой, содержащей данные о студенте в соответствии с табл. 6.1;
– Sum – целочисленный массив, каждый элемент которого представляет собой значение суммы оценок, полученных студентом за
последнюю сессию;
43
– Group1 – результирующий массив типа Stud, содержащий данные об отобранных студентах в соответствии с условием примера 6.1;
– & – адрес ячейки, передаваемый в подпроцесс Otbor;
– N – количество отобранных студентов.
В схеме алгоритма, приведенной на рис. 6.2, использованы следующие обозначения:
– Z, S, Z1, *N – формальные параметры, соответствующие фактическим, используемым при обращении к подпроцессу Otbor (рис. 6.1,
блок 12);
– i – параметр цикла для перебора и определения элементов массивов;
– Today – имя структуры типа Date, значение одного поля которой (Year) используется в подпроцессе;
– * – указатель на ячейку памяти, адрес которой используется
в подпроцессе Otbor для вычисления требуемого значения.
Примечание. Для работы с элементом структуры (полем) необходимо учитывать следующее. Доступ к значению соответствующего поля может осуществляться лишь с помощью операции доступа
к полю (в соответствии с определенной иерархией). Например, при
дальнейшей реализации алгоритма решения примера 6.1 в среде
программирования C, следует использовать полные обозначения:
Group[i].FIO[j], Group[i].DateR.Month, Group1[i].KB или Today.
Year (где символ «.» обозначает операцию доступа к полю). Этот
факт следует учитывать всегда при решении задач обработки сложных структур данных.
Пример. 6.2
Упорядочить список студентов группы по убыванию среднего
балла оценок, полученных студентами в последнюю сессию. Использовать модульный принцип программирования [3, 5, 6].
Решение. При упорядочении списка студентов в соответствии
с условием примера 6.2 используем подпроцесс Sort, в котором
пргоизводится сортировка методом «пузырька». Описание указанного метода приведено в подразд. 3.4 и представлено на рис. 3.5.
Решение примера 6.2 приведено на рис. 6.3 и рис. 6.4.
В схемах алгоритмов, приведенных на рис. 6.3 и рис. 6.4, использованы следующие обозначения:
– i, j – параметры циклов для перебора элементов массивов;
– NS – количество студентов в группе;
– Sort – имя подпроцесса, осуществляющего сортировку списка
студентов в соответствии с условием задачи;
44
1
Начало
Начало схемы алгоритма
Вывод («ДК»)
Вывод диалогового комментария
2
3
i=0… NS–1
4
Ввод ( FIO, Pol, Obr, Address,
Stip, Day, Month, Year )
5
Sum i =0
6
Ввод значений соответствующих полей (см. табл. 6.1)
Определение начального значения
суммы оценок, полученных i-м студентом
j=0… 4
7
Ввод ( Ocen j )
Ввод значений элементов массива
оценок
Sum i =Sum i + Ocen j
Вычисление значения суммы оценок,
полученных i-м студентом
8
9
j
10
SrB i =Sumi /5.0
11
Ввод (KB)
12
i
13
Sort (Group, SrB, Group 1)
14
Вывод («ДК»)
15
Вычисление значения среднего балла
Ввод значения KB
Инициация подпроцесса Sort для упорядочения списка студентов в соответствии с условием примера 6.2
Вывод диалогового комментария
i=0… NS–1
16
Вывод ( FIO, Pol, Obr, Address,
Stip, Day, Month, Year )
17
j=0… 4
18
Вывод (Ocen j )
19
Вывод значений элементов массива
оценок
j
20
Вывод ( KB, SrBi)
21
Вывод значений соответствующих полей (см. табл. 6.1)
Вывод значений KB и элементов
массива SrB
i
Конец схемы алгоритма
22
Конец
Рис. 6.3. Схема алгоритма основного процесса
45
1
Начало
Начало схемы алгоритма
2
i=0… NS–1
Копирование значений элементов исходного массива в новый массив
(массив Z1)
3
Z1 i =Z i
4
i
5
Открытие циклов по числу шагов
сортировки ( i) и перебора элементов
(j), а также определение начального
значения признака окончания процесса
сортировки Flag (блок 6)
i=1… NS–1
6
Flag =0
7
j=NS–1… i (–1)
8
Sj–1 < S j
Нет
Да
9
R =Sj–1
10
Sj–1=Sj
11
Sj =R
Сравнение значений соседних элементов массива средних баллов (блок 8) и
их перестановка в случае неупорядоченности в паре (блоки 9 –11). Кроме
этого осуществляется «перестановка»
студентов группы (блоки 12 –14). При
этом значение признака окончания
процесса сортировки Flag изменяется
на противо положный – блок 15)
– Group – исходный массив типа Stud, каждый элемент которого
является сложной структурой, содержащей данные о студенте в соответствии с табл.6.1;
– Sum – целочисленный массив, каждый элемент которого представляет собой значение суммы оценок, полученных студентом за
последнюю сессию;
– SrB – вещественный массив, каждый элемент которого представляет собой значение среднего балла оценок, полученных студентом за последнюю сессию;
– Group1 – результирующий массив типа Stud, упорядоченный
в соответствии с условием примера 6.1;
– Z, S, Z1 – формальные параметры, соответствующие фактическим, используемым при обращении к подпроцессу Sort (рис. 6.3,
блок 13);
– Flag – признак окончания процесса сортировки;
– R, R1 – вспомогательные ячейки, используемые для перестановки элементов соответствующих массивов.
12
R 1= Z1 j–1
13
Z1 j–1=Z1 j
14
Z1 j =R 1
15
Flag =1
16
j
i
Проверка значения признака окончания процесса сортировки (блок 17) и
окончание процесса сортировки в случае, когда отсутствует неупорядоченность соседних элементов массива
Конец
Конец схемы алгоритма
17
Flag ==0
Нет
18
Да
19
Рис. 6.4. Схема алгоритма подпроцесса Sort (Z, S, Z1)
46
47
7. РАБОТА С ФАЙЛАМИ ДАННЫХ
7.1. Общие сведения
В рассмотренных ранее примерах составления схем алгоритмов
решения вычислительных задач использовалось понятие консольного ввода/вывода данных. То есть значения исходных данных
вводились с клавиатуры, а результаты их обработки отображались
на экране монитора ПК. На практике часто необходимо решать задачи, связанные с такими операциями как запись исходных значений в некоторый файл, считывание из него данных, обработка данных в соответствии с некоторым условием с последующей записью
результатов в новый файл.
Файлом (от англ. file – очередь, ряд, картотека) называется последовательный набор данных, хранящийся на некотором физическом носителе и имеющий собственные имя и/или расширение.
Расширение файла предназначено для однозначной идентификации типа файлового объекта; оно записывается справа от имени
файла и отделяется от него точкой. В данном случае тип файлового объекта – это функциональная характеристика файла, с помощью которой операционная система определяет набор программ,
способных обрабатывать или использовать данный файл. Если мы
рассмотрим в качестве примера некий файл Data.txt, то в этой записи именем файла является Data, а его расширением – txt, которое указывает на то, что данный файловый объект относится к типу
«текстовый файл» и может быть обработан с использованием какого-либо текстового редактора, например стандартной программы
«Блокнот» операционной системы Windows. В приводимых ниже
примерах будем рассматривать работу только с текстовыми файлами.
Ввод исходных данных должен осуществляться с клавиатуры.
Информация по каждому студенту группы должна быть записана и
храниться в создаваемом текстовом файле Data.txt в виде отдельной
строки. Количество строк в файле должно соответствовать численности студенческой группы. Необходимо проверить корректность
записи в файл с целью дальнейшей работы с ним. Для этого необходимо осуществить операцию ввода (считывания) данных из созданного файла. Кроме того, выполнить следующее задание: подсчитать
количество иногородних студентов. Результаты вывести на экран.
Решение. Исходными являются анкетные данные о 8 студентах
группы (табл.6.1). Необходимо ввести эти данные с клавиатуры
и записать их в файл Data.txt, который должен быть расположен
в каталоге D:\$Student\Gr_1609\Abramov\. Выполнить указанное
задание, используя модульный принцип программирования.
При решении задачи используем понятие «полное обозначение
файла» – это путь + имя файла (например, D:\$Student\Gr_1609\
Abramov\Data.txt).
На рис. 7.1 и рис. 7.2 приведены схемы алгоритмов соответственно основного процесса и подпроцесса Calc, реализующего подсчет количества иногородних студентов.
1
Начало
Начало схемы алгоритма
Вывод («ДК»)
Вывод диалогового комментария
2
3
i=0… NS-1
4
,
Ввод ( FIO, Pol, Obr, Address
Stip, Day , Month, Year )
5
j=0… 4
6
Ввод (Ocenj)
7.2. Примеры работы с файлами
Пример 7.1
Составить схему алгоритма создания файла типа txt и заполнения его анкетными данными студентов в соответствии с ведомостью учебной группы (табл. 6.1). Местоположение файла определяется следующим образом. Создается самостоятельно основной
каталог – D:\$Student. Далее, в каталоге $Student создается «цепочка» подкаталогов, например, D:\$Student\Gr_1609\Abramov\,
где Gr_1609 – номер студенческой группы, Abramov – каталог студента.
48
7
8
9
10
Ввод значений соответствующих
полей (см. табл. 6.1)
j
Ввод ( KB)
i
Вывод («ДК»)
11
Ввод ( Dir )
Вывод диалогового комментария для
указания пути с именем каталога, в котором будет создан файл
Ввод местоположения (пути), где будет
создан файл
α
Рис. 7.1. Схема алгоритма основного процесса (начало)
49
α
12
Вывод («ДК»)
Ввод (FileName)
Ввод имени файла
strcat (Dir , FileName)
Конкатенация (связывание) строк Dir
и Filename для получения полного
обозначения файла (блок 14)
14
15
? – ( FIn=fopen ( Dir ,"w"))==NULL (проверка корректности введенного полного обозначения файла при операции
его «открытия» – конструкция, используемая в среде программирования C)
Да
?
Нет
16
Вывод («ДК»)
17
18
i=0… NS-1
30
Вывод ( FIO, Pol,
Obr, Address,
Stip, Day , Month,
Year)
31
33
Запись значений соответствующих
полей в файл
j=0… 4
26
34
Вывод ( KB)
37
i
Запись значения соответствующего
поля в файл
i
38
N=Calc (Group 1)
39
fclose ( FIn)
«Закрытие» файла для записи в него
данных
fopen ( FIn)
«Открытие» файла для чтения из него
записанных данных
γ
Рис. 7.1. Схема алгоритма основного процесса (продолжение)
50
j
35
36
j
β
Вывод ( Ocenj )
Ввод ( FIn; KB)
23
Вывод ( FIn; KB)
25
j=0… 4
Ввод данных о студентах из файла и
вывод значений на экран монитора
для проверки корректности операции
записи в файл
Ввод ( FIn; Ocenj )
Вывод (FIn; Ocenj )
24
i=0… NS-1
Ввод (FIn; FIO,
Pol, Obr, Address,
Stip, Day, Month,
Year )
21
22
Вывод диалогового комментария
29
32
Вывод (FIn; FIO,
Pol, Obr, Address,
Stip, Day, Month,
Year)
20
28
Вывод диалогового комментария об
ошибке
Вывод диалогового комментария об
успешном завершении проверки
Вывод («ДК»)
γ
27
Вывод («ДК»)
13
19
β
Вывод диалогового комментария для
указания имени создаваемого файла
Вывод ( N)
Вывод результата
fclose ( FIn)
«Закрытие» файла
Конец
Конец схемы алгоритма
40
41
Инициация подпроцесса Calc
Рис. 7.1. Схема алгоритма основного процесса (окончание)
51
В схеме алгоритма, приведенной на рис. 7.1, использованы следующие обозначения:
– i, j – параметры циклов для перебора элементов массивов;
– NS – количество студентов в группе;
– Dir – местоположение создаваемого файла (например,
D:\$Student\ Gr_1609\ Abramov\);
– FileName – имя создаваемого файла (например, Data.txt);
– FIn – имя файловой переменной, значением которой является
полное обозначение файла;
– strcat – функция, используемая в среде программирования
C для конкатенации (связывания) строк;
– fopen – функция, используемая в среде программирования
C для реализации операции открытия файла;
– w – параметр, используемый в среде программирования C для
задания режима «запись в файл»;
– NULL – системная константа, используемая в среде программирования C и операционной системе Windows;
– fclose – функция, используемая в среде программирования
C для реализации операции закрытия файла;
– Group – исходный массив типа Stud, каждый элемент которого
является сложной структурой, содержащей данные о студенте в соответствии с табл. 6.1 (имя массива явно не представлено – используется по умолчанию на рис. 7.1 в блоках 4, 6, 8, 19, 21, 23);
– Group1 – массив типа Stud, используемый для временного
хранения данных, считываемых из созданного файла Data.txt для
проверки корректности операции записи в файл. На рис. 7.1 имя
указанного массива (помимо блока 38) используется по умолчанию
в блоках 29, 30, 32, 33, 35, 36;
– N – количество иногородних студентов;
– Calc – имя подпроцесса для подсчета количества студентов
в соответствии с условием примера 7.1.
В схеме алгоритма, приведенной на рис. 7.2, использованы следующие обозначения:
– i – параметр цикла для перебора элементов массива Z;
– NS – количество студентов в группе;
– N – количество иногородних студентов;
– Z – имя массива, элементы которого представляют данные о
студентах (внутреннее формальное имя, используемое в подпроцессе). Ассоциируется с фактическим именем Group1, используемым
в основном процессе.
52
Начало
Начало схемы алгоритма
N=0
Обнуление сумматора
i=0… NS-1
Address == ‘i’
Да
N =N+1
Нет
Проверка – является студент иногородним или нет. Полная запись –
Z[i].Address==’i’
Подсчет количества иногородних студентов
i
Возврат N
Возврат результата в основной
процесс
Конец
Конец схемы алгоритма
Рис. 7.2. Схема алгоритма подпроцесса Calc (Z)
Пример.7.2
Основой примера является условие задачи, приведенной в примере 6.1. Исключением является тот факт, что исходные данные о
студентах группы необходимо ввести с исходного файла Data.txt,
созданного в некотором каталоге (см. пример 7.1), а результаты обработки вывести в новый файл Rezult.txt, расположенном в том же
каталоге.
Решение. Для упрощения некоторых комментариев используем
следующие обозначения: «исходный» файл – файл, содержащий
данные о студентах учебной группы; «результирующий» файл –
файл, содержащий результаты обработки ведомости студенческой
группы в соответствии с условием задачи. Решение примера 7.2
приведено на рис. 7.3 и рис. 7.4.
В схеме алгоритма, приведенной на рис. 7.3, помимо упомянутых выше (см. комментарии к рис. 6.1), использованы следующие
обозначения:
– Dir1 – местоположение исходного файла;
– FileName1 – имя исходного файла;
– Dir2 – местоположение результирующего файла;
– FileName2 – имя результирующего файла;
53
Начало
Начало схемы алгоритма
α
Вывод («ДК»)
Вывод диалогового комментария для
указания пути с именем каталога,
в котором расположен исходный файл
Ввод (FIn; KB)
Ввод местоположения (пути)
исходного файла
Ввод ( Dir1)
Вывод диалогового комментария для
указания имени исходного файла
Вывод («ДК»)
Ввод ( FileName 1)
Ввод имени исходного файла
strcat (Dir1, FileName 1)
Конкатенация (связывание) строк Dir1 и
Filename1 для получения полного
обозначения исходного файла
Да
Вывод («ДК»)
? – (FIn=fopen (Dir1,"r"))==NULL (проверка корректности введенного полного
обозначения исходного файла при операции его «открытия» – конструкция, используемая в среде программирования C)
Вывод диалоговог о комментария об
ошибке
Вывод диалогового комментария об
успешном завершении проверки
Вывод («ДК»)
Вывод диалогового комментария для
ввода исходных данных
?
Нет
Вывод («ДК»)
β
Считывание из исходного файла
значения KB
i
Закрытие исходного файла
fclose ( FIn)
Инициация подпроцесса Otbor для
отбора студентов в соответствии
с условием примера 7.2
Otbor (Group, Sum,
Group 1, & N)
Вывод диалогового комментария для указания пути с именем каталога, в котором
будет создан результирующий файл
Вывод («ДК»)
Ввод местоположения (пути)
результирующего файла
Ввод (Dir2)
Вывод диалогового комментария для указания имени результирующего файла
Вывод («ДК»)
Ввод имени результирующего файла
Ввод ( FileName 2)
Конкатенация (связывание) строк
Dir2 и Filename2 для получения полного обозначения результирующего
файла
? – (FOut=fopen (Dir2,"w"))==NULL
(проверка корректности введенного
полного обозначения результирующего файла при операции его «открытия» – конструкция, используемая в среде программирования C)
Вывод диалогового комментария об
ошибке
Вывод диалогового комментария об
успешном завершении проверки
strcat (Dir2, FileName 2)
Да
?
Нет
i=0… NS–1
Ввод ( FIn; FIO,
Pol, Obr, Address,
Stip, Day, Month,
Year )
Считывание из исходного файла
значений соответствующих полей
(данных о студентах)
Sum i=0
Обнуление сумматора
j=0… 4
Sumi =Sumi + Ocenj
Вывод в результирующий файл диалогового комментария о результатах
решения задачи
Вывод (FOut; «ДК»)
Вывод ( FOut; FIO,
Pol , Obr , Address , Stip,
Day, Month, Year )
j=0… 4
j
β
Рис. 7.3. Схема алгоритма основного процесса (начало)
54
Вывод («ДК»)
i=0… N–1
Считывание из исходного файла
значений элементов массива оценок
Вычисление значения суммы оценок, полученных i-м студентом
Ввод ( FIn; Ocen j)
α
Вывод («ДК»)
δ
γ
ε
Вывод в результирующий файл значений соответствующих полей (результатов отбора)
Рис. 7.3. Схема алгоритма основного процесса (продолжение)
55
γ
δ
ε
Вывод ( FOut ; Ocenj )
j
Вывод ( FOut ; KB)
i
fclose ( FOut)
Закрытие результирующего файла
Конец
Конец схемы алгоритма
Рис. 7.3. Схема алгоритма основного процесса (окончание)
Начало схемы алгоритма
Начало
Вывод диалогового комментария
Вывод («ДК»)
Ввод значения текущего года (полная запись – Today.Year)
Ввод (Year)
Обнуление сумматора (количество
вычисляемых по условию задачи
студентов)
*N=0
i=0… NS–1
Si == 25
Да
Pol == ‘w’
Да
Year+18<=Year
Да
Z1i =Z *N
*N=*N+1
– fopen – функция, используемая в среде программирования
C для реализации операции открытия файла;
– fclose – функция, используемая в среде программирования
C для реализации операции закрытия файла;
– r – параметр, используемый в среде программирования C для
задания режима «чтение из файла»;
– w – параметр, используемый в среде программирования C для
задания режима «запись в файл»;
– strcat – функция, используемая в среде программирования
C для конкатенации (связывания) строк;
– NULL – системная константа, используемая в среде программирования C и операционной системе Wndows;
– FIn – имя файловой переменной, значением которой является
полное обозначение исходного файла;
– FOut – имя файловой переменной, значением которой является полное обозначение результирующего файла.
Комментарии к схеме алгоритма, приведенной на рис. 7.4, соответствуют комментариям к схеме алгоритма, представленной на
рис. 6.2.
Нет
Проверка значения суммы оценок,
полученных i-м студентом
Нет
Проверка значения поля «Пол
студента» (полная запись условия –
Zi.Pol == ‘w’)
Нет
Проверка значения года
рождения студента (полная запись
условия – Zi.DateR.Year <= Today.Year)
Занесение в результирующий массив
данных о студентах, удовлетворяющих условию, и определение их численности
i
Конец
Конец схемы алгоритма
Рис 7.4. Схема алгоритма подпроцесса Otbor (Z, S, Z1, *N)
56
57
ЗАКЛЮЧЕНИЕ
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
Приведенные примеры алгоритмов решения типовых вычислительных задач должны помочь студенту освоить основные правила
и приемы составления алгоритмов и научить решать сложные задачи, представляя их решение в виде последовательности элементарных шагов.
Этап алгоритмизации вычислительных задач предваряет этап
программирования. При этом следует учитывать тот факт, что от
корректности составленного алгоритма решения задачи зависит
эффективность и качество программы, реализующей этап машинных вычислений. С этой целью приведем примеры программной
реализации алгоритмов решения некоторых задач, рассмотренных
в учебном пособии, в среде программирования Dev C ++ v.4.9.9.2
(см. Приложение).
1. С. Гудман, С. Хидетниеми. Введение в разработку и анализ
алгоритмов / пер. с англ. под ред. В. В.Мартынюка. – М.: Мир,
1981. – 368 с.
2. С. Л. Козенко. Алгоритмизация инженерных задач: программа и методические указания к самостоятельной работе студентов. –
СПб.: ГУАП, 2003. – 16 с.
3. С. Л. Козенко. Алгоритмизация инженерных задач: методические указания. – СПб.: ГУАП, 2005. – 46 с.
4. С. Л. Козенко. Информатика. Ч. 1. Лабораторный практикум. – СПб.: ГУАП, 2007. – 67 с.
5. С. Л. Козенко. Информатика. Ч. 2. Лабораторный практикум. – СПб.: ГУАП, 2007. – 54 с.
6. С. Л. Козенко. Информатика. Ч. 3. Лабораторный практикум. – СПб.: ГУАП, 2009. – 58 с.
58
59
ПРИЛОЖЕНИЕ
Пример 1.3 (а)
Текст программы
#include <stdio.h>
#include <math.h>
#include <conio.h>
int main()
{
float a, b, c, max;
printf("Vvedite a, b, c:\n");
scanf("%f%f%f", &a, &b, &c);
max=a;
if (b>max)
max=b;
if (c>max)
max=c;
printf("\nmax=%.2f", max);
getch();
return 0;
}
scanf("%f%f%f%i%i", &x0, &h, &p, &N, &M);
for(i=1;i<=M;i++)
{
x=x0+(i-1)*h;
bk=exp(-p)*x*x/2;
ak=1+bk;
printf("\na1=%.4f ", ak);
Pr=1;
for(k=2;k<=N;k++)
{
bk=bk*exp(-p)*x/(k+1);
ak=1+bk;
printf("a%i=%.4f ", k, ak);
if (k%2==0)
Pr*=ak;
}
printf("\nPr=%.4f x=%.2f\n", Pr, x);
}
getch();
return 0;
Результаты вычислений
Результаты вычислений
Пример 2.2
Текст программы
#include <stdio.h>
#include <math.h>
#include <conio.h>
int main()
{
float x0, h, p, x, ak, bk, Pr;
int N, M, i, k;
printf("Vvedite x0, h, p, N, M:\n");
60
Пример 3.2
Текст программы
#include <stdio.h>
61
#include <math.h>
#include <conio.h>
#define m 5
#define n 5
int main()
{
float A[m][n], Amax, Amin;
int i, j, Imax, Jmax, Imin, Jmin;
printf("Vvedite elemets A[%i][%i]:\n", m, n);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%f", &A[i][j]);
Amax=A[0][0];
Imax=0;
Jmax=0;
Amin=A[0][0];
Imin=0;
Jmin=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(A[i][j]>Amax)
{
Amax=A[i][j];
Imax=i;
Jmax=j;
}
else
if(A[i][j]<Amin)
{
Amin=A[i][j];
Imin=i;
Jmin=j;
}
printf("\nAmax=%.2f, Imax=%i, Jmax=%i\nAmin=%.2f, Imin=%i, Jmin=%i",
Amax, Imax+1, Jmax+1, Amin, Imin+1, Jmin+1);
getch();
return 0;
}
62
Результаты вычислений
Пример 3.7
Текст программы
#include <stdio.h>
#include <math.h>
#include <conio.h>
#define n 7
int main()
{
float A[n], R;
int i, j, Flag;
printf("Vvedite elemets A[%i]:\n", n);
for(i=0;i<n;i++)
scanf("%f", &A[i]);
for(i=1;i<n;i++)
{
Flag=0;
for(j=n-1;j>=i;j--)
if (fabs(A[j-1])<fabs(A[j]))
{
R=A[j-1];
A[j-1]=A[j];
A[j]=R;
Flag=1;
}
if (Flag==0)
break;
}
printf("\nUporyadochennyi Massiv A:\n");
for(i=0;i<n;i++)
63
}
printf("%.2f ", A[i]);
getch();
return 0;
Результаты вычислений
}
printf("\nMatrix Z[%i][%i]:\n", m, n);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
printf("%.1f ", Z[i][j]);
printf("\n");
}
getch();
return 0;
Результаты вычислений
Пример 4.5
Текст программы
#include <stdio.h>
#include <math.h>
#include <conio.h>
#define m 5
#define n 6
#define l 4
int main()
{
float Q[m][l], R[l][n], Z[m][n];
int i, j, k;
printf("Vvedite elemets Q[%i][%i]:\n", m, l);
for(i=0;i<m;i++)
for(j=0;j<l;j++)
scanf("%f", &Q[i][j]);
printf("\nVvedite elemets R[%i][%i]:\n", l, n);
for(i=0;i<l;i++)
for(j=0;j<n;j++)
scanf("%f", &R[i][j]);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
Z[i][j]=0;
for(k=0;k<l;k++)
Z[i][j]+=Q[i][k]*R[k][j];
}
64
Пример 5.2
Текст программы
#include <stdio.h>
#include <math.h>
#include <conio.h>
#define m 4
#define n 3
float Umn(float Z[m][n], float S, float Z1[m][n])
{
int i, j;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
65
}
Z1[i][j]=Z[i][j]*S;
int main()
{
float A[m][n], B[m][n], A1[m][n], B1[m][n];
int i, j;
printf("Vvedite elemets A[%i][%i]:\n", m, n);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%f", &A[i][j]);
printf("\n\nMatrix B[%i][%i]:\n", m, n);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
B[i][j]=sin(i)+cos(j);
printf("%.2f ", B[i][j]);
}
printf("\n");
}
Umn(A, 0.75, A1);
printf("\nMatrix A1[%i][%i]:\n", m, n);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
printf("%.2f ", A1[i][j]);
printf("\n");
}
Umn(B, 0.75, B1);
printf("\nMatrix B1[%i][%i]:\n", m, n);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
printf("%.2f ", B1[i][j]);
printf("\n");
}
getch();
return 0;
}
66
Результаты вычислений
Пример 6.1
Текст программы
#include <stdio.h>
#include <math.h>
#include <conio.h>
#define NS 8
#define NFIO 18
typedef struct
{
int Day;
int Month;
int Year;
} Date;
typedef struct
{
char FIO[NFIO];
char Pol;
char Obr;
char Address;
char Stip;
Date DateR;
int Ocen[5];
67
int KB;
} Stud;
void Otbor(Stud Z[NS], int S[NS], Stud Z1[NS], int *N)
{
int i;
Date Today;
printf("\nEnter current year - ");
scanf("%i", &Today.Year);
*N=0;
for(i=0;i<NS;i++)
if(S[i]==25)
if(Z[i].Pol=='w')
if(Z[i].DateR.Year+18<=Today.Year)
{
Z1[*N]=Z[i];
*N=*N+1;
}
}
int main()
{
Stud Group[NS], Group1[NS];
int Sum [NS], i, j, N;
printf("Enter data:\nIvanov_I.P.______ m s p y 11 11 1998 5 4 3 4 3 171\n\n");
for(i=0;i<NS;i++)
{
scanf("%s %c %c %c %c%i%i%i", Group[i].FIO, &Group[i].Pol,
&Group[i].Obr, &Group[i].Address, &Group[i].Stip,
&Group[i].DateR.Day, &Group[i].DateR.Month, &Group[i].DateR.Year);
Sum[i]=0;
for(j=0;j<5;j++)
{
scanf("%i", &Group[i].Ocen[j]);
Sum[i]+=Group[i].Ocen[j];
}
scanf("%i", &Group[i].KB);
}
Otbor (Group, Sum, Group1, &N);
printf("\nItogovyi spisok studentov:\n");
for(i=0;i<N;i++)
68
{
}
printf("%s %c %c %c %c %i %i %i ", Group1[i].FIO, Group1[i].Pol,
Group1[i].Obr, Group1[i].Address, Group1[i].Stip,
Group1[i].DateR.Day, Group1[i].DateR.Month, Group1[i].DateR.Year);
for(j=0;j<5;j++)
printf("%i ", Group1[i].Ocen[j]);
printf("%i\n", Group1[i].KB);
}
getch();
return 0;
Результаты вычислений
Пример 7.2
Текст программы
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <string.h>
#define NS 8
#define NFIO 18
typedef struct
{
int Day;
69
int Month;
int Year;
} Date;
typedef struct
{
char FIO[NFIO];
char Pol;
char Obr;
char Address;
char Stip;
Date DateR;
int Ocen[5];
int KB;
} Stud;
// function Otbor
void Otbor(Stud Z[NS], int S[NS], Stud Z1[NS], int *N)
{
int i;
Date Today;
printf("\n\nEnter current year - ");
scanf("%i", &Today.Year);
*N=0;
for(i=0;i<NS;i++)
if(S[i]==25)
if(Z[i].Pol=='w')
if(Z[i].DateR.Year+18<=Today.Year)
{
Z1[*N]=Z[i];
*N=*N+1;
}
}// end Otbor
// function main
int main()
{
FILE *FIn, *FOut;
Stud Group[NS], Group1[NS];
int Sum[NS];
int i, j, N;
70
char Dir1[50], FileName1[50], Dir2[50], FileName2[50];
printf("Enter path input for example - D:\\$Student\\GR_1609\\Abramov\\\n");
scanf("%s", Dir1);
printf("\nEnter FileName input:\n");
scanf("%s", FileName1);
strcat(Dir1, FileName1);
if((FIn=fopen(Dir1, "r"))==NULL)
{
printf("Path or file not exist");
getch();
return 1;
}
printf("\n%s - O'K", Dir1);
//printf("\nEnter input data\n\n");
for(i=0;i<NS;i++)
{
fscanf(FIn,"%s %c %c %c %c%i%i%i", Group[i].FIO, &Group[i].Pol,
&Group[i].Obr, &Group[i].Address, &Group[i].Stip,
&Group[i].DateR.Day, &Group[i].DateR.Month, &Group[i].DateR.Year);
Sum[i]=0;
for(j=0;j<5;j++)
{
fscanf(FIn,"%i", &Group[i].Ocen[j]);
Sum[i]+=Group[i].Ocen[j];
}
fscanf(FIn,"%i", &Group[i].KB);
}
fclose(FIn);
Otbor(Group, Sum, Group1, &N);
printf("\nEnter path output for example - D:\\$Student\\GR_1609\\Abramov\\\n");
scanf("%s", Dir2);
printf("\nEnter FileName output:\n");
scanf("%s", FileName2);
strcat(Dir2, FileName2);
if((FOut=fopen(Dir2, "w"))==NULL)
{
printf("Path not exist");
getch();
return 1;
}
printf("\n%s - O'K", Dir2);
71
}
fprintf(FOut,"Itogovyi spisok studentov:\n\n");
for(i=0;i<N;i++)
{
fprintf(FOut,"%s %c %c %c %c %i %i %i ", Group1[i].FIO, Group1[i].Pol,
Group1[i].Obr, Group1[i].Address, Group1[i].Stip,
Group1[i].DateR.Day, Group1[i].DateR.Month, Group1[i].DateR.Year);
for(j=0;j<5;j++)
fprintf(FOut,"%i ", Group1[i].Ocen[j]);
fprintf(FOut,"%i\n", Group1[i].KB);
}
fclose(FOut);
getch();
return 0;
Результаты вычислений
72
73
СОДЕРЖАНИЕ
Учебное издание
Предисловие............................................................................ 3
1. Введение в алгоритмизацию задач........................................... 1.1. Основные понятия и определения..................................... 1.2. Поиск экстремальных значений среди
нескольких величин...................................................... 5
5
2. Алгоритмы обработки числовых последовательностей................ 11
3. Алгоритмы обработки массивов данных.................................... 3.1. Общие понятия.............................................................. 3.2. Поиск экстремальных элементов в массиве........................ 3.3. Вычисление значения суммы (произведения)
элементов массива........................................................ 3.4. Сортировка (упорядочение) массива................................. 16
16
16
4. Алгоритмизация задач линейной алгебры................................. 4.1. Общие положения.......................................................... 4.2. Транспонирование матриц.............................................. 4.3. Вычисление значения следа квадратной матрицы .............. 4.4. Сложение матриц и векторов........................................... 4.5. Умножение матриц и векторов......................................... 26
26
26
27
28
30
5. Алгоритмы обработки массивов данных
с использованием подпроцессов.................................................. 33
6. Обработка сложных структур данных....................................... 6.1. Общие положения.......................................................... 6.2. Примеры работы со сложными структурами данных........... 40
40
41
7. Работа с файлами данных....................................................... 7.1. Общие сведения............................................................. 7.2. Примеры работы с файлами............................................ 48
48
48
Заключение............................................................................. 58
Рекомендуемая литература........................................................ 59
Приложение............................................................................. 60
8
Козенко Сергей Леонидович
20
21
АЛГОРИТМИЗАЦИЯ
ВЫЧИСЛИТЕЛЬНЫХ
ЗАДАЧ
Учебное пособие
Публикуется в авторской редакции
Компьютерная верстка Ю. В. Умницына
Сдано в набор 02.12.16. Подписано к печати 30.12.16. Формат 60 × 84 1/16.
Усл. печ. л. 4,35. Уч.-изд. л. 4,68.
Тираж 50 экз. Заказ № 530.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
74
Документ
Категория
Без категории
Просмотров
0
Размер файла
2 355 Кб
Теги
kozenkov
1/--страниц
Пожаловаться на содержимое документа