Схемы физической структуры данных. (для студентов специальности «Информационные управляющие системы»)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ, НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ

ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА АСУ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ И ЗАДАНИЯ

К ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ ПО

ВЫЧИСЛИТЕЛЬНОМУ ПРАКТИКУМУ

(для студентов специальности «Информационные управляющие системы»)

	Рассмотрено на заседании кафедры АСУ протокол № ___ от _________г.
	Утверждено на заседании научно- издательского совета ДонНТУ протокол № ___ от _________г.

– 2012 –

УДК 681.3.06

Методические указания к выполнению лабораторных работ по Вычислительному практикуму. /Сост.: Савкова Е.О., Поляков А.И., Теплова О.В.–Донецк: ДонНТУ – 2012, 28 с.

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

Составитель: Савкова Е.О.

Поляков А.И.

Теплова О.В.

Рецензент:

ВАРИАНТЫ ЗАДАНИЙ ПО ЛАБОРАТОРНЫМ РАБОТАМ

ПО ВЫЧИСЛИТЕЛЬНОМУ ПРАКТИКУМУ

Общие требования к оформлению лабораторных работ.

1. Титульный лист.

2. Задание и краткое пояснение по методу решения (если это необходимо).

3. Блок-схема алгоритма решения задачи.

4. Распечатка конечного варианта реализованной программы.

5. Распечатка результатов работы программы.

6. Анализ полученных результатов (контрольный ручной расчет).

При выполнении лабораторной непосредственно на занятиях возможен режим защиты выполненной работы непосредственно с экрана монитора, при этом в качестве отчета оформляется только пункты 1, 2 и 4.

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

Критерии оценки по дисциплине «Вычислительные практикум»:

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

«Отлично» - 8 работ;

«Хорошо» - 7 работ:

«Удовлетворительно» - 6 работ.

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

«Отлично» - 11 работ;

«Хорошо» - 9 работ:

«Удовлетворительно» - 8 работ.

При этом обязательно необходимо выполнить следующие работы: 3, 5, 9, 10, 11.

Лабораторная работа № 1.

Тема. Простейшие циклы.

Цель работы: Изучение приемов организации простейших циклов.

Задача.

Согласно приведенной ниже таблице вычислить требуемое выражение.

№ вар.	Вычисляемое выражение	Даны числа
Целые	Действительные
1.		n	x
2.		k	a
3.		п -нечетное	x
4.		n	x
5.		n	x
6.		n	x
7.		n	x
8.		n
9.		n	x
		n	x
11.		n	x
12.		n	a, b
13.		n	v, u
14.		n
15.		n
16.	Вычислить с точностью 0.00001	n
17.	Вычислить с точностью 0.00001	n
18.	Вычислить с точностью 0.00001		x
19.	Вычислить с точностью 0.00001		a, b
20.	Вычислить с точностью 0.00001		a, b
21.	Вычислить с точностью 0.00001		x
22.	Вычислить с точностью 0.00001		a, b
23.	Вычислить с точностью 0.00001		x, y
24.	Вычислить с точностью 0.00001
25.	Вычислить с точностью 0.00001

Лабораторная работа № 2.

Тема. Действия над векторами и матрицами.

Цель работы: практика в использовании возможностей АЯ для действий над массивами.

Задача.

1. Получить элементы квадратной матрицы размерностью не менее чем по заданной формуле.

2. Из полученной матрицы по заданному правилу получить компоненты вектора

3. Вычислить значения , где - заданная функция.

4. В качестве результата выдать на печать элементы матрицы А, вектора Х и значение U.

Правила получения вектора Х по матрице А:

1. i-ый элемент вектора Х – скалярное произведение i-ой строки матрицы А на i-ый столбец.

2. i-ый элемент вектора Х – скалярное произведение i-ой строки матрицы А на первый столбец.

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

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

5. Вектор Х – упорядоченные по убыванию средние арифметические значения элементов строк матрицы А.

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

7. В качестве элементов вектора Х принять разность между максимальным и минимальным элементами соответствующей строки матрицы А.

№	Функция формирования матрицы А
1.
2.
3.
4.
5.
6.
7.
8.

Лабораторная работа № 3.

Тема. Программирование итерационных циклов.

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

Задача.

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

Аргумент Х

Значение функции

Сумма (произведение)

Кол-во итераций

№	Вычислительная формула	Диапазон изменения аргумента	Шаг	Точ-ность	Функция
1.
2.
3.		[0.1;0.5]	0.05
4.
5.
6.
7.
8.
9.
10.
11.		[1;1.5]	0.025
12.		[0;1]	0.1
13.		[1;2]	0.1
14.		[0.1;1]	0.1
15.		[0;2]	0.1
16.		[0;1]	0.1
17.		[0;0.8]	0.04
18.
19.
20.		[-0.6;0.6]	0.1
21.		[0.1;1]	0.1
22.		[0;2]	0.1
23.
24.
25.		[0.1;0.5]	0.05

Лабораторная работа № 4.

Тема. Разработка программ с использованием функций.

Цель работы: изучение методов работы с функциями; приобретение навыков в программировании на АЯ, ориентированном на использование функций.

Задача.

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

1. В одномерных массивах X и Y найти минимальный положительный и максимальный отрицательный элементы и изменить их знак на противоположный. Определить как изменилось среднее арифметическое значение элементов массивов.

2. В матрице X размером NxM найти последнюю по порядку строку с минимальным количеством отрицательных элементов и перезаписать ее в обратном порядке.

3. В одномерных массивах Х и Y определить среднее арифметическое значение элементов и если оно больше значения N-1 –го элемента переставить элементы в обратном порядке.

4. В матрице размером NхМ определить такую подматрицу размером 3х3, сумма элементов главной диагонали которой максимальна.

5. В бинарной матрице размером NхN определить столбец, содержащий максимальное количество единиц. Бинарная – это матрица элементами которой являются либо 0, либо 1.

6. В матрице размером NхМ определить такую подматрицу размером 3х3, которая содержала бы максимальный (по значению) элемент матрицы и сумма элементов которой была бы минимальной.

7. В одномерных массивах Х и Y произвести циклический сдвиг элементов массивов на 2 позиции вправо, если отношения минимального элемента массива к максимальному по модулю больше 10 или на 4 позиции вправо в другом случае.

8. Заданы три одномерных массива различной размерности X, Y и Z определить массив у которого сумма элементов максимальна.

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

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

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

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

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

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

15. Для каждого столбца прямоугольной матрицы найти разность между максимальным и минимальным элементами данного столбца. Определить номер столбца содержащего элементы дающие минимальную разность.

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

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

18. Для каждой строки прямоугольной матрицы определить количество нарушений упорядоченности его элементов по возрастанию.

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

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

Лабораторная работа № 5.

Тема. Программирование задач аналитической геометрии.

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

Общие положения.

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

Центр тяжести множества материальных точек G в трехмерном пространстве:

G=(X_g, Y_g, Z_g) – имеет координаты:

; ; ;

где m_i – масса i-ой точки.

Расстояние между двумя точками и : .

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

Отклонение точки Р от прямой будет:

и если d<0, то точка Р находится справа от прямой, при d>0 – слева от прямой, при d=0 – лежит на прямой, а за направление прямой условно принимаем направление от точки к точке .

Расстояние от точки Р до прямой будет: .

Координаты точки Р пересечения двух прямых и :

; , где ; ; .

Точка Р лежит внутри треугольника АВС, если она находится по одну сторону от прямых АВ, ВС и СА.

Треугольник с длинами a, b, c {c=max(a, b, c))}, тогда:

- прямоугольный, если c²=a²+b²;

- остроугольный, если c²<a²+b²;

- тупоугольный, если c²>a²+b².

Варианты заданий.

1. Из заданного множества точек определить выбрать такие из которых можно построить остроугольный треугольник максимальной площади.

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

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

4. Из заданного множества точек на плоскости выбрать три различные точки так, чтобы внутри треугольника вершинами которого являются эти точки, содержалось максимальное количество точек из заданного множества.

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

6. На плоскости заданы множество точек А и точка D вне его. Подсчитать количество (неупорядоченых) различных троек точек a, b, c из А таких, что четырехугольник abcd является параллелограммом.

7. На плоскости заданы множество точек А и точка D вне его. Найти в А две такие точки a и b, чтобы треугольник abd имел максимальную площадь.

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

9. На плоскости заданы множество точек А и точка d вне его. Определить количество прямых, проходящих через две различные точки множества А и точку d.

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

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

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

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

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

15. В трехмерном пространстве задано множество материальных точек. Отсортировать это точки в порядке удаления их от центра тяжести этого множества.

Лабораторная работа № 6.

Тема. Решение задач сортировки и упорядочения.

Цель работы: практика в использовании алгоритмов сортировки при составлении программ на АЯ по упорядочению элементов массивов.

Задача.

№	Задания по упорядочению
1.	Упорядочить имеющийся массив действительных чисел по убыванию.
2.	Упорядочить имеющийся массив действительных чисел по возрастанию.
3.	В действительной матрице размера n x m упорядочить строки матрицы по возрастанию значений первых элементов.
4.	В действительной матрице размера n x m упорядочить строки матрицы по возрастанию сумм элементов строк.
5.	В упорядоченный массив действительных чисел вставить число b так, чтобы ненарушить последовательность.
6.	Из двух упорядоченных массивов получить единую упорядоченную последовательность.
7.	Из имеющегося массива действительных чисел по получить два упорядоченных по возрастанию массива, разделенных между собой средним арифметическим значением исходного массива.
8.	В действительной матрице размера n x m упорядочить строки по знаку элементов.
9.	В действительной матрице размера n x n упорядочить строки матрицы по возрастанию значений элементов ее главной диагонали.
10.	В действительной матрице размера n x m четные строки упорядочить по возрастанию элементов, а нечетные по убыванию.

Алгоритм сортировки

1. Выбором
2. Обменами
3. Вставками

Лабораторная работа № 7.

Тема. Решение задач по обработке строк и простейших структур данных.

Цель работы: изучение методов работы со строками и структурами данных; приобретение навыков в программировании на АЯ, ориентированном на обработку строк и структур.

Задача.

Разработать программу позволяющую осуществлять ввод строк с клавиатуры или считывание их из файла данных с выводом на экран, обработки в соответствии с приведенным ниже вариантом индивидуального задания и вывода результата на экран и в файл результатов. Рекомендуемое количество строк текста – 5-20. В каждой строке количество символов не должно превышать 80 (размер строки экрана в текстовом режиме). Для уменьшения количества исследуемых вариантов будем считать, что переносы слов с одной строки на другую не допускаются.

1.	Найти строку, содержащую слово максимального размера. И в ней слово минимального размера заменить на *.
2.	В тексте все во всех словах начинающихся на гласные буквы заменить начальные гласные буквы на !.
3.	Найти первую по порядку строку содержащую максимальное количество слов.
4.	По тексту заменить все гласные буквы на *. Подсчитать количество таких букв.
5.	Найти слово максимальной длины, начинающееся и заканчивающееся на гласную букву и в нем все буквы заменить на знак ‘?’.
6.	Ввести с клавиатуры несколько (от 3 до 5 букв) и определить сколько раз каждая буква встречается по тексту. Букву, которая наиболее часто встречается заменить в тексте на *.
7.	Найти последнюю по порядку строку содержащую минимальное количество слов.
8.	Найти максимальную по длине строку и удалить в ней слово, состоящее из наименьшего количества символов.
9.	В строке содержащей максимальное количество слов переставить слова в обратном порядке.
10.	В тексте найти наибольшее и наименьшее по длине слова и заменить их местами.
11.	Удалить из текста слово, содержащее наибольшее количество гласных.
12.	В словах начинающихся и заканчивающихся на одинаковые буквы, все гласные заменить на *.
13.	Найти среднюю длину слов и удалить из текста все слова длина, которых меньше найденного значения.
14.	Найти и переставить местами строки, в которых находятся слова с максимальной и минимальной длиной.
15.	В каждой строке слово с максимальной длиной заменить на его порядковый номер в этой строке.

16.	Определить количество строк в которых гласных букв больше 10, если количество таких строк больше двух, то первую и последнюю из них поменять местами.
17.	Подсчитать количество встречающихся в тексте знаков препинания. Если полученное число меньше 10, то все знаки препинания заменить на ‘!’, иначе – на ‘?’
18.	В строке с максимальным количеством слов найти самое длинное слово и переставить его буквы в обратном порядке.
19.	Удалить максимальное по длине слово и заменить все пробелы на ‘#’.
20.	Определить слово, в состав которого входит наибольшее количество гласных букв и заменить их на *.
21.	Найти слово с максимальным количеством букв и удалить из него все гласные буквы
22.	В тексте во всех четных строках слова переставить в обратном порядке, а не четных строках знаки препинания заменить на ‘#’.
23.	В каждой третьей строке максимальное слово заменить на число, соответствующее количеству входящих в нее букв.
24.	Определить максимальное по длине слово среди четных строк, и минимальное – среди нечетных и поменять их местами.
25.	Удалить из текста каждое четвертое слово. Подсчитать количество таких удалений.

Лабораторная работа № 8.

Тема. Обработка записей.

Цель работы: освоить способы реализации программ при решении задач с использованием структур и построение пользовательского интерфейса.

Общие положения.

Представление данных в виде структур применяется в основном при машинной обработке документов. Любой документ разделяется на три части: «шапка», колонки и строки. Каждая строка документа является записью, которая представляет собой единое целое и состоит из отдельных данных, называемых реквизитами. Реквизиты имеют различные форматы (числа вещественные или целые, литеры, строки и т.д.).

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

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

Использование кодификаторов при выполнении задания не обязательно.

Варианты заданий.

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

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

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

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

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

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

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

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

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

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

11. Имеется информация о ходе сессии по группам: факультет, группа, количество студентов в группе, количество экзаменов в сессию и количество студентов сдавших экзамены на «5», «4», «3» и «2» соответственно. Определить список из трех групп в которых максимальное в процентном отношении количество студентов не сдало экзамены.

12. Имеются списки жильцов дома составленные в следующем порядке: Номер квартиры, Ф.И.О., количество прописанных, числодетей, число комнат, общая площадь. Сформировать сведения о семьях имеющих 3-х и более детей. Сформировать списки перенаселенных квартир при указанной норме.

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

14. В справочном бюро содержаться сведения: Ф.И.О., год рождения, район, адрес, телефон, Сформировать список граждан младше 30 лет (списки разбить по районам). Определить трех старейших жителей города.

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

Лабораторная работа № 9.

Тема: Обработка симметричных и разреженных матриц с математическим описанием расположения элементов

Цель работы: получить практические навыки организации и обработки симметричных матриц.

Ход работы:

1. Для матриц с математическим описанием расположения элементов реализовать операции:

a. Преобразования индексов матрицы в индекс вектора

b. Получения значения элемента матрицы из ее упакованного представления по двум индексам

c. Записи значения элемента матрицы в ее упакованное представление по двум индексам

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

3. Реализовать алгоритм.

4. Подготовить отчет о выполнении работы.

Значения элементов матрицы генерируются случайным образом в диапазонах: для типов int и long [0,99], для double – [10.00, 99.99] с точностью до двух знаков после запятой.

Варианты матриц:

Симметричные квадратные матрицы (показана ось (оси) симметрии):

1. 2.

3. 4.

1

Симметричные прямоугольные матрицы (показана ось (оси) симметрии):

5. 6.

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

7. 8.

9. 10.

Треугольные матрицы (закрашены ненулевые элементы)

11. 12.

12. 14.

15. 16.

17. 18.

Схемы физической структуры данных

1. Одномерный массив для хранения не фоновых элементов;
2. Одномерный массив для хранения не фоновых элементов и вспомогательный массив размерностью количества строк матрицы для хранения номера первого не фонового элемента i-той строки в одномерном представлении.

Варианты обработки матриц: