Тема 2.5 Типовые алгоритмы обработки массивов, рекурсии
План:
Часто для работы с множеством однотипных данных (целочисленными значениями, строками, датами и т.п.) оказывается удобным использовать массивы. Например, можно создать массив для хранения списка студентов, обучающихся в одной группе. Вместо создания переменных для каждого студента, например Студент1, Студент2 и т.д., достаточно создать один
массив, где каждой фамилии из списка будет присвоен порядковый номер. Таким образом, можно дать следующее определение. Массив – структурированный тип данных, состоящий из фиксированного числа элементов одного типа.
Массив на рисунке 4.1 имеет 8 элементов, каждый элемент сохраняет число вещественного типа. Элементы в массиве пронумерованы от 1 до 8. Такого рода массив, представляющий собой просто список данных одного и того же типа, называют простым или одномерным массивом. Для доступа к данным, хранящимся в определенном элементе массива, необходимо указать имя массива и порядковый номер этого элемента, называемый индексом
- Алгоритмы обработки массивов
- Ввод-вывод элементов одномерного массива
- Сортировка элементов в массиве
Часто для работы с множеством однотипных данных (целочисленными значениями, строками, датами и т.п.) оказывается удобным использовать массивы. Например, можно создать массив для хранения списка студентов, обучающихся в одной группе. Вместо создания переменных для каждого студента, например Студент1, Студент2 и т.д., достаточно создать один
массив, где каждой фамилии из списка будет присвоен порядковый номер. Таким образом, можно дать следующее определение. Массив – структурированный тип данных, состоящий из фиксированного числа элементов одного типа.
Массив на рисунке 4.1 имеет 8 элементов, каждый элемент сохраняет число вещественного типа. Элементы в массиве пронумерованы от 1 до 8. Такого рода массив, представляющий собой просто список данных одного и того же типа, называют простым или одномерным массивом. Для доступа к данным, хранящимся в определенном элементе массива, необходимо указать имя массива и порядковый номер этого элемента, называемый индексом
Рис. 4.1 Одномерный числовой массив
Если возникает необходимость хранения данных в виде таблиц, в формате строк и столбцов, то необходимо использовать многомерные массивы. На рисунке 4.2 приведен пример массива, состоящего из четырех строк и четырех столбцов. Это двумерный массив. Строки в нем можно считать первым измерением, а столбцы вторым. Для доступа к данным, хранящимся в этом массиве, необходимо указать имя массива и два индекса, первый должен соответствовать номеру строки, а второй номеру столбца в которых хранится необходимый элемент
Если возникает необходимость хранения данных в виде таблиц, в формате строк и столбцов, то необходимо использовать многомерные массивы. На рисунке 4.2 приведен пример массива, состоящего из четырех строк и четырех столбцов. Это двумерный массив. Строки в нем можно считать первым измерением, а столбцы вторым. Для доступа к данным, хранящимся в этом массиве, необходимо указать имя массива и два индекса, первый должен соответствовать номеру строки, а второй номеру столбца в которых хранится необходимый элемент
Рис. 4.2 Двумерный числовой массив
Ввод-вывод элементов одномерного массива
При вводе массива необходимо последовательно вводить 1-й, 2-й, 3-й и т.д. элементы массива, аналогичным образом поступить и при выводе. Следовательно, необходимо организовать цикл.
Блок-схемы алгоритмов ввода элементов массива изображены на рис. 6.3-6.4.
Ввод-вывод элементов одномерного массива
При вводе массива необходимо последовательно вводить 1-й, 2-й, 3-й и т.д. элементы массива, аналогичным образом поступить и при выводе. Следовательно, необходимо организовать цикл.
Блок-схемы алгоритмов ввода элементов массива изображены на рис. 6.3-6.4.
Как видно, безусловный цикл удобно использовать для обработки всего массива, и в дальнейшем при выполнении таких операций будем применять именно его. Вывод массива организуется аналогично вводу.
Рассмотрим несколько примеров обработки массивов. Алгоритмы, с помощью которых обрабатывают одномерные массивы, похожи на обработку последовательностей (вычисление суммы, произведения, поиск элементов по определенному признаку, выборки и т. д.). Отличие заключается в том, что в массиве одновременно доступны все его компоненты, поэтому становится возможной, например, сортировка его элементов и другие, более сложные преобразования.
Вычисление суммы элементов массива
Дан массив X, состоящий из n элементов. Найти сумму элементов этого массива.
Процесс накапливания суммы элементов массива достаточно прост и практически ничем не отличается от суммирования значений некоторой числовой последовательности. Переменной S присваивается значение равное нулю, затем
последовательно суммируются элементы массива X. Блок-схема алгоритма расчета суммы приведена на рис. 6.5.
Вычисление произведения элементов массива
Дан массив X, состоящий из n элементов. Найти произведение элементов этого массива. Решение этой задачи сводится к тому, что значение переменной Р, вкоторую предварительно была записана единица, последовательно умножается на значение i–го элемента массива. Блок-схема алгоритма приведена на рис. 6.6.
Рассмотрим несколько примеров обработки массивов. Алгоритмы, с помощью которых обрабатывают одномерные массивы, похожи на обработку последовательностей (вычисление суммы, произведения, поиск элементов по определенному признаку, выборки и т. д.). Отличие заключается в том, что в массиве одновременно доступны все его компоненты, поэтому становится возможной, например, сортировка его элементов и другие, более сложные преобразования.
Вычисление суммы элементов массива
Дан массив X, состоящий из n элементов. Найти сумму элементов этого массива.
Процесс накапливания суммы элементов массива достаточно прост и практически ничем не отличается от суммирования значений некоторой числовой последовательности. Переменной S присваивается значение равное нулю, затем
последовательно суммируются элементы массива X. Блок-схема алгоритма расчета суммы приведена на рис. 6.5.
Вычисление произведения элементов массива
Дан массив X, состоящий из n элементов. Найти произведение элементов этого массива. Решение этой задачи сводится к тому, что значение переменной Р, вкоторую предварительно была записана единица, последовательно умножается на значение i–го элемента массива. Блок-схема алгоритма приведена на рис. 6.6.
Совет.
Алгоритм поиска минимального элемента в массиве будет отличаться
от приведенного выше лишь тем, что в условном блоке знак поменяется с > на <.
Сортировка элементов в массиве
Сортировка представляет собой процесс упорядочения элементов в массиве в порядке возрастания или убывания их значений. Например, массив X из n
элементов будет отсортирован в порядке возрастания значений его элементов, если X1 £ X2 £… £ Xn, и в порядке убывания, если X1 ³ X2 ³… ³ Xn.
Существует большое количество алгоритмов сортировки, но все они базируются на трех основных:
сортировка обменом;
С сортировка выбором;
С сортировка вставкой.
Представим, что нам необходимо разложить по порядку карты в колоде. Для сортировки карт обменом можно разложить карты на столе лицевой стороной вверх и менять местами те карты, которые расположены в неправильном порядке, делая это до тех пор, пока колода карт не станет упорядоченной.
Для сортировки выбором из разложенных на столе карт выбирают самую младшую (старшую) карту и держат ее в руках. Затем из оставшихся карт вновь выбрать наименьшую (наибольшую) по значению карту и помещают ее позади той карты, которая была выбрана первой. Этот процесс повторяется до тех пор, пока вся колода не окажется в руках. Поскольку каждый раз выбирается наименьшая (наибольшая) по значению карта из оставшихся на столе карт, по завершению такого процесса карты будут отсортированы по возрастанию (убыванию).
Для сортировки вставкой из колоды берут две карты и располагают их в необходимом порядке по отношению друг к другу. Каждая следующая карта, взятая из колоды, должна быть установлена на соответствующее место по отношению к уже упорядоченным картам.
Итак, решим следующую задачу. Задан массив Y из n целых чисел.
Расположить элементы массива в порядке возрастания их значений.
6.5.1. Сортировка методом «пузырька»
Сортировка пузырьковым методом является наиболее известной. Ее популярность объясняется запоминающимся названием, которое происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень, и простотой алгоритма.
Сортировка методом «пузырька» использует метод обменной сортировки иоснована на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Рассмотрим алгоритм пузырьковой сортировки более подробно.
Сравним первый элемент массива со вторым, если первый окажется больше второго, то поменяем их местами. Те же действия выполним для второго и третьего, третьего и четвертого, i–го и (i+1)–го, (n–1)–го и n–го элементов. В
результате этих действий самый большой элемент станет на последнее (n-е) место. Теперь повторим данный алгоритм сначала, но последний (n-й) элемент,
рассматривать не будем, так как он уже занял свое место. После проведения данной операции самый большой элемент оставшегося массива станет на (n–1)-е
место. Так повторяем до тех пор, пока не упорядочим весь массив.
табл.6.2 подробно расписан процесс упорядочивания элементов в массиве. Нетрудно заметить, что для преобразования массива, состоящего из n элементов, необходимо просмотреть его n–1 раз, каждый раз уменьшая диапазон просмотра на один элемент. Блок–схема описанного алгоритма приведена на рис. 6.8. Обратите внимание на то, что для перестановки элементов (блок 4) используется буферная переменная b, в которой временно хранится значение элемента, подлежащего замене.
Таблица 6.2. Процесс упорядочивания элементов в массиве по возрастанию
Алгоритм поиска минимального элемента в массиве будет отличаться
от приведенного выше лишь тем, что в условном блоке знак поменяется с > на <.
Сортировка элементов в массиве
Сортировка представляет собой процесс упорядочения элементов в массиве в порядке возрастания или убывания их значений. Например, массив X из n
элементов будет отсортирован в порядке возрастания значений его элементов, если X1 £ X2 £… £ Xn, и в порядке убывания, если X1 ³ X2 ³… ³ Xn.
Существует большое количество алгоритмов сортировки, но все они базируются на трех основных:
сортировка обменом;
С сортировка выбором;
С сортировка вставкой.
Представим, что нам необходимо разложить по порядку карты в колоде. Для сортировки карт обменом можно разложить карты на столе лицевой стороной вверх и менять местами те карты, которые расположены в неправильном порядке, делая это до тех пор, пока колода карт не станет упорядоченной.
Для сортировки выбором из разложенных на столе карт выбирают самую младшую (старшую) карту и держат ее в руках. Затем из оставшихся карт вновь выбрать наименьшую (наибольшую) по значению карту и помещают ее позади той карты, которая была выбрана первой. Этот процесс повторяется до тех пор, пока вся колода не окажется в руках. Поскольку каждый раз выбирается наименьшая (наибольшая) по значению карта из оставшихся на столе карт, по завершению такого процесса карты будут отсортированы по возрастанию (убыванию).
Для сортировки вставкой из колоды берут две карты и располагают их в необходимом порядке по отношению друг к другу. Каждая следующая карта, взятая из колоды, должна быть установлена на соответствующее место по отношению к уже упорядоченным картам.
Итак, решим следующую задачу. Задан массив Y из n целых чисел.
Расположить элементы массива в порядке возрастания их значений.
6.5.1. Сортировка методом «пузырька»
Сортировка пузырьковым методом является наиболее известной. Ее популярность объясняется запоминающимся названием, которое происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень, и простотой алгоритма.
Сортировка методом «пузырька» использует метод обменной сортировки иоснована на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Рассмотрим алгоритм пузырьковой сортировки более подробно.
Сравним первый элемент массива со вторым, если первый окажется больше второго, то поменяем их местами. Те же действия выполним для второго и третьего, третьего и четвертого, i–го и (i+1)–го, (n–1)–го и n–го элементов. В
результате этих действий самый большой элемент станет на последнее (n-е) место. Теперь повторим данный алгоритм сначала, но последний (n-й) элемент,
рассматривать не будем, так как он уже занял свое место. После проведения данной операции самый большой элемент оставшегося массива станет на (n–1)-е
место. Так повторяем до тех пор, пока не упорядочим весь массив.
табл.6.2 подробно расписан процесс упорядочивания элементов в массиве. Нетрудно заметить, что для преобразования массива, состоящего из n элементов, необходимо просмотреть его n–1 раз, каждый раз уменьшая диапазон просмотра на один элемент. Блок–схема описанного алгоритма приведена на рис. 6.8. Обратите внимание на то, что для перестановки элементов (блок 4) используется буферная переменная b, в которой временно хранится значение элемента, подлежащего замене.
Таблица 6.2. Процесс упорядочивания элементов в массиве по возрастанию
Междисциплинарный курс
Разработка программных модулей
Вы можете оставить отзыв отправив письмо на данную почту
pobeats30@gmail.com
pobeats30@gmail.com
