Перечень, наименование, обозначение символов и отображаемые ими функции

Кафедра «информатика»

 

 

 

 

Алгоритмы в блок-схемах

 

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

к выполнению лабораторной работы

для студентов

по направлениям 190000, 200000, 260000, 280000

специальностей 140211, 150202, 151001, 150002,

19201, 190601, 190603, 190702, 200503, 260601, 280101

 

Курган 2006

 

 

Кафедра: «Информатика»

 

Дисциплина: «Информатика»

(направления: 190000, 200000, 260000, 280000

специальности: 140211, 150202, 151001, 150002, 19201, 190601, 190603, 190702, 200503, 260601, 280101)

 

Составили:

старший преподаватель Сысолятина Л.Г.

старший преподаватель Бекишева М.Б.

 

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

 

 

Утверждены на заседании кафедры «25» мая 2006 г., протокол № 8

 

Рекомендованы методическим советом Курганского государственного университета

«____» _______________ 2006 г.

Введение

Прежде чем обратиться к рассмотрению конкретных алгоритмов, необходимо определиться с тем, что же такое алгоритм. Традиционно считается, что самый первый алгоритм был придуман древнегреческим математиком Евклидом – правило нахождения общего делителя двух целых чисел. В современной математике понятие алгоритма является ключевым понятием, которое восходит к работам выдающегося узбекского математика IX века Аль-Хорезми.

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

Алгоритм и его свойства

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

Исполнитель алгоритма -это тот объект или субъект, для управления которым составлен алгоритм.

Система команд исполнителя (СКИ) - это вся совокупность команд, которые исполнитель умеет выполнять.

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

Понятность: алгоритм составляется только из команд, входящих в СКИ исполнителя.

Точность: каждая команда алгоритма управления определяет однозначное действие исполнителя.

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

Среда исполнителя: обстановка, в которой функционирует исполнитель.

Определенная последовательность действий исполнителя всегда применяется к некоторым исходным данным. Например: для приготовления блюда по кулинарному рецепту нужны соответствующие продукты (данные). Для решения математической задачи (решение квадратного уравнения) нужны исходные числовые данные (коэффициенты уравнения).

Полный набор данных: необходимый и достаточный набор данных для решения поставленной задачи (получения искомого результата).

 

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

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

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

При составлении блок-схемы алгоритма рекомендуется располагать ее на одной странице ученической тетради и придерживаться правил, установленных ГОСТ 19.002-80 «Схемы алгоритмов и программ. Правила выполнения» и ГОСТ 19.003-80 «Схемы алгоритмов и программ. Обозначения условные графические».

Фрагменты ГОСТ 19.002-80

Единая система программной документации

Схемы алгоритмов и программ

Правила выполнения

 

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

Стандарт полностью соответствует МС ИСО 2636-73.

 

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

1.1.1. При выполнении схем алгоритмов и программ отдельные функции алгоритмов и программ, с учетом степени их детализации, отображаются в виде словных графических обозначений – символов по ГОСТ 19.003-80.

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

1.1.3. Координаты зоны представляют:

по горизонтали – арабскими цифрами слева направо в верхней части листа;

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

1.1.4. Координаты зон в виде сочетания букв и цифр присваиванию символам, вписанным в поля этих зон, например А1, А2, А3, В1, В2, В3 и т.д.

При выполнении схем от руки, если поле листа не разбито на зоны, символам присваивают порядковые номера.

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

1.1.6. Расположение символов на схеме должно соответствовать требованиям ГОСТ 19.003-80.

1.1.7. Линии потока должны быть параллельны линиям внешней рамки схемы.

1.1.8. Направления линии потока сверху вниз и слева направо принимают за основные и, если линии потока не имеют изломов, стрелками можно не обозначать. В остальных случаях направление линии потока обозначать стрелкой обязательно.

1.1.9. Расстояние между параллельными линиями потока должны быть не менее 3 мм, между остальными символами схемы – не менее 5 мм.

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

1.1.11. Для удобства детализации программы должны быть использованы символы «Процесс», «Решение», «Модификация», «Ввод-вывод» и «Пуск-останов», при этом внутри символов на расстоянии не менее 0,25 а проводят тонкую линию (размер а по ГОСТ 19.003-80)

1.1.12. Записи внутри символов должны быть представлены так, чтобы их можно было читать слева направо и сверху вниз, независимо от направления потока (черт. 1) Вид а должен быть прочитан как вид б.

 

 

А б

Рис. 1

Правила применения символов

1.2.1. Применение символов должно соответствовать указанному в табл. 1.

Таблица 1

Фрагмент схемы	Содержание обозначения	Правила применения
В3 В2     19 18 20 1 2 А В1 Е5 В1 В1 А А А3 5 5 0 10 Е3 Е3 Е2 а Лист 0 10 Лист 0 12 А3 б = y1 011E1 y2 016A1 y3 005B5 y1 015E4	Возможные варианты обозначения символов в схемах: В2, В3, С2 – координаты зоны листа, в которой размещен символ     18, 19, 20 - порядковые номера символов на схеме     Комментарий   Продолжение таблицы 1   Соединитель: Е5, В1, А, 5 – идентификаторы соединителя в виде: Буквы и цифры (координаты зоны листа)     буквы     цифры     Межстраничный соединитель Первая строка внутри межстраничного соединителя определяет номер листа схемы, вторая – координату символа   А3 – определяет зону на данном листе, где расположен символ «Комментарий» 010Е3 – определяет номер листа и зону расположения, связываемую с символом Е3 Продолжение таблицы 1   Линии потока   Излом линии потока под углом 90°     Пересечение линий потока     Слияние линий потока: место слияний линий потока обозначается точкой     Продолжение таблицы 1 Возможные варианты отображения решения А = В, Р ³ 0 – условия решений; А, В, Р - параметры     yi - условие i -го исхода. 011Е1, 016А3, 005В5, 015Е4 – адреса исходов. Структура адреса имеет вид XXXXX координата символа номер листа схема В5 – знак, указывающий, что условия решения даются в виде таблицы или символа «Комментарий», расположенных на данном листе в зоне В5   Начало, прерывание и конец алгоритма или программы:   пуск   прерывание   останов	Координату зоны символа или порядковый номер проставляют слева в верхней части символа в разрыве его контура     Допускается не проставлять координаты символов при выполнении схем от руки и при наличии координатной сетки Применяется, если пояснение не помещается внутри символа (для пояснения характера параметров, особенностей процесса, линий потока и др.) Комментарий записывают параллельно основной надписи Комментарий помещают в свободном месте схемы алгоритма на данном листе и соединяют с поясняемым символом   При большой насыщенности схемы символами отдельные линии потока между удаленными друг от друга символами допускается обрывать. При этом в конце (начале) обрыва должен быть помещен символ «Соединитель»     а) связывание линией потока символы находятся на разных листах. Примечание. При изготовлении схем с помощью ЭВм допускается указывать рядом с обрывом линии потока адресные ссылки без использования символов «Соединитель» и «Межстраничный соединитель»; б) в случае связи некоторого символа со многими другими символами, расположенными на разных листах, на входе этого символа помещают один символ «Межстраничный соединитель». Внутри которого на первой строке помещают знак #, а на второй строке – координаты символа «Комментарий». Внутри символа «Комментарий» указывают номера страниц и координаты символов, связанных с поясняемым символом Применяют для указания направления линии потока: можно без стрелки, если линия направлена слева направо и сверху вниз; со стрелкой – в остальных случаях Обозначает изменение направлений линии потока   Применяется в случае пересечения двух несвязанных линий потока     Применяется в случае слияния линий потока, каждая из которых направлена к одному и тому же символу на схеме Место слияния линий потока допускается обозначать точкой или цифрой 0   При числе исходов не более трех признак условия решения (Да, Нет, =, >, <) проставляют над каждой выходящей линей потока или справа от линии потока   При числе исходов более трех условие исхода проставляется в разрыве линии потока. Адрес исхода проставляется в продолжении условия исхода и отделяется от него пробелом;   в символе «Соединитель» указывают координату зоны, куда должна помещаться таблица или символ «Комментарий»     Символы применяют в начале схемы алгоритма или программы, в случае прерывания е и в конце Внутри символа «Пуск-останов» может указываться наименование действия или идентификатор программы

Фрагменты ГОСТ 19.003-80

Единая система программной документации

Схемы алгоритмов и программ

Обозначения условные графические

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

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

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

 

Линейный алгоритм

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

Х:=5

Команда присваивания – команда исполнителя, в результате которой переменная получает новое значение.

Пример: x:=5 Переменной X присваивается значение,

равное 5.

Команда ввода - команда, по которой значения переменных задаются через устройства ввода (например, клавиатуру).

Пример: ввод А - ввод значения переменной А с клавиатуры компьютера.

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

Пример: вывод Х - значение переменной Х выводится на экран.

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

 

Повторять

<тело цикла>

условие

до тех пор, пока не выполнится <условие>

 

Примеры

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

Решение. В алгебраической форме решение задачи выглядит следующим образом:

.

Исходными данными являются четыре целые величины: а, b, с, d. Результат - два целых числа m и n.

		алг деление дробей целa, b, c, m, n, d нач ввод a, b, c, d m:= a´d n:= b´c вывод “Числитель=”, m вывод “Знаменатель=”, n кон

 

 

 

Тест: a = 3, b=4, c=5, d=6.

Результат: m = 18, n = 20.

 

Пример 2. Даны две переменные величины X и Y. Требуется произвести между ними обмен значениями. Обмен происходит через промежуточную переменную Z.

 

 

ввод X,Y

Z:=X

X:=Y

Y:=Z

вывод X, Y

Тест: x = 3, y = -7.

Результат: x = -7, y = 3.

 

 

 

 

Пример 3. Даны три вещественных числа А, В, С. Найти наибольшее среди них.

Решение.1 способ.

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

 

 

Тест: a = 3, b = 6, c = 2.

Результат: D = 6.

2 способ. Задача решена с помощью вложенных ветвлений.

 

 

Пример 4. Дано целое положительное число N. Вычислить факториал этого числа: N! = 1 * 2 * 3 *... * N

Решение. Задача решается c помощью циклического алгоритма. Составим два варианта алгоритма: цикла с параметром и с применением цикла с предусловием.

		алг Факториал 2 целF, N, R нач ввод N F:=1 дляRот1доN повторять нц F:=F´ R кц вывод “Факториал=”, F кон

 

Тест: N = 5.

Результат: факториал F = 120.

 

 

		алг Факториал 1 целF, N, R нач ввод N F:=1 R:=1 покаR£N,повторять нц F:=F´R R:=R+1 кц вывод “Факториал=”, F кон

 

 

 

 

 

Пример 5. вычислить значение функции Y = A = BX + CX² для изменяющимся с шагом 0,5.

Пример 6. Вычислить выборочное среднее С и выборочную дисперсию D случайной величины x по формулам

, , ,

(х₁, х₂, …, х₅₀ – выборочные значения случайной величины х).

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

 

		алг Сумма вещА, В, С нач А = 0 В = 0 для k от 1 до 50 повторять нц ввод х A:= A+x B:= B+x кц C:= A/50 B:=B/50 – C^2 вывод “значение С=”, С “значение В=”, В кон

 

Пример 7. Использование вложенных циклов на примере вычисления двойной суммы

где

А= - матрица или двумерный массив данных одного и того же типа

В = (b₁, b₂, b₃, …, b_k) – одномерный массив (вектор) данных одного и того же типа.

 

 

алг Массив вещВk, Ank, C цел k, n нач для k от 1 до 9 повторять нц ввод bk кц для k от 1 до 9 повторять для n от 1 до 8 повторять нц ввод Аnk кц С:=0 для n от 1 до 8 повторять нц для k от 1 до 9 повторять нц C:=C+Ank×B кц кц выводС кон

 

 

Варианты

Задание по лабораторной работе «Алгоритмы в блок-схемах»

Составить алгоритмы на уровне блок-схем решения задач 5.1., 5.2., 5.3., 5.4., 5.5., 5.6. Контроль решения задачи или тест или ожидаемый результат должен быть рассмотрен и подготовлен до решения задачи с помощью ЭВМ. Номер варианта указывает преподаватель.

Задачи на линейный алгоритм

5.1.1. Вычислить объем конуса и площадь основания. Даны радиус основания R и высота конуса H. (V= ).

5.1.2. Вычислить радиус вписанного в треугольник круга по сторонам треугольника.

, где .

5.1.3. Даны два числа. Найти их сумму, произведение и разность.

5.1.4. Дано t. Камень бросили в колодец, и через t секунд послышался всплеск воды. На какой глубине (от сруба) вода в колодце. (h= g*t²/2)

5.1.5.Составить программу вычисления площади треугольника по его трем углам A, B, C и стороне a.
.

5.1.6.Вычислить площадь поверхности цилиндра по радиусу основания R и высоте цилиндра H. .

5.1.7.Дана сторона куба. Вычислить объем куба и полную поверхность.

5.1.8.Даны площадь треугольника S и стороны a, b, c. Вычислить сумму его высот.

5.1.9.Вычислить радиус описанного круга по сторонам треугольника.
, где .

5.1.10.Вычислить площадь трапеции по ее основаниям и высоте. .

5.1.11.Длины сторон первого прямоугольника a и b, его площадь в 6 раз меньше площади второго прямоугольника. Найти длину стороны второго прямоугольника, если длина одной из его сторон равна c.

5.1.12.Составить алгоритм вычисления площади треугольник со сторонами a, b, c (а, b, c - вещественные положительные числа).

5.1.13.Длина стороны треугольника равна a, периметр равен Р, длины двух других сторон равны между собой. Найти эти длины.

5.1.14.Периметр треугольника рaвен Р, длина одной стороны равна a, другой - b. Найти длину третьей cтоpоны.

5.1.15.Найти полную поверхность конуса с высотой H и радиусом основания R .

Задачи на разветвление

5.2.1. Написать алгоритм нахождения максимального среди четы­рех целых чисел.

5.2.2. Написать алгоритм проверки условия: имеются ли среди трех целых чисел два положительных числа?

5.2.3. Написать алгоритм проверки условия: могут ли три данных числа быть длинами сторон треугольника?

5.2.4. Написать алгоритм проверки условия: лежит ли данная точка c координатами (х, у) в первой четверти координатной плос­кости?

5.2.5. Проверить принадлежность числа x интервалам [а,b] или [c,d].

5.2.6. Проверить, является ли четырехугольник со сторонам a, b, c, d ромбом.

5.2.7. Определить, является ли треугольник со сторонами а, b, c равнобедренным.

5.2.8. Определить, является ли треугольник со сторонами а, b, c равносторонним.

5.2.9. Среди чисел а, b, с определить количество отрицательных.

5.2.10. Среди чисел а, b, с определить количество положительных.

5.2.11. Числа а и b - катеты одного треугольника, с и d - катеты другого. Определить являются ли эти треугольники равновеликими.

5.2.12. Определить, принадлежит ли заданная точка (х,у) плоской фигуре, являющейся кольцом с центром в начале координат, с внутренним радиусом r1 и внешним радиусом r2.

5.2.13. Какая площадь больше - параллелограмма со сторонами а, b и углом между ними 30° или площадь прямоугольника со сторонами n, m?

5.2.14. Выбрать среди данных четырех чисел a, b, c, d те, которые принадлежат интервалу (m, n).

5.2.15. Сколько чисел среди а, b, c, d принадлежит отрезку [m, n].

Задачи на двумерные массивы

 

5.6.1. Дана действительная матрица размера m*n. Найти сумму наибольших значений элементов ее строк.

5.6.2. Дана действительная матрица размера m*n. Найти сумму наибольших значений элементов ее столбцов.

5.6.3. В данной квадратной матрице порядка n найти сумму элементов строки, в которой расположен элемент с наименьшим значением. Предполагается, что такой элемент единственный.

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

5.6.5. Дана целочисленная квадратная матрица порядка n. Найти номера строк, все элементы которых – нули.

5.6.6. Дана целочисленная квадратная матрица порядка n. Найти номера строк, элементы в каждой из которых одинаковы.

5.6.7. Дана целочисленная квадратная матрица порядка n. Найти номера строк, все элементы которых – четны.

5.6.8. Дана действительная квадратная матрица порядка n. Создать массив номеров столбцов с отрицательными элементами на главной диагонали.

5.6.9. Дана действительная квадратная матрица порядка n. Создать массив номеров строк с отрицательными элементами на главной диагонали.

5.6.10. Дана действительная матрица размера m*n. Найти среднее арифметическое наибольшего и наименьшего значений ее элементов.

5.6.11. Дана целочисленная квадратная матрица порядка n. Выяснить, имеются ли в матрице ненулевые элементы, и если имеются, то указать номера этих элементов.

5.6.12. Дана целочисленная матрица порядка m*n. Найти матрицу, получающуюся из данной перестановкой столбцов – первого с последним.

5.6.13. Дана действительная матрица размера m*n. Найти произведение наибольших значений элементов ее строк, если они не нулевые.

5.6.14. Дана действительная матрица размера m*m. Найти разность наибольших значений элементов ее столбцов и соответствующих этим столбцам диагональных элементов.

5.6.15. В данной квадратной матрице порядка n найти сумму элементов строки, в которой расположен элемент со значением, принадлежащим интервалу (1; 5). Предполагается, что такой элемент единственный.

Список ЛИТЕРАТУРы

 

1. Информатика: Базовый курс: Учебник для вузов / Под ред. С. В. Симоновича. – СПб.: Питер, 2003. С 640.

2. Угринович Н. Информатика и информационные технологии. М.: Бином, Лаборатория знаний, 2003. С.512.

3. Семакин И.Г., Вараксин Г. С. Информатика. Структурированный конспект базового курса. М.: Лаборатория базовых знаний, 2004. С.168.

4. Семакин И.Г., Хеннер Е. Информатика: Задачник – практикум. Т.1. М.: Лаборатория базовых знаний, 2002. С.304.

5. ГОСТ 19.002-80. Единая система программной документации. Схемы алгоритмов и программ. Правила выполнения.

6. ГОСТ 19.003-80. Единая система программной документации. Схемы алгоритмов и программ. Обозначения условные графические.

 

содержание

 

 

Введение. 3

Алгоритм и его свойства. 3

1. Фрагменты ГОСТ 19.002-80. 5

1.1. Правила выполнения схем. 5

1.2. Правила применения символов. 7

2. Фрагменты ГОСТ 19.003-80. 11

2.1. Перечень, наименование, обозначение символов и отображаемые ими функции 11

2.2. Соотношение геометрических элементов символов. 14

3. основные типы алгоритмических структур. 15

3.1. Линейный алгоритм. 15

3.2. Алгоритмическая структура «Ветвление». 15

3.3. Алгоритмическая структура «Выбор». 17

3.4. Алгоритмическая структура «Цикл». 17

4. Примеры.. 19

5. Варианты.. 28