 |
Основные алгоритмические конструкции
|
|
|
|
ИНФОРМАТИТКА
Методические указания
по лабораторной работе N1
Алгоритмы
г. Могилев 2016
Лабораторная работа разработана доцентом К.В. Овсянниковым
БЕЛОРУССКО-РОССИЙСКИЙ УНИВЕРСИТЕТ
Содержание
1 Цель работы...................................................................................................................................... 4
2 Ход работы........................................................................................................................................ 5
2.1 Получение индивидуального задания.................................................................................... 5
2.2 Оформление отчета................................................................................................................... 5
3 Содержание отчета........................................................................................................................... 6
4 Краткие теоретические сведения................................................................................................... 7
4.1 Алгоритмизация........................................................................................................................ 7
4.2 Пример алгоритма................................................................................................................... 12
5. Задания........................................................................................................................................... 14
6 Контрольные вопросы................................................................................................................... 16
Литература......................................................................................................................................... 17
Цель работы
Целью лабораторной работы является:
1) программирование базовых конструкций алгоритмов;
2) получение практических навыков по работе с алгоритмами.
Ход работы
Получение индивидуального задания
Вначале следует получить индивидуальное задание у преподавателя, проводящего лабораторную работу. Варианты заданий приводятся в разделе 5.
Оформление отчета
Отчет оформляется индивидуально каждым студентом.
|
|
|
Содержание отчета
Отчет по лабораторной работе выполняется на листах формата А4. В состав отчета входят:
1) титульный лист;
2) цель работы;
3) текст индивидуального задания;
4) выполнение индивидуального задания.
Краткие теоретические сведения
Алгоритмизация
Происхождение понятия алгоритма связано с именем великого среднеазиатского ученого Аль Хорезми, жившего в 9 веке н. э. Им были сформулированы впервые правила выполнения четырех арифметических действий.
Алгоритм – это точная инструкция, а инструкции встречаются во всех областях человеческой деятельности. Однако не всякую инструкцию можно назвать алгоритмом. Алгоритм применяется к искомому набору исходных величин, называемых аргументами.
Цель исполнения алгоритма – получение определенного результата, если в результате исполнения алгоритма не достигнута определенная цель, значит алгоритм либо неверен, либо не завершен.
Алгоритм – это метод (способ) решения задачи, записанный по определенным правилам, обеспечивающим однозначность его понимания и механического исполнения при всех значениях исходных данных за конечное число шагов.
Или более коротко: алгоритм – это строго определенная последовательность действий, необходимых для решения данной задачи.
Примером алгоритма может служить кулинарный рецепт приготовления блюда. Рассмотрим простейший алгоритм – алгоритм заварки чая:
1) Подготовить исходные величины – чай, воду, чайник, стакан, ложку.
2) Налить в чайник воду.
3) Довести воду до кипения и снять с огня.
4) Всыпать в чайник чай.
5) Довести воду до кипения (но не кипятить), снять с огня.
6) Чай готов. Процесс прекратить.
Основными свойствами алгоритмов являются:
1 Универсальность (массовость) – применимость алгоритма к различным наборам исходных данных.
|
|
|
2 Дискретность – процесс решения задачи по алгоритму разбит на отдельные действия.
3 Однозначность – правила и порядок выполнения действий алгоритма имеют единственное толкование.
4 Конечность – каждое из действий и весь алгоритм в целом обязательно завершаются.
5 Результативность – по завершении выполнения алгоритма обязательно получается конечный результат.
6 Выполнимость – результата алгоритма достигается за конечное число шагов.
Алгоритм считается правильным, если его выполнение дает правильный результат.
Выделяют три крупных класса алгоритмов:
· вычислительные алгоритмы – работающие с числами и матрицами, хотя сам процесс вычисления может быть долгим и сложным;
· информационные алгоритмы – работающих с большими объемами информации (алгоритмы баз данных);
· управляющие алгоритмы, генерирующие различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми алгоритмы управляют.
Способы записи алгоритмов
Для записи алгоритмов используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма. Выделяют следующие основные способы записи алгоритмов:
· вербальный, когда алгоритм описывается на человеческом языке;
· символьный, когда алгоритм описывается с помощью набора символов;
· графический, когда алгоритм описывается с помощью набора графических изображений.
Общепринятыми способами записи являются графическая запись с помощью блок-схем и символьная запись с помощью какого-либо алгоритмического языка.
Описание алгоритма с помощью блок схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Ниже приводятся изображения символов схемы программы по ГОСТ 19.701-90. Внешний вид основных блоков, применяемых при написании блок схем, приведен в таблице 4.1.
Таблица 4.1 – Графические изображения элементов схем алгоритмов
| № п/п | Изображение | Наименование этапа |
| Символ «Процесс» Он предназначен для изображения вычислительного действия или последовательности вычислительных действий, которые указываются внутри блока | |
| Символ «Решение». Предназначен для проверки условия и передачи управления в соответствии с ним. Внутри блока должен быть указан вопрос, решение, условие или сравнение. | |
| Символ «Терминатор» | |
| Символ «Данные (ввод/вывод)» | |
| Символ предопределенного процесса (вызова подпрограммы) | |
| Символ «Подготовка (модификация)» | |
| Символы «Границы цикла» | |
| Символ «Соединитель» | |
| Символ «Комментарий» |
Основные алгоритмические конструкции
|
|
|
· Линейный алгоритм.
· Разветвляющийся алгоритм.
· Циклический алгоритм.
· Вспомогательный алгоритм.
Линейный алгоритм – алгоритм или фрагмент алгоритма, в котором порядок исполнения инструкций соответствует порядку их записи.
Инструкции линейного алгоритма выполняются последовательно одна за другой в порядке их записи. Блок-схему линейного алгоритма обычно представляют в виде блок-символов, соединенных последовательно. В каждый блок-символ входит не более одной линии потока информации. Из каждого блок-символа выходит не более одной линии потока информации. Обычно блок-схему размещают таким образом, что блок-символы размещаются один под другим, и нет необходимости обозначать линии потока информации стрелками.
Допускается изображать линейный алгоритм горизонтально или в виде изгибающейся под прямыми углами цепочки блок – символов. В этом случае линии потока информации, идущие снизу вверх и справа налево, следует изображать в виде стрелок.
Линейный фрагмент имеет любой алгоритм. В алгоритме «Кипячение воды» можно выделить два линейных фрагмента.
Рисунок 4.1 – Линейные фрагменты алгоритма «Кипячение воды»
Разветвляющийся алгоритм – алгоритм или фрагмент алгоритма, в котором порядок исполнения инструкций не определен изначально, имеет не менее двух вероятных направлений, каждое из которых соответствует одному из возможных исходов проверки логического условия.
Своим ветвлением разветвляющийся алгоритм обязан логическому условию, проверка которого на истинность обязательно приводит к возможности реализации одного из двух взаимоисключающих исходов. Линии потока информации, выходящие из блока «Решение», могут быть отмечены парами противоположных по смыслу знаками:
|
|
|
Таблица 4.2 – Знаки и символы, используемые в алгоритмах
| «да», «нет»; «+», «–»; «1», «0». | Условие истинно: «да», «+», «1». Условие ложно: «нет», «–», «0. |
Таблица 4.3 – Стандартное ветвление имеет два вероятных направления
| 
|
| Стандартное ветвление | Двухуровневое ветвление |
В то же время, комбинируя проверку нескольких логических условий, можно получить многоуровневое ветвление с тремя и более вероятными направлениями.
Обычно ветвление является фрагментом более сложного алгоритма. На рисунке представлен фрагмент алгоритма «Кипячение воды».
Рисунок 4.2 –Фрагмент разветвляющегося алгоритма
Циклический алгоритм – фрагмент алгоритма с ветвлением, в котором инструкция или группа инструкций исполняются более одного раза, т. е. повторяются.
Тело цикла – группа повторяющихся инструкций.
Основой циклического алгоритма является повторение инструкции или группы инструкций – тела цикла. Начало и завершение повторения тела цикла определяется итогом проверки логического условия.
Как правило, циклический алгоритм является фрагментом более сложного алгоритма. На рисунке 1 таблицы 10 представлен фрагмент алгоритма «Кипячение воды». Инструкция «Ждите 1 мин» является телом цикла и будет повторятся до тех пор, пока вода не закипит.
Циклический алгоритм имеет две базовые структуры – цикл с постусловием и цикл с предусловием.
Циклический алгоритм с постусловием (таблица 10, рисунок 2) характеризуется тем, что проверка условия расположена после тела цикла (лат. post – после).
Таблица 4.4 – Базовые структуры циклических алгоритмов
| 
| 
|
| Рисунок 1 –Циклический фрагмент алгоритма «Кипячение воды» | Рисунок 2 – Циклический алгоритм с постусловием | Рисунок 3 – Циклический алгоритм предусловием |
Циклический алгоритм с предусловием характеризуется тем, что проверка условия расположена перед телом цикла (Таблица 4.4, рисунок 3).
Вспомогательный алгоритм – функционально независимый алгоритм, к которому алгоритм более высокого уровня может обращаться произвольное количество раз.
В программировании вспомогательный алгоритм именуется «подпрограмма». В результате более чем полувековой мировой практики программирования созданы разнообразные вспомогательные алгоритмы, которые позволяют решать большинство стандартных задач программирования. Практически каждый язык программирования имеет обширную библиотеку подпрограмм, с помощью которой можно решать сложные алгоритмические задачи намного быстрее и проще.
|
|
|
Пример алгоритма
Образец составления алгоритма решения квадратного уравнения ax2+bx + c =0
Рисунок 4.3 –Пример составления алгоритма
Задания
Задание 1.
Составить блок-схему алгоритма решения задачи с условным переходом. Необходимо рассчитать значение искомой переменной по одному из двух альтернативных выражений в зависимости от значения переменной условия, значение которого необходимо предварительно вычислить согласно заданию. Значения переменной условия и переменной результата должны выводиться на экран.
Исходные данные к заданию находятся в таблице 5.1.
Таблица 5.1 - Индивидуальные задания
Задание 2.
Составить блок-схему алгоритма решения циклической задачи вычисления значения функции в зависимости от значения переменной аргумента. Значения переменной аргумента должны изменяться от начального до конечного значения с заданным шагом изменения. Исходные данные к заданию находятся в таблице 5.2.
Таблица 5.2 - Индивидуальные задания
Задание 3.
Составить блок-схему алгоритма решения нижеприведенной задачи
1. Даны три целых числа. Найти количество положительных чисел в исходном наборе.
2. Даны три целых числа. Найти количество положительных и количество отрицательных чисел в исходном наборе.
3. Даны две переменные вещественного типа: A, B. Перераспределить значения данных переменных так, чтобы в A оказалось меньшее из значений, а в B — большее. Вывести новые значения переменных A и B.
4. Даны две переменные целого типа: A и B. Если их значения не равны, то присвоить каждой переменной сумму этих значений, а если равны, то присвоить переменным нулевые значения. Вывести новые значения переменных A и B.
5. Даны две переменные целого типа: A и B. Если их значения не равны, то присвоить каждой переменной большее из этих значений, а если равны, то присвоить переменным нулевые значения. Вывести новые значения переменных A и B.
6. Даны три числа. Найти наименьшее из них.
7. Даны три числа. Найти среднее из них (то есть число, расположенное между наименьшим и наибольшим).
8. Даны три числа. Вывести вначале наименьшее, а затем наибольшее из данных чисел.
9. Даны три числа. Найти сумму двух наибольших из них.
10. Даны три переменные вещественного типа: A, B, C. Если их значения упорядочены по возрастанию, то удвоить их; в противном случае заменить значение каждой переменной на противоположное. Вывести новые значения переменных A, B, C.
11. Даны три переменные вещественного типа: A, B, C. Если их значения упорядочены по возрастанию или убыванию, то удвоить их; в противном случае заменить значение каждой переменной на противоположное. Вывести новые значения переменных A, B, C.
12. Даны три целых числа, одно из которых отлично от двух других, равных между собой. Определить порядковый номер числа, отличного от остальных.
13. Даны четыре целых числа, одно из которых отлично от трех других, равных между собой. Определить порядковый номер числа, отличного от остальных.
14. На числовой оси расположены три точки: A, B, C. Определить, какая из двух последних точек (B или C) расположена ближе к A, и вывести эту точку и ее расстояние от точки A.
15. Даны целочисленные координаты точки на плоскости. Если точка совпадает с началом координат, то вывести 0. Если точка не совпадает с началом координат, но лежит на оси OX или OY, то вывести соответственно 1 или 2. Если точка не лежит на координатных осях, то вывести 3.
16. Даны координаты точки, не лежащей на координатных осях OX и OY. Определить номер координатной четверти, в которой находится данная точка.
17. Даны целочисленные координаты трех вершин прямоугольника, стороны которого параллельны координатным осям. Найти координаты его четвертой вершины.
18. Дан номер года (положительное целое число). Определить количество дней в этом году, учитывая, что обычный год насчитывает 365 дней, а високосный - 366 дней. Високосным считается год, делящийся на 4, за исключением тех годов, которые делятся на 100 и не делятся на 400 (например, годы 300, 1300 и 1900 не являются високосными, а 1200 и 2000 - являются).
19. Дано целое число. Вывести его строку-описание вида «отрицательное четное число», «нулевое число», «положительное нечетное число» и т. д.
20. Дано целое число, лежащее в диапазоне 1-999. Вывести его строку-описание вида «четное двузначное число», «нечетное трехзначное число» и т.д.
Задание 4.
Составить блок-схему алгоритма решения нижеприведенной задачи
1. Дано целое число N (> 0). Найти сумму 1 + 1/2 + 1/3 +... + 1/N
2. Дано целое число N > 0. Найти сумму N2 + (N + 1)2 + (N + 2)2 +... + (2•N)2
3. Дано целое число N > 0. Найти произведение 1*2*3...
4. Дано целое число N > 0. Найти значение выражения 1.1 - 1.2 + 1.3 -... (N слагаемых, знаки чередуются).
5. Дано вещественное число A и целое число N >0. Найти A в степени N (числа A перемножаются N раз).
6. Дано вещественное число A и целое число N (> 0). Найти сумму 1+A+A2+A3 +...+AN.
7. Дано вещественное число A и целое число N > 0. Найти значение выражения 1-A+A2-A3 +... + (-1)NAN.
8. Дано целое число N > 0. Найти произведение N! = 1*2*...*N (N-факториал). Чтобы избежать целочисленного переполнения, вычислять это произведение с помощью вещественной переменной и вывести его как вещественное число.
9. Дано целое число N > 0. Найти сумму 1! +2! + 3! +...+N! (выражение N! - N-факториал - обозначает произведение всех целых чисел от 1 до N). Чтобы избежать целочисленного переполнения, проводить вычисления с помощью вещественных переменных и вывести результат как вещественное число.
10. Дано целое число N > 0. Найти сумму 1 + 1/(1!) + 1/(2!) + 1/(3!) +... + 1/(N!) (выражение N! — N–факториал — обозначает произведение всех целых чисел от 1 до N). Полученное число является приближенным значением константы e.
11. Дано вещественное число X и целое число N > 0. Найти значение выражения 1 + X + X2/(2!) +... + XN/(N!) (N! = 1•2•...•N). Полученное число является приближенным значением функции exp в точке X.
12. Дано вещественное число X (|X|<1) и целое число N > 0. Найти значение выражения X - X2/2 + X3/3 -... + (-1)N-1•XN/N. Полученное число является приближенным значением функции ln в точке 1+X.
13. Дано вещественное число X (|X|<1) и целое число N > 0. Найти значение выражения X - X3/3 + X5/5 -... + (-1)N•X2N+1/(2•N+1). Полученное число является приближенным значением функции arctg в точке X.
14. Дано целое число N (> 1) и две вещественные точки на числовой оси: A, B (A < B). Отрезок [A, B] разбит на N равных отрезков. Вывести H - длину каждого отрезка, а также набор точек A, A+H, A+2H, A+3H,..., B, образующий разбиение отрезка [A,B].
15. Дано целое число N > 1 и две вещественные точки на числовой оси: A, B (A < B). Отрезок [A, B] разбит на N равных отрезков. Вывести H - длину отрезка, а также значения функции F(X) = 1 - sin(X) в точках, разбивающих отрезок [A,B]: F(A), F(A+H), F(A+2H),..., F(B).
16. Дано целое число N > 1. Найти наименьшее целое число K, при котором выполняется неравенство 3к > N.
17. Дано целое число N > 1. Найти наибольшее целое число K, при котором выполняется неравенство 3к < N.
18. Дано целое число N > 1. Вывести наименьшее из целых чисел K, для которых сумма 1 + 2 +... + K будет больше или равна N, и саму эту сумму.
19. Дано число A > 1. Вывести наименьшее из целых чисел K, для которых сумма 1 + 1/2 +... + 1/ K будет больше A, и саму эту сумму.
20. Начальный вклад в банке равен 1000 руб. Через каждый месяц размер вклада увеличивается на P процентов от имеющейся суммы (P — вещественное число, 0<P<25). По данному P определить, через сколько месяцев размер вклада превысит 1100 руб., и вывести найденное количество месяцев K (целое число) и итоговый размер вклада S (вещественное число).
6 Контрольные вопросы
1. Кто и когда впервые ввел понятие алгоритма?
2. Каковы способы записи алгоритмов?
3. В чем заключаются основные свойства алгоритма?
4. Перечислите основные алгоритмические структуры и опишите их.
5. Каковы основные принципы разработки алгоритмов?
6. Чем объясняется разнообразие форм записи алгоритмов?
7. Охарактеризуйте словесно-пошаговый способ записи алгоритмов.
8. Охарактеризуйте табличную форму записи алгоритмов.
9. Что такое результат выполнения алгоритма?
10. Что такое исходные данные?
11. Что представляет собой графическая форма записи алгоритма?
12. Каков порядок составления блок-схем?
13. Охарактеризуйте основные блоки блок схем.
14. Для чего необходимо ветвление в алгоритмах?
15. Какие формы ветвления различают?
16. Для чего используют структуру «цикл»?
17. Какие виды циклов вы знаете?
18. Что такое тело цикла?
Литература
1. Аветисян Р. Д., Аветисян Д. В. Теоретические основы информатики. — М.: РГГУ, 1997.
2. Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: В 2 ч. 4.2: Пер. с нем. — М.: Мир, 1990.
3. Информатика в понятиях и терминах. — М.: Просвещение, 1991.
4. Информатика. Энциклопедический словарь для начинающих. — М.: Педагогика-Пресс, 1994.
5. Основы информатики и вычислительной техники / А. Г. Гейн, В. Г.Житомирский, Е.В.Линецкий и др. — М.: Просвещение, 1991.
6. Веретенникова Е.Г. и др. Информатика: Учебное пособие / Веретенникова Е.Г. и др.; Е. Г. Веретенникова, С. М. Патрушина, Н. Г. Савельева. - Ростов н/Д.: Изд-кий центр "Март", 2002. - 416с.
7. Королев Л. Н. Информатика. Введение в компьютерные науки: Учебник / Л. Н. Королев, А. И. Миков; Л. Н. Королев, А. И. Миков. - М.: Высш. шк., 2003. - 341с.
8. Симонович С. В. Общая информатика: Учебное пособие / С. В. Симонович, Г. А. Евсеев, А. Г. Алексеев. - М.: АСТ- ПРЕСС КНИГА, 2004. - 592с.
9. Информатика. Базовый курс: Под ред. Симановича С. В. - 2-е изд. - СПб.: Питер, 2006. - 640с.
10. Алексеев А. П. Информатика 2007 / А. П. Алексеев. - М.: Солон-Пресс, 2007. - 608с. 2 экз.
11. Степанов А.Н. Информатика: Учебное пособие / А. Н. Степанов. - СПб.: Питер, 2002. - 608с.
12. Острейковский В. А. Информатика: Учебник / В. А. Острейковский. - 3-е изд., стер. - М.: Высшая школа, 2005. - 511с.
13. Конев Ф. Б. Информатика для инженеров: Учебное пособие / Ф. Б. Конев. - М.: Высшая школа, 2004. - 272с.ц
|
|
|
