Гваева И.В.

Новиков В.И.

Обернихина И.С.

Щербович Ж.И.

ИНФОРМАЦИОННЫЙ ПРОФЕССИОНАЛИЗМ И СТРУКТУРЫ ДАННЫХ ИНФОРМАЦИОННЫХ СИСТЕМ

Практикум

Минск 2007

Содержание

Введение 3

Основные понятия 4

Тема 1. Линейные алгоритмы 20

Примеры построения линейных алгоритмов 20

Задания для самостоятельного выполнения 22

Тема 2. Разветвляющиеся алгоритмы 24

Примеры построения разветвляющихся алгоритмов 24

Задания для самостоятельного выполнения 28

Тема 3. Циклические алгоритмы. Одномерные массивы 29

Примеры построения алгоритмов на одномерных массивах 29

Задания для самостоятельного выполнения 31

Тема 4. Циклические алгоритмы. Двумерные массивы 33

Примеры построения алгоритмов на двумерных массивах 34

Задания для самостоятельного выполнения 37

Тема 5. Циклические алгоритмы. Трехмерные массивы 39

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

Задания для самостоятельного выполнения 44

Литература 46

Приложение 1. Символы (ГОСТ 19.701-90) 47

Введение

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

Данный практикум представляет собой сборник задач с примерами решения на уровне составления блок-схем алгоритмов типовых задач по теме курса «Структуры данных, информации и информационных ресурсов». В практикуме рассматриваются вопросы построения алгоритмов простейших вычислительных процессов:

- линейных;

- ветвящихся;

- циклических.

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

Основные понятия

Алгоритм - описание последовательности действий для решения задачи или достижения поставленной цели.

Алгоритм - правила выполнения основных операций обработки данных.

Алгоритм - описание вычислений по математическим формулам.

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

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

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

ПОНЯТИЕ АЛГОРИТМА И СПОСОБЫ ЕГО ЗАПИСИ

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

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

Составление алгоритма рассмотрим на элементарном примере. Допустим, имеется ряд чисел: 12, 18, 40, —20, 7, .... 53. Требуется определить сумму положительных чисел этого ряда. Задача до­вольно проста, достаточно выбрать положительные числа и сло­жить их. Для решения ее на ЭВМ необходимо составить алгоритм, указав все элементарные операции в нужной последовательности. Полагаем, что сумма положительных чисел равна 0. Просматри­ваем последовательно числа, начиная с первого. С каждым новым положительным числом сумма будет увеличиваться. Количество чисел определено, и каждый раз, переходя к новому числу, необ­ходимо проверить, есть ли еще числа, чтобы через определенное количество шагов закончить вычисление и выдать полученный ре­зультат.

Запишем алгоритм на обычном языке. Каждый шаг алгоритма связан с выполнением определенной команды.

Шаг 1. Пусть начальное значение суммы равно 0.

Шаг 2. Прочти 1-е число.

Шаг 3. Проверь, если значение его положительное, то выполни шаг 4, в противном случае выполни шаг 5.

Шаг 4. Прибавь это число к текущей сумме.

Шаг 5. Проверь, есть ли еще числа. Если «да», то выполни шаг б, в противном случае выполни шаг 7.

Шаг 6. Прочти следующее число, затем вернись к шагу 3.

Шаг 7. Выпиши полученную сумму.

Шаг 8. Остановись, т. е. прекрати вычисления.

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

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

Шаг 1. S=0, где S — сумма положительных чисел.

Шаг 2. Прочти 1-е число; i=1 (i — порядковый номер числа).

Шаг 3. Если a_i>0, то выполни шаг 4, в противном случае —шаг 5

(a_i—a_i значение числа с порядковым номером i)

Шаг 4. S=S+a_i и т. д.

Шаг 5. Конец вычислений.

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

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

В качестве примера рассмотрим выполнение операторной схемы для ранее составленного алгоритма, используя при этом следующие операторы: В — оператор ввода, представляющий ввод исходных данных в ЭВМ; А — арифметический оператор, предусматривающий выполнение арифметических операций; Р — логический оператор, предусматривающий проверку некоторых условий с целью установления порядка выполнения других операторов; П — оператор, представляющий печать результатов; Я — оператор останова, прекращения вычислений.

Каждый оператор имеет порядковый номер, соответствующий последовательности операций в составленном алгоритме: B₁ — ввод данных; А₂ —S:=0; А₃ — i:= 1; Р₄ —а_i>0; A₅ — S:=S+a_i; А₆— i:=i+1; Р₇ — i>п; П₈ — печать результатов; Я₉— останов (S — сумма положительных чисел, i — порядковый номер числа, a_i — число, соответствующее порядковому номеру i, n — количест­во чисел).

При проверке условия, заданного логическим оператором Р, справа от него ставится оператор, соответствующий выполнению поставленного условия. Если условие не выполнено, то к очередному оператору проводится линия со стрелкой, как это показано на представленной ниже операторной схеме:

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

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

Основные операторы

Название символа	Графическое представление	Описание
Пуск-останов		Начало или конец алгоритмов. Внутри фигуры пишут «начало» или «конец» соответственно.
Действие		Прямоугольником обозначается операция. Например, присваивание.
Условие		Внутри ромба пишутся проверяемые условия. Оператор условия имеет две или три выхода в зависимости от проверенных условий.
Ввод-вывод		Параллелограмм обозначает операции ввода-вывода данных.

Наглядность и обозримость схемы, целостность восприятия, однозначность в отображении вычислительного процесса облегчают чтение алгоритма, проверку его правильности и внесение изменений. Графическое отображение алгоритма облегчает также составление программы для решения задачи на ЭВМ.

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

Рис. 4.1 Графическая запись алгоритма

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

1. анализ условия задачи;

2. выделение элементарных арифметических и логических операций, которые необходимо выполнить;

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

4. запись алгоритма графически в виде схемы или иным способом.

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

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

результативность. Реализация вычислительного процесса, предусмотренного алгоритмом, должна через определенное число шагов привести к выдаче результата или сообщения о невозможности решения задачи;

массовость. Решение однотипных задач с различными исходными данными может быть осуществлено по одному алгоритму. Это дает возможность создавать типовые программы для решения многих экономических задач;

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

ПРАВИЛА ВЫПОЛНЕНИЯ СХЕМ АЛГОРИТМОВ

Правила выполнения схем алгоритмов и программ установлены ГОСТ 19.701-90 ЕСПД.

ЛИНИИ ПОТОКА

Линии потока — это прямые, соединяющие символы на схеме и указывающие последовательность связей между ними. Как и контур символа, они проводятся сплошной основной линией (ГОСТ . 2.303—68 ЕСКД). Линии потока проводятся параллельно линиям рамки; направление их сверху вниз и слева направо принято за основное и стрелками не обозначается. Во всех других случаях на конце линии потока ставится стрелка, которая изображается по типу стрелок на размерных линиях (ГОСТ 2.307—68 ЕСКД) (см. рис. 1.12). В случае изменения направления линии потока она про­водится с изломом под углом 90° и независимо от направления составляющих отрезков ломаной линии всегда заканчивается стрелкой (рис. 4.7).

Если схема занимает более одного листа, линия потока обрывается, а для связи символов используется межстраничный соединитель. По форме символ межстраничного соединителя напоминает стрелку, положение его может изменяться в зависимости от направления линии потока, с которой он связан (см. рис. 4.4; 4.7). Внутри символа «межстраничный соединитель» указывается адрес — откуда (или куда) направлена линия потока. Надпись дается в две строки: в первой строке указывается номер листа, во второй — порядковый номер символа или era координаты. На рис. 4.12 показано продолжение схемы с 6-го на 7-й лист. На месте обрыва линии потока, на одном и другом листе, изображен межстраничный соединитель.

На листе 6 на месте обрыва линии потока, проведенной от символа 15, изображен межстраничный соединитель, внутри кото­рого указан адрес 007 16, где 007 —номер листа, на который переносится продолжение программы, 16 —порядковый номер символа, к которому направлена линия потока.

Прерванная линия потока на листе 7 начинается с межстра­ничного соединителя. Адрес 00615 внутри соединителя указывает: 006 — номер листа, с которого перенесено продолжение схемы; 15 — порядковый номер символа, от которого следует линия потока.

ВОЗМОЖНЫЕ ВАРИАНТЫ ОТОБРАЖЕНИЯ РЕШЕНИЯ

Символ «решение» ото­бражает на схеме выбор направления выполнения алгоритма или программы в зависимости от результатов проверки условия, указанного внутри этого символа. В одном случае условие может предопределять только два возможных направления в процессе вычислений. Например А=В? При выполнении этого условия направление вычислений обозначается словом «Да», в противном случае—словом «Нет». Слова «Да» и «Нет» пишутся строчными буквами, начиная с заглавных (прописных), и располагаются ближе к символу «решение», справа от соответствующей линии потока, если она направлена вертикально, и над линией потока, если она направлена горизонтально (рис. 4.15, а). Если условие предусматривает три исхода, как показано на рис. 4.15, б, у каждого из трех предусмотренных направлений процесса вычислений ставится соответствующий признак условия.

На рис. 4.15, в показан пример, когда количество условий и. соответствующих им исходов более трех. У линии потока, направленной от символа «решение», где предусмотрен анализ условий, приведены условия и адреса исходов. Например, при выполнении условия У₁ символом-преемником будет символ, расположенный в зоне Е1 11-го листа, к нему направлено продолжение процесса вычислений от символа «решение». При выполнении другого условия адрес символа-преемника изменяется.

СОСТАВЛЕНИЕ СХЕМЫ АЛГОРИТМА

Как составить схему алгоритма? Начнем с рассмотрения конкретного примера. Допустим, имеется массив целых чисел, организованных в форме вектора. Число элементов вектора — 20; А — имя вектора; i — индекс элемента, определяющий его порядковый номер. Максимальное значение i=20. Требуется определить сумму всех элементов вектора А. Обозначим сумму буквой S.

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

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

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

1. Изображение схемы начинаем с символа «пуск-останов», так как каждый вычислительный процесс имеет начало и конец и это должно быть отражено на схеме. Внутри символа пишется слово «начало» (рис. 4.16).

2. Исходные данные вводятся в оперативную память машины. Для обозначения этой операции используется символ «ввод-вывод». Внутри этого символа указываются имя и размерность массива — ввод вектора А_[20].

3. По условию задачи необходимо определить сумму элементов вектора. Сумма обозначена произвольно выбранной буквой S. Пользуясь символом «комментарий», расшифровываем принятое обозначение, чтобы каждый мог прочесть его однозначно: S:=0. Сумме S присваивается нулевое значение. Это означает пересылку 0 в ту ячейку, которая предназначена для накапливания суммы. Мы как бы очищаем ячейку от каких-либо других значений, чтобы не допустить искажения результата. Для отображения операции присваивания на схеме используется символ «процесс».

4. Индекс i, определяющий порядковый номер элемента, принимает значение 1. i: = 1, обращаемся к первому элементу вектора.

5. К сумме S, имеющей нулевое значение, прибавляем первый элемент вектора: S:=S+а_i. В ячейке памяти, предназначенной для S, появляется новое значение суммы.

6. Количество элементов вектора определено, в данном примере — 20, следовательно, повторять операцию суммирования (S:=S+а_i) мы можем столько раз, сколько элементов содержит вектор, т. е. 20 раз.

Осуществляется проверка, продолжать суммирование или закончить. При выборе направления вычислений на схеме используется символ «решение». Внутри символа ставится вопрос: i=20? Предусмотрены два возможных направления: если i достигло своего максимального значения, то полученная сумма S выводится на печать и процесс вычислений прекращается. В противном случае переходим к новому элементу вектора и операция суммирования повторяется.

7. С увеличением значения i на 1 (i: =i + 1) получаем новый элемент вектора, для чего используется символ «модификация». Новый элемент прибавляем к текущей сумме, на схеме показано возвращение к символу 5. Последовательность операций, отображенных на схеме символами 5, 6 и 7, будет повторяться (в нашем примере 20 раз).

8. Получив окончательный результат, т. е. сумму всех 20 элементов вектора, значение 5 выдается на печать. Операция вывода данных изображается на схеме символом «ввод-вывод». Внутри символа следует написать «вывод S».

9. Заканчивается схема символом «пуск-останов», внутри которого пишется слово «Конец».

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

Направленные снизу вверх или справа налево, линии потока должны заканчиваться стрелкой. Слова «Да» и «Нет» у символа «решение» пишутся правее линии потока или над ней. Символ «комментарий» использован для пределения выполняемой операции (символ 5) и для пояснения буквенного обозначения S (символ 3).

ЭЛЕМЕНТАРНЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ

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

1. Последовательность двух или более операций. Выполняемые операции независимы от условий и последовательно располагаются на схеме, одна за другой. Эта структура имеет место на том участке, где отображается вычисление простых арифметических выражений (рис. 4.17).

2. Выбор направления. Решение задачи зависит от результата проверки некоторого заранее определенного условия, признак которого указывается, как правило, внутри символа «решение». В зависимости оттого, выполняется ли это условие, выбирается одно из предусмотренных направлений процесса вычислений, так называемых ветвей. При этом могут быть два варианта.

Первый вариант. Вычислительный процесс организован по двум ветвям. Направление вычислений выбирается путем проверки выполнения определенных условий. Результаты проверки зависят от свойств исходных данных или от промежуточных результатов. Например, необходимо определить количество положительных и количество отрицательных элементов вектора A. Обозначим их соответственно K₁ и K₂. Если элемент положительный, т. е. а_i>0, то вычисление идет по правой ветви, К₁ увеличивается на 1. Если а_i<0, выбирается другая ветвь, количество отрицательных элементов К₂ увеличивается на 1. Вычисление предусмотрено по одной и другой ветви (рис. 4.18, а).

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

Если элемент равен 5, К увеличивается на 1; если условие не соблюдается, вычисление не выполняется, а линия потока направлена к операции изменения значения индекса, что обозначает переход к следующему элементу (рис. 4.18, б).

3. Повторение. Операция может повторяться при соблюдении определенного условия. Обратимся к примеру, представленному на рис. 4.19. Операция S: = S + a_i будет повторяться до тех пор, пока индекс i не достигнет максимального значения, т. е. 20 раз. После каждого шага проверяется значение индекса i. На рис. 4.19, а проверка осуществляется после операции сложения, а затем уже, при условии если i<20, индекс i увеличивается на 1 и вновь повторяется операция сложения.

На рис. 4.19, б взаимное положение символов несколько изменено. Проверка осуществляется после изменения значения индекса: при условии i< или i=20 прибавляется новый элемент.

И первое и второе взаимное положение символов допустимо. Когда внутри символа «решение» поставлено условие, нужно быть внимательным при выборе ветви (да, нет), чтобы выбор был логически оправдан.

Каждая из трех представленных выше структур должна иметь единственную точку входа в структуру и единственную точку выхода из нее и перехода к следующему шагу программы или к следующей алгоритмической структуре.

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

Вычислительные процессы, выполняемые ЭВМ по заданной: программе, подразделяют на три основных вида: линейные, ветвящиеся и циклические.