Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритмы обработки одномерных массивов↑ Стр 1 из 4Следующая ⇒ Содержание книги Похожие статьи вашей тематики
Поиск на нашем сайте
Тема 4.7 Алгоритмы обработки одномерных массивов
Структурированные данные Средства описания и работы с одномерными массивами данных
Динамические массивы 4.7.4. Базовые алгоритмы обработки одномерных массивов и примеры их программирования Элементы управления для работы со списками 4.7.6. Тестовые задания 4.7.7. Лабораторная работа по теме «Программирование алгоритмов формирования и обработки одномерных массивов» 4.7.7.1. Вопросы, подлежащие изучению
4.7.7.2. Общее задание на разработку проекта 4.7.7.3. Варианты индивидуальных заданий
4.7.7.4. Содержание отчёта
4.7.7.5. Пример выполнения задания
4.7.7.6. Контрольные вопросы
Структурированные данные Часто приходится обрабатывать не одиночные данные, а совокупность данных одного типа. Например, задача табулирования функции, которая состоит в получении последовательности значений заданной функции при нескольких значениях аргумента. Для промежуточного хранения каждого значения полученных данных требуется объявить собственную переменную с уникальным именем. Обращение к каждой переменной последовательности по имени превращается в длинную вереницу однотипных операций с каждой переменной. Программный код становится плохо обозримым. Для размещения такой программе требуется много памяти. Для устранения указанных проблем в алгоритмических языках используются структурированные данные. Самыми простыми структурированными данными являются массивы данных. Массив – это совокупность однотипных переменных (элементов массива). Имя у всех переменных одно и то же, а для доступа к конкретному элементу массива используется дополнительный идентификатор – его порядковый номер (индекс), который начинается с 0. Кроме массивов в программировании для построения эффективных алгоритмов могут использоваться и другие стандартные структуры данных, такие структуры данных, как стеки, очереди, связанные списки и другие. Наряду со стандартными структурами данных, могут использоваться структуры данных, определяемые пользователем. Эти структуры данных определяются средствами объектно-ориентированного программирования с помощью классов.
4.7.2. Средства описания и работы с одномерными
Массив – последовательность переменных одинакового типа, объединенных общим именем. Например: одномерный массив а(9) состоит из 10 элементов с общим именем а: a(0), a(1), a(2), a(3),..., a(9), упорядоченных по индексу i, который принимает значения от 0 до 9:
Массив в программе VBобъявляется точно так же, как объявляются простые переменные. Если массив объявлен локальным, его можно использовать только в той процедуре, в которой он объявлен. Если массив объявлен как глобальный, он может быть использован в любом месте программы. При объявлении массива оператор объявления должен включать следующую информацию: · имя массива – имя (идентификатор), которое используется для представления массива в программе; · тип данных – тип данных, который имеют элементы массива; · размерность (ранг) – количество измерений объявляемого массива (т.е. количество индексов при объявлении; одномерные массивы имеют одно измерение); · количество элементов – количество элементов, которые будут содержаться в массиве.
Рассмотрим примеры некоторых описаний массивов:
В этих примерах объявлены следующие массивы: · одномерный массив d, состоящий из 31 элемента типа Integer с индексами от 0 до 30; · одномерный массив a, состоящий из 11 элементов типа Double с индексами от 0 до 10; · двумерный массив b, состоящий из 14х11=151 элемента типа Single с индексами по строкам от 0 до 13 и по столбцам от 0 до 10. Обратите внимание, что значением нижней границы массива в VB может быть только 0. Таким образом, массив состоит из элементов, которые могут быть доступны при помощи индексов. При обращении к элементам массива индексы записываются вслед за именем в круглых скобках и могут представлять собой любое допустимое целочисленное выражение. Например, d(24), a(2*i+1). Обратите внимание, что количество индексов указывает на размерность массива. Так, в приведенном выше примере размерность массива a(10) равна единице. Массив b(2,3) имеет размерность 2. В отличие от размерности, размер массива – это количество элементов в массиве. В нашем примере размер массива, а(10) равен 11. Перед использованием массива в программе его необходимо объявить с помощью оператора Dim, а элементам массива присвоить конкретные значения. Оператор Dim выделяет место в памяти компьютера для размещения элементов массива, обнуляет элементы числовых массивов или заполняет элементы строковых массивов пустыми строками (''''). Как и для простых типов, данных, при объявлении массивов, которые являются структурированными типами данных, различают два способа распределения памяти: статическое – на этапе компиляции до выполнения программы, и динамическое – в ходе выполнения программы. По умолчанию массив, границы которого заданы константными выражениями, считается статическим. Память для размещения такого массива выделяется на этапе компиляции и сохраняется за ним на весь период выполнения. Заполнить элементы массива конкретными значениями можно с помощью ввода значений элементов массива, с помощью оператора присваивания или с помощью инициализации элементов массива. Инициализация элементов массива – это поэлементное присваивание значения в операторе объявления массива. В этом случае размер массива не указывается в круглых скобках после имени массива, а определяется неявно размером списка значений. Список значений начинается с элемента с индексом 0 и заключается в фигурные скобки, например:
Следует отметить, что независимо от конкретной задачи, алгоритмы формирования и обработки массивов обычно строятся с использованием регулярных циклических структур:
Чтобы облегчить работу с массивами в процедурах, для определения верхней границы массива используется встроенная функция Эта функция возвращает (определяет) номер последнего элемента массива и позволяет обрабатывать массивы в процедурах, не передавая в них в качестве параметра количество элементов массива. Например,
Кроме того, для определения верхней границы одномерного массива можно использовать метод GetUpperBound(). Поскольку массив одномерный, то в скобках следует указывать значение 0. Например:
Если имя массива, является формальным параметром процедуры, то после имени массива необходимо поместить пустые круглые скобки:
Кроме того, известно, что ключевое слово ByVal указывает передачу аргумента-массива по значению, а ключевое слово ByRef указывает, что аргумент-массив передается по ссылке. Заметим, что если ключевые слова ByVal или ByRef опущены, то аргумент-массив передается по ссылке. Таким образом, при описании формальных параметров любой процедуры после ИмяМассива необходимо всегда включать пустые круглые скобки, так как они указывают, что этот параметр является одномерным массивом.
Обращение к этим процедурам может, например, быть следующим:
Обратите внимание на то, что после имени массива, который является фактическим параметром, скобки отсутствуют.
Как известно, передача аргументов по значению (с помощью ключевого слова ByVal) приводит к тому, что VB передает копию данных процедуре. Поэтому не следует передавать массивы по значению, если в этом нет особой необходимости.
Пример 4.7.2-1. Написать процедуры ввода/вывода, которые могут использоваться в алгоритмах формирования и отображения одномерных массивов. Процедуры ввода и вывода для одномерных массивов представлены на
Рис. 4.7.2-1. Процедура ввода элементов массива Single с клавиатуры Примера 4.7.2-1
Рис. 4.7.2-2. Процедура формирования массива случайным образом Примера 4.7.2-1
Рис. 4.7.2-3. Процедура форматного вывода массива Single в ListBox Примера 4.7.2-1 Динамические массивы
Различают два способа распределения памяти: статическо е – на этапе компиляции до выполнения программы, и динамическое – в ходе выполнения программы. По умолчанию массив, границы которого заданы константными выражениями, считается статическим. Память для размещения такого массива выделяется на этапе компиляции программы и сохраняется за ним на весь период выполнения программы. Например:
Однако размеры массивов не всегда известны заранее, часто они определяются в ходе выполнения программы. Например, при табулировании значений функции количество хранимых значений в одномерном массиве определяется шагом дискретизации и диапазоном табулируемых значений функции, которые могут задаваться пользователем или вычисляться в процессе выполнения программы. Объявлять размерности массивов такими большими, что это будет заведомо достаточно для всех случаев, не всегда возможно и нерационально. Одно из решений проблемы – выделять память под массив не на этапе компиляции – статически, а после определения его размера – динамически. В качестве размера массива может быть использована переменная, значение которой вычисляется или вводится перед объявлением массива:
Другое решение проблемы – разделить в программе объявление массива и определение его размера – выделение памяти под него. При объявлении массива размер не указывается:
Значение размерности определяется позже (вычисляется или вводится) непосредственно перед его использованием, и тогда для выделения памяти уже объявленному массиву с указанием конкретной размерности массива используется оператор ReDim или ReDim Preserve:
Таким образом, динамические массивы имеют весьма полезное свойство – их размеры могут изменяться в процессе выполнения программ. При этом оператор ReDim изменяет размер массива и очищает его (обнуляет его элементы), а оператор ReDim Preserve изменяет размер массива и сохраняет значения существующих элементов. В следующем примере каждый раз при добавлении нового элемента к массиву происходит увеличение размера массива на единицу:
Таким образом, для создания динамического массива его необходимо предварительно объявить, не указывая количество элементов массива:
Затем, в момент, когда необходимо распределить под него память, используется оператор ReDim:
Второй вариант используется для изменения размера массива и для сохранения содержимого. На рис. 4.7.4-7, рис. 4.7.4-9 и рис. 4.7.4-10 приведены примеры программных кодов, использующие динамические массивы.
4.7.4. Базовые алгоритмы обработки одномерных массивов и примеры их программирования
Типичными задачами работы с одномерными массивами являются определение факта наличия в них заданного элемента и отбор элементов, удовлетворяющих определённым условиям. В обоих случаях используется циклическое сравнение элементов массива с заданным образцом. Для определения факта наличия заданного образца в массиве достаточно единственного совпадения, после чего дальнейший просмотр прекращается. Если условие отбора может выполняться для нескольких элементов массива, то необходим просмотр всего массива до конца. Для досрочного прекращения просмотра элементов массива в цикле используется оператор В массивах больших размеров для сокращения времени просмотра применяется упорядоченное хранение элементов. Для числовых массивов используется упорядочение элементов по значению, для текстовых – по алфавиту (точнее, по значению кода символов). Упорядочение обычно производиться путём сортировки элементов неупорядоченного массива. Из всего многообразия существующих задач, связанных с обработкой одномерных массивов, можно выделить следующие базовые алгоритмы: · Нахождение суммы значений элементов массива при заданных условиях (Пример 4.7.4-1). · Нахождение произведения значений элементов массива при заданных условиях (Пример 4.7.4-2). · Нахождение максимального и минимального значений элементов массива и их индексов (Пример 4.7.4-3). · Формирование нового массива из элементов одного или нескольких массивов в соответствии с заданными критериями (Примеры 4.7.4-3 – 4.7.4-4). · Формирование массива в соответствии с определенными правилами (Пример 4.7.4-7). · Вставка элемента по заданному критерию в массив · Удаление элемента по заданному критерию из массива · Обмен значений элементов массива по заданному критерию · Сортировка (упорядочивание) элементов массива (Пример 4.7.4-9).
Пример 4.7.4-1. Разработать процедуру, которая вычисляет произведение положительных и сумму отрицательных элементов массива x(). Схема алгоритма и программный код процедуры приведены на Напомним, что вычисление суммы и произведения обычно осуществляется по рекуррентным формул: s0 = 0; si+1 = si + xi+1; p0 = 1;
Рис. 4.7.4-1. Схема алгоритма и программный код процедуры Pr741() Примера 4.7.4-1
Пример 4.7.4-2. Разработать процедуру, в которой вычисляется произведение ненулевых элементов вещественного массив a(). Схема алгоритма и программный код приведены на рис. 4.7.4-2.
Рис. 4.7.4-2. Схема алгоритма и программный код процедуры Pr742() Примера 4.7.4-2 Пример 4.7.4-3. Разработать процедуру-Function, которая находит максимальное значения элементов массива t(). Схема алгоритма и программный код приведены на рис. 4.7.4-3.
Рис. 4.7.4-3. Схема алгоритма и программный код процедуры Pr743() Примера 4.7.4-3 Пример 4.7.4-4. Разработать процедуру-Function, которая находит индекс минимального значения элементов массива t().
Рис. 4.7.4-4. Схема алгоритма и программный код процедуры Pr744() Примера 4.7.4-4 Пример 4.7.4-5. Разработать процедуру, которая в заданном массиве c() переставляет элементы с целыми значениями в начало массива.
Рис. 4.7.4-5. Схема алгоритма и программный код процедуры Pr745() Примера 4.7.4-5 Для того чтобы переставить целые элементы в начало массива, в переменной k будем хранить номер элемента, в который переписывается очередное целое значение. Чтобы определить, является ли очередной элемент массива целым числом, проводится сравнение разности значения целой части очередного элемента и значения очередного элемента массива c(i) с нулем. Целая часть значения c(i) выделяется с помощью функции Fix(). Если очередной элемент массива c(i) содержит целое значение, то производится обмен значений двух элементов массива c(k) и c(i) c помощью temp. Схема алгоритма и программа приведены на рис. 4.7.4-5.
Пример 4.7.4-6. Разработать процедуру-Sub, в которой необходимо сформировать массив c(), по следующему правилу:
Схема алгоритма и программный код приведены на рис. 4.7.4-6.
Рис. 4.7.4-6. Схема алгоритма и программный код процедуры Pr746() Примера 4.7.4-6
Пример 4.7.4-7. Разработать процедуру-Sub, в которой необходимо сформировать массив y(), переписав в него положительные элементы исходного массива x().
Рис. 4.7.4-7. Схема алгоритма и программный код процедуры Pr747() Пример 4.7.4-7 Для решения поставленной задачи необходимо проверить знак у всех элементов массива х(). При этом текущий индекс n формируемого массива y() меняется независимо от индекса i исходного массива х(). Индекс n увеличивается на единицу только при появлении положительного элемента х(). Таким образом, после проверки всех элементов массива х() в переменной n будет содержаться число положительных элементов исходного массива. Схема алгоритма и программный код приведены на рис. 4.7.4-7.
Пример 4.7.4-8. Разработать процедуру-Sub, в которой необходимо из двух исходных массивов p() и r() с одинаковым числом элементов получить массив v() путем последовательного попарного переписывания в него элементов массивов p() и r(). В данной задаче для формирования массива v() используется переменная k, которая представляет собой номер очередного элемента массива v(). В цикле одновременно заполняются два элемента массива v(): в элемент с номером k переписывается i -й элемент из массива p(), а в элемент с номером (k+1) переписывается i -й элемент из массива r(). На рис. 4.7.4-8 приведены алгоритм и процедура и решения задачи.
Рис. 4.7.4-8. Схема алгоритма и программный код процедуры Pr748() Пример 4.7.4-8 Пример 4.7.4-9. Разработать программный код процедуры-Sub, который из массива вещественных чисел x(n) удаляет все отрицательные элементы и подсчитывает их количество k. Удаление всех отрицательных элементов массива реализуется в процедуре Pr748() по так называемому алгоритму «сжатия». Метод заключается в поиске удаляемого отрицательного элемента, фиксации его номера, а затем в последовательной перезаписи всех последующих элементов массива так, чтобы значение следующего i+1 элемента записывалось на место предыдущего, и так до конца массива.
Рис. 4.7.4-9. Схема алгоритма и программный код процедуры Pr749() Пример 4.7.4-9 Из последовательности исчезает удаляемый элемент, однако последний элемент повторяется дважды, поэтому после выхода из внутреннего цикла по перезаписи элементов длина массива (число n) должна быть уменьшена на единицу. Для изменения размерности массива используется оператор ReDim Preserve. уменьшена на единицу. Для изменения размерности массива используется оператор ReDim Preserve. Так как отрицательные элементы могут идти подряд, то i+1 элемент, который перешел на место i -го, тоже может быть меньше нуля. Поэтому необходимо снова проверить текущий i -й элемент (бывший i+1) и, возможно, тоже удалить его «сжатием». Переход к следующему элементу по параметру i (т.е. увеличение i на 1) происходит, только если проверяемый i -й элемент оказался неотрицательным, поэтому алгоритм «сжатия» может быть реализован с помощью внешнего итеративного (не регулярного) цикла. Ввод исходного одномерного массива случайными числами из диапазона [-10;5] осуществляет процедура vvod(), а вывод массива на форму в элемент управления ListBox осуществляет процедура vivod(), которая по вычисляемому методом Length количеству элементов массива проводит проверку, не является ли выводимый массив пустым. На рис. 4.7.4-9 приведены алгоритм и программа решения задачи. Пример 4.7.4-10. Разработать процедуру-Sub, действие которой заключается в удалении из массива x() одинаковых элементов.
Рис. 4.7.4-10. Схема алгоритма и программный код процедуры Pr7410() Пример 4.7.4-10 Решения задачи заключается в последовательном сравнении каждого элемента исходного массива со всеми остальными. В цикле происходит формирование массива x(j). Если элемент массива x(i) равен элементу x(j), то j -й элемент удаляется, а длина массива уменьшается на единицу. Алгоритм «сжатия» для получения массива с уникальными элементами и программа, реализующая данный алгоритм, приведены на рис. 4.7.4-10. Пример 4.7.4-11. Разработать процедуры-Sub, в которых осуществляется сортировка по убыванию значений элементов массива. Сделаем несколько общих замечаний по поводу сортировки элементов массива. Во-первых, стоит отметить, что под упорядочиванием (сортировкой) массива подразумевается процесс перестановки элементов массива с целью размещения элементов массива в определенном порядке. Наиболее часто применяются следующие способы упорядочивания массивов. 1) Упорядочивание по возрастанию. Каждый следующий элемент в массиве должен быть больше предыдущего. 2) Упорядочивание по убыванию. Каждый следующий элемент в массиве должен быть меньше предыдущего. 3) Упорядочивание по неубыванию. Каждый последующий элемент в массиве должен быть больше или равен предыдущему. 4) Упорядочивание по невозрастанию. Каждый последующий элемент в массиве должен быть меньше или равен предыдущему.
Во-вторых, необходимо отметить, что главным показателем качества алгоритма сортировки считается его быстродействие, реальные программы работают с большими объемами данных, сохраняемыми в массивах. Повышение быстродействия, под которым понимается уменьшение количества просмотров массива от начала до конца (проходов) с целью определения упорядоченности, может быть достигнуто за счет применения различных методов сортировки. Одним из простейших методов сортировки массива является сортировка прямого выбора, который нельзя отнести к высокоэффективным, так как в этом методе используется фиксированное число проходов, а оно не зависит от уровня первоначальной упорядоченности массива. Можно отметить также, что при разработке программ, связанных с сортировкой элементов массивов, при выводе результирующего массива можно использовать дополнительный цикл, который позволяет пользователю увидеть количество проходов, необходимых для окончательной сортировки массива. Рассмотрим «сортировку выбором» (метод «прямого выбора»). Алгоритм и программа сортировки массива по убыванию методом «прямого выбора» приведены на рис. 4.7.4-11.
Рис. 4.7.4-11. Схема алгоритма и программный код процедуры Pr7411() Пример 4.7.4-11
Суть этого метода сортировки состоит в следующем. Сортировка элементов массива по убыванию производится с помощью вложенных циклов. Сначала осуществляется поиск наибольшего элемента массива и его индекса среди всех элементов, начиная с 1-го. Найденный максимальный элемент меняется с первым элементом. Затем вновь осуществляется поиск наибольшего элемента массива и его индекса, но уже со второго элемента, и найденный максимальный элемент обменивается со 2-м элементом, и т.д. Таким образом, число найденных максимумов (поисков) равно n. При этом во внешнем цикле, начиная с первого и до предпоследнего элемента массива, сначала очередной элемент принимается за максимальный, а затем, после выполнения внутреннего цикла, обеспечивается заполнение этого очередного элемента массива наибольшим «среди оставшихся элементов». Внутренний цикл осуществляет перебор и сравнение последующих элементов, начиная с (i+1) -го до последнего элемента массива. В результате выполнения внутреннего цикла, в переменной xmax фиксируется значение наибольшего элемента, а в переменной k - его номер. Далее, во внешнем цикле выполняется перестановка найденного максимального элемента на место очередного i -го элемента массива. Рассмотрим сортировку элементов массива модифицированным методом «пузырька» (прямого обмена). Алгоритм и программа упорядочения массива по модифицированному методу «пузырька» приведены на рис. 4.7.4-12.
Рис. 4.7.4-12. Схема алгоритма и программный код процедуры Pr7412() Пример 4.7.4-11
Суть метода заключается в последовательном сравнении первого элемента массива со вторым, третьим и т.д. Если значения в паре расположены не в порядке возрастания (т.е. по убыванию), то их меняют местами. После первого просмотра элемент массива с наименьшим значением становится первым. Далее все элементы, начиная с третьего, сравниваются со вторым, в результате чего элемент со значением, следующим за минимальным элементом, становится на второе место. Продолжая таким же образом, вплоть до предпоследнего элемента, сортируют весь массив. Обратите внимание, что в схемах алгоритмов обмен значениями обозначается символом «↔», а в примере обмен реализован через дополнительную переменную xx. Массив - это 1) совокупность данных одного типа, объединенных общим именем 2) совокупность данных одного типа 3) набор индексированных данных 4) набор разных данных 5) набор однотипных файлов на диске Индексом массива может быть 1) выражение любого типа 2) любое целочисленное выражение 3) только целочисленные переменные 4) переменные любого типа Оператор Dim 1) резервирует область памяти для элементов массива 2) резервирует имя для элементов массива 3) выстраивает элементы массива в линейку 4) подсчитывает количество элементов массива Сортировка массива – это 1) упорядочивание элементов массива либо по возрастанию, либо по убыванию 2) перезапись элементов массива в обратном порядке 3) удаление нулевых элементов массива 4) в списке нет правильного ответа Фрагмент программы
выполняет 1) сжатие массива «сдвигом влево» 2) сжатие массива «сдвигом вправо» 3) удаление первых K элементов массива 4) удаление последних N-K элементов массива Фрагмент программы
1) удаляет из массива нулевые элементы 2) перемещает нулевые элементы влево 3) перемещает нулевые элементы вправо 4) оставляет все по-прежнему Вопросы, подлежащие изучению 1) Способы описания и объявления одномерных массивов. 2) Возможности резервирования памяти и хранения элементов массива. 3) Способы задания значений элементам массива: присваиванием; инициализацией; вводом по запросу с клавиатуры; заполнением массива данных случайными числами в заданном диапазоне. 4) Базовые алгоритмы обработки одномерных массивов: вычисление суммы (произведения) элементов массива; нахождение номера (и значения) минимального (максимального) значения элемента массива; формирование нового массива из исходного массива по заданному критерию; сортировка элементов массива от большего к меньшему (или от меньшего к большему); удаление элементов массива, имеющих равные значения (сжатие массива); удаление элементов массива по заданному критерию (сжатие по признаку). 5) Методы класса Array. 6) Методы работы с элементами управления ListBox и ComboBox. 4.7.7.2. Общее задание на разработку проекта 1) Изучите вопросы программирование алгоритмов формирования и обработки одномерных массивов (Тема 7). 2) Создайте приложениес именем Проект-4.7. 3) Выберите вариант задания из табл. 4.7.7-1. 4) Разработайте графический интерфейс пользователя. 5) Разработайте схемы алгоритмов процедур пользователя в соответствии с индивидуальным заданием, предварительно проведя формализацию. 6) Напишите программный код процедур по разработанным алгоритмам. 7) Разработайте проект приложения, решающий поставленную задачу, который состоит из интерфейса пользователя и соответствующего программного кода, а также написанных ранее процедур обработки, ввода и вывода элементов массива. Все пользовательские процедуры должны находиться в модуле формы. Обмен данными между пользовательскими процедурами должен осуществляться через параметры, без использования глобальных переменных. 8) Подготовьте входные массивы чисел для решения задачи, если исходные данные не заданы. 9) Выполните приложение и получите результат. 10) Докажите правильность результата.
Варианты индивидуальных заданий Таблица 4.7.7-1
|