Класс. МУПР ОП.08 Теория алгоритмов. Методические указания по проведению практических работ по дисциплине Теория алгоритмов
 Скачать 3.39 Mb.
|
Практическая работа №15. Составление алгоритма поиска в неупорядоченном массивеЦель работы: Получение навыков построения алгоритмов последовательного поиска. Теоретический материал для повторения Массив представляет собой упорядоченную структуру однотипных данных, которые называются элементами массива. Доступ к каждому элементу массива осуществляется с помощью индекса – в общем случае порядкового номера элемента в массиве. Массивы могут быть как одномерными (адрес каждого элемента определяется значением одного индекса), так и многомерными (адрес каждого элемента определяется значением нескольких индексов). Массивы занимают смежные ячейки памяти. (Другими словами, элементы массива в памяти расположены последовательно друг за другом.) Ячейка с наименьшим адресом относится к первому элементу массива, а с наибольшим — к последнему. Предположим, мы используем массив a из семи элементов. После заполнения массив будет выглядеть следующим образом.
Для работы с одномерными массивами применяются циклические алгоритмы. Алгоритм, предусматривающий многократное повторение одного и того же действия над новыми данными, называется циклическим. Тело цикла - это повторяющаяся последовательность действий (блок инструкций). Цикл называется арифметическим, если число повторений цикла известно заранее или может быть вычислено. Цикл называется арифметическим, если число повторений цикла известно заранее или может быть вычислено. Выражение 1 выполняется только один раз в начале цикла. Обычно оно определяет начальное значение параметра цикла (инициализирует параметр цикла). Выражение 2 — это условие выполнения цикла. Выражение 3 обычно определяет изменение параметра цикла. Блок инструкций — тело цикла, то есть инструкции, которые должны выполняться заданное количество раз..  Обратите внимание на то, что после вычисления выражения 3 происходит возврат к вычислению выражения 2 — проверке условия повторения цикла. Поиск минимального (максимального) элемента массива Задачу поиска минимального элемента массива рассмотрим на примере массива целых чисел. Алгоритм поиска минимального (максимального) элемента массива довольно очевиден: сначала делается предположение, что первый элемент массива является минимальным (максимальным), затем остальные элементы массива последовательно сравниваются с этим элементом. Если во время очередной проверки обнаруживается, что проверяемый элемент меньше (больше) принятого за минимальный (максимальный), то этот элемент становится минимальным (максимальным) и продолжается проверка оставшихся элементов.  Чтобы не загромождать блок-схему, вывод исходного массива обозначен одним блоком «вывод» (надо помнить, что для вывода на экран массива используется цикл с параметром). Поиск в массиве заданного элемента методом простого перебора При решении многих задач возникает необходимость определить, содержит ли массив определенную информацию или нет. Например, проверить, есть ли в списке студентов фамилия Петров. Задачи такого типа называются поиском в массиве. Для организации поиска в массиве могут быть использованы различные алгоритмы. Наиболее простой — это алгоритм простого перебора. Поиск осуществляется последовательным сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы. Алгоритм простого перебора применяется, если элементы массива не упорядочены. Цикл просмотра элементов массива завершается, если в массиве обнаружен элемент, равный образцу (в этом случае значение специальной переменной-признака равно единице), или если проверены все элементы массива. По завершении цикла по значению переменной-признака можно определить, успешен поиск или нет. Очевидно, что чем больше элементов в массиве и чем дальше расположен нужный элемент от начала массива, тем дольше программа будет искать необходимый элемент. Пример Заполнить массив десятью значениями 30,53,11,35,17,42,21,84,75,61. Составить алгоритм, который по введенному пользователем числу определит – есть это число в данной последовательности и выведет на экран позицию в массиве этого числа.  Задание Составить блок-схему алгоритма решения задачи. 1) Определить число максимумов в заданной последовательности чисел. 2) Заменить все минимумы в последовательности чисел их утроенным значением. 3) Сжать числовой массив, удалив из него все максимумы. Дополнительные задания 1) Найти повторяющиеся элементы в заданной последовательности чисел. 2) Найти неповторяющиеся элементы в заданной последовательности чисел. 3) Составить однопроходный алгоритм подсчета минимумов в последовательности чисел. |