Базовые алгоритмы обработки одномерных массивов и примеры их програмирования

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

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

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

  • • Нахождение сумм значений элементов массива при заданных условиях (Пример 7.4-1).
  • • Нахождение произведений значений элементов массива при заданных условиях (Пример 7.4-1 - 7.4-2).
  • • Нахождение максимального и миниммального значений элементов массива и их индексов (Пример 7.4-3).
  • • Формирование нового массива из элементов одного или нескольких массивов в соответствии с заданными критериями (Примеры 7.4-3 - 7.4-4).
  • • Формирование массива в соответствии с определенными правилами (Пример 7.4-7).
  • • Вставка элемента массива (Пример 7.4-5).
  • • Удаление элемента массива (Пример 7.4-6).
  • • Обмен значений элементов массива (Пример 7.4-8).
  • • Сортировка (упорядочивание) элементов массива (Пример 7.4-9).

Пример 7.4-1. Разработать процедуру-Sub, которая вычисляет произведение положительных и сумму отрицательных элементов массива х().

Схема алгоритма и код процедуры приведены на рис. 7.4-1.

Напомним, что вычисление суммы и произведения обычно осуществляется с использованием следующих рекуррентных формул: Схема алгоритма и программный код процедуры Рг741( ) Примера 7.4-1

Рис. 7.4-1. Схема алгоритма и программный код процедуры Рг741( ) Примера 7.4-1

Пример 7.4-2. Разработать процедуру-Function, в которой вычисляется произведение ненулевых элементов вещественного массив а().

Схема алгоритма и программный код процедуры Рг742( ) Примера 7.4-2

Рис. 7.4-2. Схема алгоритма и программный код процедуры Рг742( ) Примера 7.4-2

Пример 7.4-3. Разработать процедуру-Function, которая находит максимальное значение элементов массива х().

Схема алгоритма и программный код приведены на рис. 7.4-3.

Схема алгоритма а программный код процедуры Рг743()

Рис. 7.4-3. Схема алгоритма а программный код процедуры Рг743()

Примера 7.4-3

Пример 7.4-4. Разработать процедуру-Function, которая находит индекс минимального значения элементов массива х().

Схема алгоритма и программный код приведены на рис. 7.4-4.

Пример 7.4-5. Разработать процедуру-Sub, которая в заданном массиве с() переставит элементы с целыми значениями в начало массива.

Для того чтобы переставить целые элементы в начало массива, в переменной к будем хранить номер элемента, в который переписывается очередное целое значение. Чтобы определить, является ли очередной элемент массива целым числом, проводится сравнение разности значения целой части очередного элемента и значения очередного элемента массива c(i) с нулем.

Целая часть значения c(i) выделяется с помощью функции Fix(). Если очередной элемент массива c(i) содержит целое значение, то производится обмен значений двух элементов массива с(к) и c(i) с помощью переменной temp.

Схема алгоритма и программа приведены на рис. 7.4-3.

Схема алгоритма и программный код процедуры Рг744( )

Рис. 7.4-4. Схема алгоритма и программный код процедуры Рг744( )

Примера 7.4-4

Пример 7.4-6. Разработать процедуру-Sub, в которой необходимо сформировать массив с() по следующему правилу:

На рис. 7.3-6 приведены алгоритм и программа решения задачи.

Схема алгоритма а программный код процедуры Рг746()

Рис. 7.4-6. Схема алгоритма а программный код процедуры Рг746()

Примера 7.4-6

Пример 7.4-7. Разработать процедуру-Sub, в которой необходимо сформировать массив у( ), переписав в него положительные элементы исходного массива х().

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

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

Схема алгоритм и программа процедуры приведены на рис. 7.4-3.

Пример 7.4-8. Разработать процедуру-Sub, в которой необходимо из двух исходных массивов р() и г() с одинаковым числом элементов получить массив v( ) путем последовательного попарного переписывания в него элементов массивов р() и г().

Схема алгоритма и программный код процедуры Рг747() Пример 7.4-7

Рис. 7.4-7. Схема алгоритма и программный код процедуры Рг747() Пример 7.4-7

Схема алгоритма и программный код процедуры Рг748( ) Пример 7.4-8

Рис. 7.4-8. Схема алгоритма и программный код процедуры Рг748( ) Пример 7.4-8

В данной задаче для формирования массива v( ) используется переменная к, которая представляет собой номер очередного элемента массива v(). В цикле одновременно заполняются два элемента массива v( ): в элемент с номером к переписывается i-й элемент из массива р(), а в элемент с номером (к+1) переписывается i-й элемент из массива г().

На рис. 7.4-8 приведены алгоритм и процедура и решения задачи.

Пример 7.4-9. Разработать программный код процедуры-Sub, который из массива вещественных чисел х(п) удаляет все отрицательные элементы и подсчитывает их количество к.

Схема алгоритма и программный код процедуры Рг749()

Рис. 7.4-9. Схема алгоритма и программный код процедуры Рг749()

Пример 7.4-9

Удаление всех отрицательных элементов массива реализуется в процедуре Рр749( ) по так называемому алгоритму «сжатия». Метод заключается в поиске удаляемого отрицательного элемента, фиксации его номера, а затем в последовательной перезаписи всех последующих элементов массива так, чтобы значение следующего i+1 элемента записывалось на место предыдущего, и так до конца массива.

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

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

Ввод исходного одномерного массива случайными числами из диапазона [-10;5] осуществляет процедура vvod ( ), а вывод массива на форму в элемент управления ListBox осуществляет процедура vivod ( ), которая по вычисляемому методом Length количеству элементовмассива проводит проверку, не является ли выводимый массив пустым.

На рис. 7.4-9 приведены алгоритм и программа решения задачи.

Пример 7.4-10. Разработать процедуру-Sub, действие которой заключается в удалении из массива х() одинаковых элементов.

Решения задачи заключается в последовательном сравнении каждого элемента исходного массива со всеми остальными. В цикле происходит формирование массива x(j). Если элемент массива x(i) равен элементу x(j), то j-й элемент удаляется, а длина массива уменьшается на единицу.

Алгоритм «сжатия» для получения массива с уникальными элементами и программа, реализующая данный алгоритм, приведены на рис. 7.4-10.

Пример 7.4-11. Разработать процедуры-Sub, в которых осуществляется сортировка по убыванию значений элементов массива.

Сделаем несколько общих замечаний по поводу сортировки элементов массива.

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

  • 1) Упорядочивание по возрастанию. Каждый следующий элемент в массиве должен быть больше предыдущего.
  • 2) Упорядочивание по убыванию. Каждый следующий элемент в массиве должен быть меньше предыдущего.
  • 3) Упорядочивание т. е, что каждый последующий элемент в массиве должен быть больше или равен предыдущему.
Схема алгоритма и программный код процедуры Рг7410() Пример 7.4-10

Рис. 7.4-10. Схема алгоритма и программный код процедуры Рг7410() Пример 7.4-10

4) Упорядочивание по невозрастанию. Каждый последующий элемент в массиве должен быть меньше или равен предыдущему.

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

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

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

Схема алгоритма и программный код процедуры Рг7411()

Рис. 7.4-11. Схема алгоритма и программный код процедуры Рг7411()

Пример 4.7.4-11

Рассмотрим «сортировку выбором» (метод «прямого выбора»).

Алгоритм и программа сортировки массива по убыванию методом «прямого выбора» приведены на рис. 7.4-11.

Суть этого метода сортировки состоит в следующем.

Сортировка элементов массива по убыванию производится с помощью вложенных циклов. Сначала осуществляется поиск наибольшего элемента массива и его индекса среди всех элементов, начиная с 1-го. Найденный максимальный элемент меняется с первым элементом. Затем вновь осуществляется поиск наибольшего элемента массива и его индекса, но уже со второго элемента, и найденный максимальный элемент обменивается со 2-м элементом, и т. д.. Таким образом, число найденных максимумов (поисков) равно п. При этом во внешнем цикле, начиная с первого и до предпоследнего элемента массива, сначала очередной элемент принимается за максимальный, а затем, после выполнения внутреннего цикла, обеспечивается заполнение этого очередного элемента массива наибольшим «среди оставшихся элементов».

Внутренний цикл осуществляет перебор и сравнение последующих элементов, начиная с (i+D -го до последнего элемента массива. В результате выполнения внутреннего цикла в переменной хтах фиксируется значение

Схема алгоритма и программный код процедуры Рг7412( )

Рис. 7.4-12. Схема алгоритма и программный код процедуры Рг7412( )

Пример 7.4-11

наибольшего элемента, а в переменной к - его номер. Далее во внешнем цикле выполняется перестановка найденного максимального элемента на место очередного i-ro элемента массива.

Расмотрим сортировку элементов массива модифицированным методом «пузырька» (прямого обмена).

Алгоритм и программа упорядочения массива по модифицированному методу «пузырька» приведены на рис. 7.4-12.

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

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

Обратите внимание, что в схемах алгоритмов обмен значениями обозначается символом «<->», а в примере обмен реализован через дополнительную переменную хх.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >