Практикум
Минск 2007
Содержание
Введение. 3
Основные понятия. 4
Тема 1. Линейные алгоритмы.. 7
Примеры построения линейных алгоритмов. 7
Задания для самостоятельного выполнения. 9
Тема 2. Разветвляющиеся алгоритмы.. 11
Примеры построения разветвляющихся алгоритмов. 11
Задания для самостоятельного выполнения. 16
Тема 3. Циклические алгоритмы.Одномерные массивы.. 17
Примеры построения алгоритмов на одномерных массивах. 17
Задания для самостоятельного выполнения. 19
Тема 4. Циклические алгоритмы.Двумерные массивы.. 21
Примеры построения алгоритмов на двумерных массивах. 22
Задания для самостоятельного выполнения. 25
Тема 5. Циклические алгоритмы. Трехмерные массивы.. 27
Примеры построения алгоритмов на трехмерных массивах. 28
Задания для самостоятельного выполнения. 32
Литература. 34
Приложение 1. Символы (ГОСТ 19.701-90) 36
Введение
Одной из важнейших задач курса «Информационный профессионализм и структуры данных информационных систем» является развитие алгоритмических способностей студентов путем изучения структур данных информационных систем, навыков алгоритмизации линейных, ветвящихся и циклических вычислительных процессов.
Данный практикум представляет собой сборник задач с примерами решения на уровне составления блок-схем алгоритмов типовых задач по теме курса «Структуры данных, информации и информационных ресурсов». В практикуме рассматриваются вопросы построения алгоритмов простейших вычислительных процессов:
- линейных;
- ветвящихся;
- циклических.
При написании практикума авторы руководствовались тем, что подготовка студентов 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. Если ai>0, то выполни шаг 4, в противном случае —шаг 5
(ai—ai значение числа с порядковым номером i)
Шаг 4. S=S+ai и т. д.
Шаг 5. Конец вычислений.
Алгоритм решения задачи может быть записан в виде операторной схемы. Операторная схема представляет собой последовательность символов-операторов, расположенных в том порядке (в направлении слева направо), как это предусмотрено алгоритмом решения задачи.
Оператором принято называть указание на выполнение определенных действий при реализации программы. Оператор в программе — это совокупность символов, указывающих операцию и значение или местоположение ее операндов.
В качестве примера рассмотрим выполнение операторной схемы для ранее составленного алгоритма, используя при этом следующие операторы: В — оператор ввода, представляющий ввод исходных данных в ЭВМ; А — арифметический оператор, предусматривающий выполнение арифметических операций; Р — логический оператор, предусматривающий проверку некоторых условий с целью установления порядка выполнения других операторов; П — оператор, представляющий печать результатов; Я — оператор останова, прекращения вычислений.
Каждый оператор имеет порядковый номер, соответствующий последовательности операций в составленном алгоритме: B1 — ввод данных; А2 —S:=0; А3 — i:= 1; Р4 —аi>0; A5 — S:=S+ai; А6— i:=i+1; Р7 — i>п; П8 — печать результатов; Я9— останов (S — сумма положительных чисел, i — порядковый номер числа, ai — число, соответствующее порядковому номеру i, n — количество чисел).
При проверке условия, заданного логическим оператором Р, справа от него ставится оператор, соответствующий выполнению поставленного условия. Если условие не выполнено, то к очередному оператору проводится линия со стрелкой, как это показано на представленной ниже операторной схеме:
Алгоритм может быть записан на алгоритмическом языке. Алгоритмический язык — набор символов и система правил образования и истолкования конструкций из этих символов для задания алгоритмов. Алгоритмические языки, предназначенные для записи программ и данных, называют языками программирования.
Структура алгоритма может быть отображена графически в виде схемы. Графический способ записи алгоритма по сравнению с рассмотренными ранее имеет ряд преимуществ. Во-первых, он наиболее нагляден: на схеме алгоритма каждая операция вычислительного процесса изображается определенной геометрической фигурой, внутри которой дается краткая запись содержания операции. Начертания этих геометрических фигур — символов, их размеры и отображаемые ими функции определены ГОСТом, что обеспечивает однозначную запись и чтение схемы алгоритма. ГОСТ определяет также правила выполнения схем. Во-вторых, графическое изображение алгоритма дает возможность наглядно показать разветвление путей решения задачи в зависимости от выполнения поставленного условия, отобразить многократное повторение отдельных этапов вычислительного процесса.
Основные операторы
| Название символа | Графическое представление | Описание |
| Пуск-останов | 
| Начало или конец алгоритмов. Внутри фигуры пишут «начало» или «конец» соответственно. |
| Действие | 
| Прямоугольником обозначается операция. Например, присваивание. |
| Условие | 
| Внутри ромба пишутся проверяемые условия. Оператор условия имеет две или три выхода в зависимости от проверенных условий. |
| Ввод-вывод | 
| Параллелограмм обозначает операции ввода-вывода данных. |
Наглядность и обозримость схемы, целостность восприятия, однозначность в отображении вычислительного процесса облегчают чтение алгоритма, проверку его правильности и внесение изменений. Графическое отображение алгоритма облегчает также составление программы для решения задачи на ЭВМ.
Алгоритм, словесная запись которого рассмотрена ранее, на рис. 4.1 представлен в виде схемы. На схеме графическими символами отображены операции вычислительного процесса в установленной последовательности их выполнения, выявлены логические связи между ними, определен этап вычислительного процесса, который многократно повторяется. Операция сложения повторяется столько раз, сколько в данном ряде положительных чисел.
Рис. 4.1 Графическая запись алгоритма
Точных указаний о том, как составить алгоритм, нет, но определенная последовательность в составлении алгоритма должна быть выдержана. Можно выделить следующие основные этапы:
1) анализ условия задачи;
2) выделение элементарных арифметических и логических операций, которые необходимо выполнить;
3) определение последовательности выполнения операций. Если решение задачи связано с выполнением определенных условий, то при составлении алгоритма должна быть предусмотрена проверка выполнения условий с целью выбора направления в процессе вычислений;
4) запись алгоритма графически в виде схемы или иным способом.
При составлении алгоритма необходимо учитывать следующие требования, предъявляемые к алгоритму:
определенность. Алгоритм должен быть однозначным, исключающим любое произвольное толкование отображаемого им вычислительного процесса;
результативность. Реализация вычислительного процесса, предусмотренного алгоритмом, должна через определенное число шагов привести к выдаче результата или сообщения о невозможности решения задачи;
массовость. Решение однотипных задач с различными исходными данными может быть осуществлено по одному алгоритму. Это дает возможность создавать типовые программы для решения многих экономических задач;
дискретность. Определяемый алгоритмом вычислительный процесс может быть расчленен на отдельные этапы, элементарные операции.