Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Воронежский институт МВД России
Кафедра автоматизированных информационных систем
органов внутренних дел
УТВЕРЖДАЮ
Начальник кафедры АИС ОВД
полковник полиции
И.В. Атласов
« ___ » ____________ 2012 г.
и методические указания курсантам на лабораторное занятие
ТМ № 1 Тема 3: «Алгоритмические модели поиска и сортировки данных»
Разработал:
ст. преподаватель кафедры
АИС ОВД, майор полиции
В.В. Конобеевских
Обсуждено и одобрено
на заседании методической
секции кафедры АИС ОВД
Протокол № от « » 2012 г.
Обсуждено и одобрено
на заседании кафедры АИС ОВД
Протокол № от « » 2012 г.
Воронеж 2012
Тематический модуль № 1
Тема 3
Лабораторное занятие № 2 «Алгоритмы нахождения заданных элементов в двумерных числовых массивах»
Цели занятия:
Учебно-воспитательные:
Категория слушателей: 2 курс РТФ.
Время: 90 мин.
Место проведения: дисплейный класс.
Материально-техническое обеспечение:
1) персональный компьютер IBM PC, с операционной системой Windows;
2) текстовый процессор Microsoft Office Word 2003 и выше;
3) тестирующая программа tTester.
ПЛАН ЗАНЯТИЯ
|
Учебные вопросы |
Время, мин |
|
Вступительная часть . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1. Алгоритмы обработки двумерных числовых массивов . . . . 2. Выполнение индивидуального задания . . . . . . . . . . . . . . . . . . Заключительная часть…………………………………………….. |
5 20 50 15 |
Литература:
основная:
дополнительная:
3. Информатика. Ч. I. Технические и программные средства реализации информационных процессов: курс лекций [Текст] / Авт.-сост. С. А. Мишин, О. И. Каляпина. – Воронеж: Воронежский институт МВД России, 2008. − 292
ЗадАние и МЕТОДИЧЕСКИЕ УКАЗАНИЯ курсантам по подготовке к лаборатороному занятию
Подготовительная часть. В часы самоподготовки курсанты повторяют содержание материала лекции.
В тетради сделать запись темы и целей занятия, кратких теоретических сведений по отрабатываемым учебным вопросам.
Элементы теории
Двумерный массив - это структура однотипных элементов, расположенных в виде таблицы значений. Такое представление значений соответствует математическому понятию двумерный массив. Каждый элемент в двумерном массиве идентифицируется номером строки и номером столбца, на пересечении которых он расположен. Например, в двумерном массиве А, изображенном на рис. 1, элемент со значением 5 расположен на пересечении третьей строки и второго столбца. Этот элемент будет обозначаться как А(3,2). А элемент А(1,4) имеет значение , равное нулю. Такое представлениенабора значений позволяет выполнять обработку как отдельных значений в двумерном массиве, так и последовательности значений, расположенных в строках или столбцах.
Рис. 1. Пример двумерного массива
В дальнейшем будем считать, что для двумерного массива A(N,М) в обозначении элемента А(i,j) первое значение i соответствует номеру строки и изменяется от 1 до N, а j-номеру столбца и изменяется от 1 до М. В отличие от одномерного массива, в котором использовался только один номер для определения местоположения элемента и требовался только один цикл для ввода элементов, в двумерном массиве для обработки элементов необходимы два вложенных друг в друга цикла. Внешний цикл предназначен для изменения номера строки i, а второй, внутренний, - для изменения номера столбца j в текущей строке i.
На рис. 2 представлен простой алгоритм ввода элементов, построенный в виде структуры из вложенных циклов.
Рис. 2. Алгоритм ввода элементов двумерного массива
Алгоритм ввода-вывода матриц
Матрицы, как и массивы, нужно вводить (выводить) поэлементно. Блок-схема ввода элементов матрицы изображена на рис. 3. Вывод матрицы организуется аналогично вводу.
|
Рис. 3 Ввод элементов матрицы |
Рис. 4. Свойства элементов матрицы |
Рассмотрим несколько задач обработки матриц. Для их решения напомним читателю некоторые свойства матриц (рис. 4):
Задача. .Найти сумму элементов матрицы, лежащих выше главной диагонали.
Рис. 5 . Матрица элементов
Алгоритм решения данной задачи (рис. 6) построен следующим образом: обнуляется ячейка для накапливания суммы (переменная S). Затем с помощью двух циклов (первый по строкам, второй по столбцам) просматривается каждый элемент матрицы, но суммирование происходит только в том случае если, этот элемент находится выше главной диагонали, то есть выполняется свойство i < j.
Рис. 6 . Алгоритм нахождения суммы элементов матрицы, лежащих выше главной диагонали.
На рисунке 7 изображен еще один вариант решения данной задачи. В нем проверка условия i<j не выполняется, но, тем не менее, в нем так же суммируются элементы матрицы, находящиеся выше главной диагонали. Для того чтобы понять, как работает этот алгоритм, вернемся к рисунку 5. В первой строке заданной матрицы необходимо сложить все элементы, начиная со второго. Во второй - все, начиная с третьего, в i-й строке процесс начнется с (i+1)-го элемента и так далее. Таким образом, первый цикл работает от 1 до N, а второй от i+1 до M..
Рис. 7 . Алгоритм нахождения суммы элементов матрицы, лежащих выше главной диагонали.
Задача.
Преобразовать исходную матрицу так, чтобы первый элемент каждой строки был заменен средним арифметическим элементов этой строки.
Для решения данной задачи необходимо найти в каждой строке сумму элементов, которую разделить на их количество. Полученный результат записать в первый элемент соответствующей строки. Блок-схема алгоритма решения приведена на рис. 8.
Рис. 8
Задача.
Задана матрица An, m. Сформировать вектор Pm, в который записать номера строк максимальных элементов каждого столбца.
Алгоритм решения этой задачи следующий: для каждого столбца матрицы находим максимальный элемент и его номер, номер максимального элемента j-го столбца матрицы записываем в j-й элемент массива P. Блок-схема алгоритма приведена на рис. 9.
Рис.9
Вопросы и задания для самопроверки
{-2, 5, 9, 14, 0, -32}
{3, 3.4, -4.0, 25, -6, 1.7}
{‘d’, ‘Q’, ‘1’, ‘v’}
{‘Ivanov’, ‘Petrov’, ‘Dmitriy’}
{‘s’, ‘w’, 2, ‘33’, ‘s’}
{‘Ivan’, ‘A’, ‘R’}.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ОТРАБОТКЕ УЧЕБНЫХ ВОПРОСОВ
2. Выполнение индивидуального задания
Задание 1. Составить циклические алгоритмы (в виде схемы и псевдокода) и таблицы трассировки для следующих задач обработки двумерных массивов:
1. Опишите алгоритм ввода элементов двумерного массива.
2. Опишите алгоритм выводы элементов двумерного массива.
3. Как поменять местами два элемента массива?
4. Опишите алгоритм нахождения суммы всех элементов двумерного массива?
5. Опишите алгоритм нахождения произведения всех элементов двумерного массива?