§20. Обработка массивов.
Информатика. Учебник для 9 класса (по учебнику К. Ю. Полякова, Е.А. Еремина, базовый уровень)
Введение
Ключевые слова:
• массив • перестановка элементов • вспомогательная переменная • выход за границы массива • линейный поиск • сортировка
Современные компьютеры работают с огромными массивами данных. При этом размер программы не зависит от размера массива: можно написать очень короткую программу, которая обрабатывает миллиарды чисел.
Из курса 8 класса вы уже знаете, как найти сумму элементов массива и его максимальный (минимальный) элемент, определить количество элементов, удовлетворяющих условию. В этом параграфе мы изучим некоторые более сложные алгоритмы.
Вспомните и запишите в тетрадь, как:
• объявить целочисленный массив из N элементов;
• заполнить массив нулями;
• заполнить массив натуральными числами от 1 до N;
• заполнить массив случайными числами в диапазоне [50, 100];
• найти сумму значений всех элементов массива;
• найти сумму значений чётных элементов массива;
• найти количество отрицательных элементов массива;
• найти максимальный элемент массива.
Перестановка элементов массива
Во многих задачах нужно переставлять элементы массива, т. е. требуется менять местами значения двух ячеек памяти.
Представьте себе, что в кофейной чашке налит сок, а в стакане — кофе, и вы хотите, чтобы было наоборот. Что вы сделаете?
Вернёмся к программированию. Чтобы поменять местами значения двух переменных — а и b, нужно использовать третью переменную того же типа:
с:=а с:=а;
а:=b а:=b;
b:=с b:=с;
Перестановка двух элементов массива, например А [i] и А [к], выполняется так же:
с:=А[i] с:=А[i];
А[i]:=А[k] A[i]:=А[к];
А[к]:=с А[к]:=с;
Теперь рассмотрим несколько задач, в которых требуется переставить элементы массива в другом порядке.
Задача 1. Массив А содержит чётное количество элементов N. Нужно поменять местами пары соседних элементов: первый со вторым, третий — с четвёртым и т.д. (рис. 4.1).
Рис. 4.1
С каким элементом нужно поменять местами элемент А [i]? Зависит ли ваш ответ от свойств числа i?
Сергей написал такой алгоритм для решения задачи 1:
нц для i от 1 до N
поменять местами A[i] и A[i+1]
кц
Выполните его вручную для массива {1, 2, 3, 4} (N = 4). Объясните результат. Найдите ошибки в этом алгоритме.
Обратите внимание, что на последнем шаге цикла мы будем менять местами элемент А [ N ] с несуществующим элементом A [N+1 ]. Это вызовет ошибку, которая называется выход за границы массива. Но даже если изменить наибольшее значение переменной цикла на N-1, программа всё равно будет работать неправильно, т. е. приведёт к неверному решению задачи 1. Получится, что первый элемент просто «переедет» на место последнего.
Для того чтобы исправить программу, нужно изменять переменную i с шагом 2:
Решение на языке Паскаль получилось немного более сложным, потому что в этом языке можно изменять переменную цикла только с шагом 1 или -1, а нам нужен шаг 2. В этой ситуации можно, например, использовать цикл с условием (цикл while).
Предложите другое решение этой задачи, записав нужные операторы в теле цикла.
Реверс массива
Задача 2. Требуется выполнить реверс массива, т. е. переставить элементы массива в обратном порядке, так чтобы первый элемент стал последним, а последний — первым (рис. 4.2).
Рис. 4.2
С каким элементом нужно поменять местами элемент А [1] ? Элемент А [2]? Элемент А [i]?
Если индекс первого элемента в паре увеличивается на 1, а индекс второго элемента уменьшается на 1, что можно сказать о сумме индексов этих элементов?
В этой задаче сумма индексов элементов, участвующих в обмене, для всех пар равна N+1, поэтому элемент с номером i должен меняться местами с (N+l-i)-M элементом.
Выполните вручную следующий алгоритм для массива {1, 2, 3, 4} (N = 4). Объясните результат. Найдите ошибки в этом алгоритме (почему он не решает задачу 2?).
нц для i от 1 до N
поменять местами A[i] и А[N+1-i]
кц
Для того чтобы не выполнять реверс дважды, нужно остановить цикл на середине массива:
нц для i от 1 до div(N, 2)
поменять местами А[i] и A[N+l-i]
кц
Запишите в тетради операторы, которые нужно добавить в тело цикла. Для обмена используйте вспомогательную переменную с.
нц для i от 1 до div(N, 2) for i:=l to N div 2 do begin
• • • • • •
КЦ end;
Запишите в тетради другое решение задачи реверса массива, которое использует цикл с условием (пока, while).
Линейный поиск в массиве
Очень часто требуется найти в массиве заданное значение или определить, что его там нет. Для этого нужно просмотреть все элементы массива с первого до последнего. Как только будет найден элемент, равный заданному значению X, надо завершить цикл и вывести результат. Такой поиск называется линейным.
Сколько операций сравнения придётся выполнить, если в массиве N элементов? В каком случае количество сравнений будет наименьшим? Наибольшим?
Катя торопилась и написала такой алгоритм линейного поиска:
i:=1
нц пока A[i]<>Х i:=i+l
кц
вывод ‘А [‘, i,’] = ‘,X
Проверьте: правильно ли сработает алгоритм, если искать в массиве {1, 2, 3} число 2? Число 4?
Этот алгоритм хорошо работает, если нужный элемент в массиве есть, однако приведёт к ошибке, если такого элемента нет, — получится зацикливание и выход за границы массива. Чтобы этого не произошло, в условие нужно добавить ещё одно ограничение: i <= N. Если после окончания цикла это условие нарушено, это означает, что поиск был неудачным — элемента нет:
В сложном условии i <= N и А [i] <> X первым должно проверяться именно отношение i <= N. Если первая часть условия, соединённого с помощью операции И, ложна, то вторая часть не вычисляется — уже понятно, что всё условие ложно. Дело в том, что, если i > N, проверка условия А [i] <> X приводит к выходу за границы массива, и программа может завершиться аварийно.
Возможен ещё один поход к решению этой задачи: используя цикл с переменной, перебрать все элементы массива и досрочно завершить цикл, если найдено требуемое значение:
Для выхода из цикла используется оператор выход (в Паскале — break), номер найденного элемента сохраняется в переменной nХ. Если её значение осталось равным нулю (не изменилось в ходе выполнения цикла), то в массиве нет элемента, равного X.
Сортировка массивов
Сортировка — это расстановка элементов списка (массива) в заданном порядке.
Возникает естественный вопрос: зачем сортировать данные? На него легко ответить, вспомнив, например, работу со словарями: сортировка слов по алфавиту облегчает поиск нужной информации.
Для чисел обычно используют сортировку по возрастанию (каждый следующий элемент больше предыдущего) или убыванию (следующий элемент меньше предыдущего). Если в массиве есть одинаковые элементы, их можно расставить по неубыванию (каждый следующий элемент не меньше предыдущего) или невозрастанию.
Математики и программисты изобрели множество способов сортировки. В целом их можно разделить на две группы: 1) простые, но медленно работающие (на больших массивах), и 2) сложные, но быстрые.
Мы изучим один из простых методов, который называется методом выбора. Для примера будем рассматривать сортировку по возрастанию (неубыванию).
Предположим, что мы нашли минимальный элемент массива. Где он должен размещаться в отсортированном массиве?
Запишите в тетради фрагмент программы для поиска номера минимального элемента массива.
Для того чтобы поставить на место минимальный элемент, мы просто поменяем его местами с первым элементом массива.
Запишите в тетради фрагмент программы, который меняет местами элементы А[1] и A[nMin]. Используйте вспомогательную переменную с.
После того как мы установили на место первый (минимальный) элемент, находим минимальный из оставшихся и ставим его на второе место и т. д. Полный алгоритм записывается в виде вложенного цикла:
На первом шаге внешнего цикла значение i равно 1, и мы ставим на первое место минимальный элемент. На следующем шаге i = 2, мы ищем минимальный элемент среди всех, кроме первого, и т. д.
Обратите внимание, что внешний цикл выполняется N-1 раз (а не N). Этого достаточно, потому что если N-1 элементов стоят на своих местах, то последний тоже стоит на своём месте (другого свободного места для него нет).
Решение на языке Паскаль выглядит так:
Что получится, если внешний цикл (по переменной i) выполнить только 1 раз? Только 3 раза?
Выводы
• Поменять местами значения двух элементов массива можно с помощью вспомогательной переменной.
• Выход за границы массива — это обращение к элементу массива с несуществующим индексом.
• Линейный поиск — это перебор всех элементов массива до тех пор, пока не будет найден нужный элемент или не закончится массив.
• Сортировка — это расстановка элементов списка (массива) в заданном порядке. Для чисел обычно используют сортировку по возрастанию (неубыванию) или убыванию (невозрастанию). Данные сортируют для того, чтобы ускорить последующий поиск.
Нарисуйте в тетради интеллект-карту этого параграфа.
Вопросы и задания
1. Что такое выход за границы массива? Что опаснее — чтение или запись данных за границами массива?
2. На какой идее основан метод сортировки выбором?
3. Объясните, зачем нужен вложенный цикл в алгоритме сортировки.
4. Как нужно изменить программу сортировки, чтобы элементы массива были отсортированы по убыванию?
5. Выполните по указанию учителя задания в рабочей тетради.
Подготовьте сообщение
а) «Сортировка методом пузырька»
б) «Сортировка методом вставки»
§20. Обработка массивов.
§21. Матрицы (двумерные массивы).