Лабораторная работа № 2. Ветвящиеся алгоритмы

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

Логические выражения состоят из логических констант, переменных и отношений, соединенных логическими операциями. В простейших случаях в операторах используют отношения: два выражения, соединенных знаком отношения (<, >, >=, <=, =, <>), например I > 20. Но иногда возникают условия, требующие использования более сложных логических выражений.

Пример. На плоскости задана фигура (рис.5.1.): усеченный круг. Вводится точка с координатами X,Y. Определить, принадлежит введенная точка фигуре или нет. В результате выводится: «Введенная точка принадлежит фигуре» или «Введенная точка фигуре не принадлежит».

Рис.5.1. Пример фигуры.

Для определения вхождения точки в круг можно использовать формулу окружности:

Соответственно изменив знак = на < (или <= – всё равно, так как на границах фигуры точки не проверяются) получим условие вхождения точки в круг c координатами центра (3,3) и радиусом 3:

Кроме этого область, занятая треугольником, так же не входит в закрашенную область, то есть полуплоскость над прямой Y = –X+7 фигуре не принадлежит. Условия нахождения точки внутри круга и под прямой должны выполняться одновременно. Для этого необходимо использовать логическую операцию AND.

Таким образом, логическое выражение

примет истинное значение, если точка входит в закрашенную область, иначе ложное. Тогда в логическом операторе по прямой ветви Then выводится «Введенная точка принадлежит фигуре», а по ветви Else «Введенная точка фигуре не принадлежит».

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

При выполнении лабораторной работы составить два варианта программы (без использования операции NOT) для фигуры, соответствующей варианту задания, которые приведены в табл.5.1.

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

Таблица 5.1. Варианты заданий.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. 16.

17. 18.

19. 20.

21. 22.

23. 24.

25. 26.

27. 28.

29. 30.

Лабораторная работа № 3.
Циклы с известным числом повторений

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

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

Пример: составить программу, вычисляющую значение суммы:

Прежде чем вычислять выражение под знаком суммы и очередную частичную сумму, необходимо определить начальное значение параметра цикла (в данном случае i, которое изменяется от 1 до 10 с шагом 1, то есть i будет принимать последовательно значения 1, 2, 3, 4, ..., 9, 10), и начальную частичную сумму S. Так как вычисления еще не производились, то S = 0.

Затем вычисляется выражение под знаком суммы для i = 1, затем i = 2, 3, ... до 10 и каждый раз складывается с предыдущей частичной суммой S _i-1. При этом получается новая частичная сумма S _i. После этого i увеличивается на единицу и проверяется, не стало ли i > 10. Если еще меньше или равно 10, то вычисляется новая частичная сумма, в противном случае вычисление суммы будет закончено, и это значение выводится на печать.

Воспользуемся стандартной схемой циклического процесса, представленной на рис.6.1.

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

В блоке 2 производится вычисление выражения, стоящего под знаком суммы и сложение с предыдущей частичной суммой S _i-1. В итоге получается новая частичная сумма S _i.

В блоке 3 происходит изменение параметра цикла (увеличение i на 1). Это блок подготовки к новому циклу.

Блок 4 – блок проверки окончания цикла. Необходимо проверить, стало ли i больше 10. Если стало, то цикл закончен, следующим должен выполняться блок печати. Если нет, то вычисление частичной суммы продолжается дальше, то есть выполняются блоки 2 и 3.

Проверка может осуществляться условным оператором IF, но для организации циклов в языке Паскаль специально предусмотрены три оператора цикла. Если количество повторений заранее известно, и параметр является целым числом, то целесообразно использовать оператор FOR, включающий в себя блоки 1, 3, 4. В этом случае в алгоритме можно применить блок «Модификация».

Алгоритм для примера с использованием оператора FOR приведен на рис.6.2. Варианты заданий – в табл.6.1.

Рис. 6.1. Блок-схема алгоритма циклического процесса

Рис. 6.2. Блок-схема алгоритма примера.

Таблица 6.1. Варианты заданий

№ вар.	Вычислить сумму	№ вар.	Вычислить сумму
№ вар.	Вычислить сумму	№ вар.	Вычислить сумму

Лабораторная работа № 4.
Циклы с заранее неизвестным числом повторений

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

Проверка цикла осуществляется следующим образом. Так как выражение под знаком суммы постепенно убывает с ростом слагаемых в сумме (условие сходимости), то наступает момент, когда очередное слагаемое станет меньше наперед заданного числа e (грубо говоря, точности вычисления сумм), и остальные слагаемые будут мало влиять на конечный результат. Поэтому, когда выражение под знаком суммы | f (i) | будет меньше e, то вычисления прекращаются и предполагается, что сумма найдена с заданной точностью.

Так как количество слагаемых заранее неизвестно, то циклом FOR пользоваться нельзя. Для этих целей предназначаются циклические операторы WHILE и REPEAT. Необходимо помнить, что у этих операторов параметр цикла автоматически не изменяется, и его надо менять принудительно. Поэтому при составлении блок-схемы алгоритма блок «Модификация» не используется.

При вычислении суммы должен вычисляться факториал по формуле:

Где П – знак произведения (аналогично знаку суммы), то есть 5! = 1· 2· 3· 4· 5 = 120. Факториал можно вычислить отдельным циклом, а можно и в цикле вычисления суммы. Для этого вводится дополнительная переменная, например f = j !, и затем в цикле умножается на текущее значение j.

Кроме значения суммы на печать полезно вывести значение счетчика циклов, то есть узнать, из скольких слагаемых состоит сумма.

Варианты заданий приведены в табл.7.1.

Примечание. В языке Турбо Паскаль под переменные типа INTEGER выделяется два байта, и допустимые для них значения находятся в диапазоне только от -32768 до 32767. Поэтому число 10!, реально равное 3628800, в этом случае будет представлено как 24320. Таким образом, выражение под знаком суммы может никогда и не стать меньше заданной точности. Для работы с большими целыми числами рекомендуется использовать вещественный тип REAL с диапазоном представления от 2.9·10^-39 до 1.7·10³⁸, или, в крайнем случае, целый тип LongInt с диапазоном от ‑2.147.483.648 до 2.147.483.647.

Таблица 7.1. Варианты заданий

№ вар.	Вычислить	При х, равном	Точность вычислений e
		0,149	10 -5
		5,99	10 -3
		3,1	10 -4
		1,91	10 -5
		1,42	10 -3
		0,99	10 -4
		1,51	10 -5
		3,48	10 -3
		7,55	10 -4
		2,15	10 -5
		0,81	10 -3
№ вар.	Вычислить	При х, равном	Точность вычислений e
		0,77	10 -4
		3,95	10 -5
		1,62	10 -3
		4,14	10 -4
		1,24	10 -5
		3,3	10 -3
		2,8	10 -4
		0,95	10 -5
		4,5	10 -3
		0,85	10 -4
		2,4	10 -5
		1,7	10 -3
№ вар.	Вычислить	При Х, равном	Точность вычислений e
		4,2	10 -4
		2,2	10 -5
		3,1	10 -3
			10 -4
		8,5	10 -5
		0,15	10 -3
		2,9	10 -4

Лабораторная работа № 5.
Средства вывода. Таблицы

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

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

Макет таблицы рисуется на бумаге в клетку, и каждая клетка принимается за одну позицию. При этом учитывается, где расположена таблица, то есть, сколько позиций надо отступить от левого края листа, каким образом проводятся вертикальные и горизонтальные линии (обычно вертикальные – набор знаков I или !, горизонтальные – знаки минус или подчеркивание). Определяется ширина таблицы, которая зависит от количества выводимых значений и точности, с какой эти значения выводятся (длина числа зависит от количества цифр в числе). После этого, символ за символом, в операторы вывода заносится с макета информация о том, как должен выглядеть заголовок таблицы.

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

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

Все кодовые таблицы символов имеют и символы псевдографики. Это такие символы, как вертикальная черта, прямой угол, перекрестье и т.д., например: │, └, ┘, ║, ╬, ╙. Если знать сочетания клавиш для символов псевдографики, то изображение таблиц получается лучше. Но это требуется не всегда, например, для данной лабораторной работы достаточно знаков, таких, как латинское «I» большое или восклицательный знак «!», и тире «–» или символ подчеркивания «_».

Пример. Вывести таблицу значений функции с точностью 7 знаков после запятой, причем х изменяется от 2 до 9 с шагом 1.

Блок-схема алгоритма представлена на рис. 8.3, полученный результат на рис. 8.1, вариант результата – на рис. 8.2.

-------------------

I X I SQRT(X) I

-------------------

I 2 I 1.4142132 I

I 3 I 1.7320509 I

I 4 I 2.0000000 I

I 5 I 2.2360678 I

I 6 I 2.4494896 I

I 7 I 2.6457510 I

I 8 I 2.8284273 I

I 9 I 3.0000000 I

-------------------

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

┌─────┬───────────┐

│ Х │ SQRT(X) │

├─────┼───────────┤

│ 2 │ 1.4142132 │

│ 3 │ 1.7320509 │

│ 4 │ 2.0000000 │

│ 5 │ 2.2360678 │

│ 6 │ 2.4494896 │

│ 7 │ 2.6457510 │

│ 8 │ 2.8284273 │

│ 9 │ 3.0000000 │

└─────┴───────────┘

Рис 8.2. Вывод таблиц с использованием символов псевдографики.

Рис.8.3. Блок-схема алгоритма для примера.

Таблица 8.1. Варианты заданий

№ вар.	Функции	Начальное значение х	Конечное значение х	Шаг изменения х
		0,2	1,7	0,1
				0,05
				0,05
				0,5
				0,5
		0,1		0,1
				0,2
		0,1		0,05
		0,1		0,1
		0,05		0,05
		0,05		0,05
				0,05
				0,5
				0,05
		-1		0,1
		-2		0,2
№ вар.	Функции	Начальное значение х	Конечное значение х	Шаг изменения х
				0,2
				0,05
				0,05
		0,1		0,05
				0,1
				0,1
		0,1	1,5	0,1
				0,1
		0,5		0,25
				0,5
		1,05		0,05

Лабораторная работа № 6.
Двойные и кратные циклы

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

Пример: вычислить с точностью до 0.001.

Здесь внешней суммой является сумма по i, а внутренней – сумма по j. Можно рассматривать вычисление этих сумм отдельно, учитывая, что вычисление внутренней суммы является частью вычисления внешней суммы, то есть телом внешнего цикла. То есть цикл по i – внешний, по j – внутренний, находящийся целиком внутри текущего вычисления очередного слагаемого по i.

Варианты заданий приведены в табл.9.1.

Таблица 9.1. Варианты заданий

№ вар.	Вычислить	Точность вычислений e
		10 -3
		10 -4
		10 -3
		10 -4
		10 -3
		10 -4
		10 -3
		10 -4
		10 -3
		10 -4
№ вар.	Вычислить	Точность вычислений e
		10 -3
		10 -4
		10 -3
		10 -4
		10 -3
		10 -4
		10 -3
		10 -4
		10 -3
		10 -4
№ вар.	Вычислить	Точность вычислений e
		10 -3
		10 -4
		10 -3
		10 -4
		10 -3
		10 -4
		10 -3
		10 -4
		10 -3
		10 -4

Лабораторная работа № 7.
Сортировка массивов

Массивы, – упорядоченные по индексу элементы одинакового типа, – широко используются при составлении программ. Над элементами массивов можно производить различные операции, например сортировку.

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

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

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

Рассмотрим наиболее часто используемые простые методы сортировки массивов на примерах сортировки по возрастанию.