Учебник. А. Ю. Босова Москва бином. Лаборатория знаний 2016 11 класс Базовый уровень Учебник
 Скачать 4.61 Mb.
|
|
Глава 2. алгоритмы и программирование 8.2. Задачи поиска элемента с заданными свойствами Очень часто в реальной жизни нам приходится сталкиваться с задачей поиска информации в большом массиве данных. Напри- мер, поиск нужного слова в словаре, поиск времени отправления нужного поезда в расписании, поиск нужного товара в интернет- магазине и т. д. В программировании поиск — одна из наиболее часто встре- чающихся задач невычислительного характера. В алгоритмах поиска существует два возможных варианта окончания их работы: поиск может оказаться удачным — за- данный элемент найден в массиве и определено его месторасполо- жение, либо поиск может оказаться неудачным — необходимого элемента в данном объёме информации нет. Рассмотрим несколько типовых задач поиска, первое знаком- ство с которыми у вас состоялось ещё в основной школе. Пример 3. Последовательный поиск в неупорядоченном мас- сиве. Имеется массив a[1..n]; требуется найти элемент массива, рав- ный p. Алгоритм последовательного поиска в неупорядоченном мас- сиве может быть следующим. 1. Установить i = 1. 2. Если a[i] = p, алгоритм завершил работу успешно. 3. Увеличить i на 1. 4. Если i ≤ n, то перейти к шагу 2. В противном случае алго- ритм завершил работу безуспешно. Возможная программа, реализующая этот алгоритм на языке Pascal, имеет вид: const n=10; var a: array [1..n] of integer; i, p: integer; begin writeln('Ввод значений элементов массива:'); for i:=1 to n do read(a[i]); write('Ввод p: '); readln(p); i:=1; while (i<=n) and (a[i]<>p) do i:=i+1; 107 Структурированные типы данных. массивы §8 if i=n+1 then writeln('Искомого элемента в массиве нет') else writeln('Искомый элемент a[', i, '] = ', a[i]) end. Внимательно рассмотрите условие продолжения цикла. В каком случае выполнение цикла продолжается? В каких случаях осу ществляется выход из цикла? Запустите программу на выполнение в среде программирования Pascal. Как иначе можно решить эту задачу, например, с использованием цикла for? Напишите соответствующую программу. Оценим сложность рассмотренного алгоритма последовательного поиска, непосредственно зависящую от числа сравнений с иско мым элементом. В худшем случае искомый элемент окажется на последнем месте или не будет найден вообще. В таком случае не обходимо будет проделать n сравнений, т. е. сложность алгоритма будет равна О(n). Пример 4. Поиск максимумов и минимумов. Имеется массив a[1..n]; требуется найти значение наибольшего (наименьшего) элемента массива. Алгоритм поиска значения наибольшего (максимального) эле- мента в неупорядоченном массиве может быть следующим. 1. Установить значение текущего максимума равным первому исследуемому элементу (max := a[1]). 2. Установить счётчик равным 2 (i := 2). 3. Если исследованы ещё не все элементы (i <= n), то перейти к шагу 4, иначе алгоритм окончен (максимальный элемент равен max). 4. Если рассматриваемый элемент больше, чем текущий макси- мум (a[i] > max), то max присвоить значение a[i]. 5. Перейти к следующему элементу (увеличить i на единицу). 6. Перейти к шагу 3. Возможная программа, реализующая этот алгоритм на языке Pascal, имеет вид: const n=10; var a: array [1..n] of integer; i, max: integer; begin writeln('Ввод значений элементов массива:'); 108 Глава 2. алгоритмы и программирование for i:=1 to n do read(a[i]); max:=a[1]; i:=2; while (i<=n) do begin if a[i] > max then max:=a[i]; i:=i+1 end; writeln('Max=', max) end. Запустите программу на выполнение в среде программирования Pascal. Как иначе можно решить эту задачу, например, с использованием цикла for? Напишите соответствующую программу. Преобразуйте программу так, чтобы с её помощью можно было находить минимальный элемент массива. Какие изменения надо внести в программу для поиска индекса максимального (минимального) элемента массива? Самостоятельно оцените сложность рассмотренного алгоритма. 8.3. Проверка соответствия элементов массива некоторому условию Пример 5. Подсчёт количества элементов, удовлетворяющих некоторому условию. Зачастую бывает важно выяснить, сколько элементов, облада- ющих определённым свойством, содержится в массиве. Для решения этой задачи следует: 1) присвоить нулевое значение переменной, введённой для под- счёта количества элементов, удовлетворяющих заданному условию (k := 0); 2) организовать просмотр всех элементов массива: если просма- триваемый элемент удовлетворяет заданному условию, значе- ние переменной k увеличивать на 1. Фрагмент программы подсчёта количества элементов массива, например б→ольших некоторого числа p, имеет вид: k:=0; for i:=1 to n do if a[i]>p then k:=k+1; 109 Структурированные типы данных. массивы §8 Запишите полный текст программы и выполните её на компьюте ре для рассматриваемого в примере 8 массива а, состоящего из семи элементов, и числа p = 15. Как модифицировать программу, чтобы можно было вычислить сумму элементов массива, больших некоторого числа p? Пример 6. Проверка соответствия всех элементов массива некоторому условию. Для того, чтобы установить факт соответствия всех элементов массива некоторому условию достаточно: 1) подсчитать количество элементов массива, соответствующих заданному условию; 2) сравнить найденное количество с общим числом элементов массива и вывести соответствующий результат. Самостоятельно разработайте программу, позволяющую опреде лить, все ли элементы массива являются двузначными числами. Выполните её на компьютере для рассматриваемого в примере 8 массива а, состоящего из семи элементов. Пример 7. Проверка массива на упорядоченность. Рассмотрим алгоритм, позволяющий определить, упорядочены ли элементы массива a[1..n] по неубыванию, т. е. каждый эле- мент массива с 1-го по (n – 1)-й не больше последующего. Самый простой путь решения этой задачи — проверить, есть ли в массиве такие пары элементов, что a[i] > a[i + 1]. Если по- добные пары элементов есть, то массив не упорядочен по неубы- ванию, а если таких пар нет, то упорядочен. В программе будем использовать логическую переменную flag: • если flag = true, то массив упорядочен; • если flag = false, то массив неупорядочен. Ниже представлен фрагмент программы, реализующей этот алгоритм: flag:=true; for i:=1 to n-1 do if a[i]>a[i+1] then flag:=false; Запишите полный текст программы и выполните её на компьюте ре для рассматриваемого в примере 8 массива а, состоящего из семи элементов. Как можно решить эту же задачу путём подсчёта количества пар элементов массива, таких что a[i] > a[i + 1] (a[i] <= a[i + 1])? 110 Глава 2. алгоритмы и программирование 8.4. Удаление и вставка элементов массива Пример 8. Удаление из массива элемента с индексом k. Имеется одномерный целочисленный массив из семи элемен- тов: i 1 2 3 4 5 6 7 a[i] 10 12 5 8 4 15 20 Удалим из массива элемент с индексом k = 4, а все элементы, расположенные справа от него, сдвинем на одну позицию влево. Получим следующий целочисленный массив из шести элементов: i 1 2 3 4 5 6 a[i] 10 12 5 4 15 20 При удалении из массива любого из элементов размерность массива уменьшается на 1. Мы видим, что элементы с индексами от 1 до k – 1 не изме- нились. На место элемента с индексом k (4) переместился эле- мент, имевший индекс k + 1 (5), на место элемента с индексом k + 1 (5) переместился элемент, имевший индекс k + 2 (6) и т. д. В общем случае, фрагмент программы удаления из массива a[1..n] элемента с индексом k и последующим сдвигом всех рас- положенных справа от него элементов на одну позицию влево имеет вид: for i:=k to n-1 do a[i]:=a[i+1]; Запишите полный текст программы и выполните её на компьютере для рассмотренного выше массива а. Пример 9. Вставка в массив элемента на место с индексом k. Будем работать с тем же массивом из семи элементов. Но те- перь наша задача будет состоять в том, чтобы вставить в массив на место с индексом k = 4 (т. е. после элемента с индексом k – 1) ещё один элемент, имеющий значение 11. Получим следующий целочисленный массив из восьми эле- ментов: 111 Структурированные типы данных. массивы §8 i 1 2 3 4 5 6 7 8 a[i] 10 12 5 11 8 4 15 20 При вставке в массив ещё одного элемента размерность мас- сива увеличивается на 1. Это надо учесть при описании массива. Итак, a[4] := 11. Элементу a[5] следует присвоить то значе- ние, которое было у a[4], элементу a[6] — значение, которое было у a[5] и т. д. В общем случае, элементу a[k + 1] следует присвоить то значение, которое было у a[k]. Подумайте, что получится в результате выполнения следующих групп операторов присваивания: 1) a[4]:=11; a[5]:=a[4]; a[6]:=a[5]; a[7]:=a[6]; a[8]:=a[7]; 2) a[8]:=a[7]; a[7]:=a[6]; a[6]:=a[5]; a[5]:=a[4]; a[4]:=11; В общем случае, фрагмент программы вставки в массив a[1..n – 1] элемента на место с индексом k и сдвигом k-го, (k + 1)-го, …, (n – 1)-го элементов на одну позицию вправо имеет вид: for i:=n downto k+1 do a[i]:=a[i-1]; a[k]:=<значение элемента>; Запишите полный текст программы и выполните её на компьютере для рассмотренного выше массива а. Помните, что при описании массива надо учесть размерность массива, получающегося в ре зультате работы программы. 8.5. Перестановка всех элементов массива в обратном порядке Пример 10. Перестановка всех элементов массива a[1..n] в обратном порядке сводится к тому, что меняются местами первый и последний элементы, второй и предпоследний элементы и т. д. Перестановка нашего массива из семи элементов даст такой результат: i 1 2 3 4 5 6 7 a[i] 20 15 4 8 5 12 10 В общем случае, меняются местами элементы a[i] и a[n – i + 1]. 112 Глава 2. алгоритмы и программирование Вспомним, как можно произвести обмен значений между дву- мя переменными. Выполнение операторов: a[1]:=a[n]; a[n]:=a[1]; к желаемому результату не приводит. Самый простой вариант — использование вспомогательной переменной: r:=a[i]; a[i]:=a[n–i+1]; a[n–i+1]:=r; Выясним, сколько всего операций обмена следует произвести. Если произведена перестановка, например, первого и послед- него элементов, то одновременно произведена и перестановка по- следнего и первого элементов. Таким образом, если число эле- ментов массива чётное, то достаточно произвести n/2 операций обмена. Но что происходит, если массив содержит нечётное число эле- ментов? Например, в нашем массиве из семи элементов выпол- нялось три обмена, а четвёртый элемент, занимающий централь- ную позицию, оставался на своём месте. В общем случае число операций обмена при перестановке в обратном порядке всех n элементов массива определяется как n div 2. В общем случае, фрагмент программы по перестановке в обратном порядке всех элементов массива a[1..n] имеет вид: for i:=1 to n div 2 do begin r:=a[i]; a[i]:=a[n-i+1]; a[n-i+1]:=r end Запишите полный текст программы и выполните её на компьюте ре для рассмотренного выше массива а, состоящего из семи и из шести элементов. 8.6. Сортировка массива Сортировка — один из наиболее распространённых процессов современной обработки данных. 113 Структурированные типы данных. массивы §8 Сортировка — это распределение элементов массива в соответст вии с определёнными правилами. Под сортировкой (упорядочением) массива понимают пере- распределение значений его элементов в некотором определённом порядке. Порядок, при котором в массиве первый элемент имеет самое маленькое значение, а значение каждого следующего элемента не меньше значения предыдущего элемента, называют неубывающим. Порядок, при котором в массиве первый элемент имеет самое большое значение, а значение каждого следующего элемента не больше значения предыдущего элемента, называют невозрастающим. Цель сортировки — ускорить последующий поиск элементов, т. к. нужный элемент легче искать в упорядоченном массиве. Рассмотрим и проанализируем несколько алгоритмов сорти- ровки для решения следующей задачи. Дан одномерный массив целых чисел. Требуется отсортировать его так, чтобы все эле- менты были расположены в порядке неубывания: a[i] <= a[i + 1]. Обменная сортировка методом «пузырька» Своё название алгоритм получил благодаря следующей ассо- циации: если сортировать этим алгоритмом массив по неубыва- нию, то максимальный элемент «тонет», а «лёгкие» элементы поднимаются на одну позицию к началу массива на каждом шаге алгоритма. Пусть n — количество элементов в неупорядоченном массиве. 1. Поместим на место n-го элемента (a[n]) наибольший элемент массива. Для этого: 1) положим i = 1; 2) пока не обработана последняя пара элементов, т. е. (n – 1)-й и n-й элементы: • сравниваем i-й и (i + 1)-й элементы массива; • если a[i] > a[i + 1] (элементы расположены не по поряд- ку), то меняем элементы местами; • переходим к следующей паре элементов, сдвинувшись на один элемент вправо. 2. Повторяем пункт 1, каждый раз уменьшая размерность не- упорядоченного массива на 1, до тех пор, пока не будет об- работан массив из одной пары элементов (таким образом, на k-м просмотре будут сравниваться первые (n – k) элементов со своими соседями справа). 114 Глава 2. алгоритмы и программирование Пример 11. Есть массив: 5 4 3 2 1. На примере этого массива подсчитаем количество элементарных действий в вычислительном процессе алгоритма сортировки методом «пузырька»: • 1-я итерация: 4 3 2 1 5 (4 сравнения, 4 обмена); • 2-я итерация: 3 2 1 4 5 (3 сравнения, 3 обмена); • 3-я итерация: 2 1 3 4 5 (2 сравнения, 2 обмена); • 4-я итерация: 1 2 3 4 5 (1 сравнение, 1 обмен). Алгоритм закончил работу. Было сделано 10 сравнений и 10 обменов (4 + 3 + 2 + 1). Этот алгоритм легко запоминается, но на практике он исполь- зуется достаточно редко из-за квадратичной сложности, означаю- щей, что в общем случае количество выполненных сравнений и обменов сопоставимо с n 2 , где n — количество элементов массива. Попытайтесь самостоятельно запрограммировать алгоритм сорти ровки методом «пузырька». Сортировка выбором Сортировка выбором (в порядке неубывания) осуществляется следующим образом: 1) в массиве выбирается минимальный элемент; 2) минимальный и первый элементы меняются местами (первый элемент считается отсортированным); 3) в неотсортированной части массива снова выбирается мини- мальный элемент и меняется местами с первым неотсортиро- ванным элементом массива; 4) действия, описанные в пункте 3, повторяются с неотсортиро- ванными элементами массива до тех пор, пока не останется один неотсортированный элемент (его значение будет макси- мальным). Пример 12. Есть массив: 5 4 3 2 1. 1-я итерация: 1 4 3 2 5 (4 сравнения, 1 обмен). 2-я итерация: 1 2 3 4 5 (3 сравнения, 1 обмен). 3-я итерация: 1 2 3 4 5 (2 сравнения, 0 обменов). 4-я итерация: 1 2 3 4 5 (1 сравнение, 0 обменов). В общем случае алгоритм сортировки выбором имеет квадра- тичную сложность относительно операций сравнения и линей- ную сложность относительно операций обменов. Этот алгоритм целесообразно применять, когда операция обмена над элементами массива особенно трудоёмка (например, если элементом массива является запись с большим числом полей). 115 Структурированные типы данных. массивы §8 Приведём фрагмент программы, реализующей описанный выше алгоритм: for i:=1 to n-1 do begin imin:=i; for j:=i+1 to n do if a[j] per:=a[i]; a[i]:=a[imin]; a[imin]:=per; end; Запишите полный текст программы и выполните её на компьютере для рассмотренного выше массива. СамОе ГлаВнОе Из элементов простых типов в языке Pascal можно образо- вывать составные типы данных (структуры данных). Примером таких структур являются одномерные массивы. Массив в языке Pascal — это набор однотипных данных, при- чём количество этих данных фиксировано и определяется при описании массива. Все переменные, входящие в массив, имеют одно и то же имя — имя массива, а различаются они по индек- су — номеру (месту) в массиве. Перед использованием в программе массив должен быть опи- сан, т. е. должно быть указано имя массива, количество элемен- тов массива и их тип. Это необходимо для того, чтобы выделить в памяти под массив блок ячеек нужного типа. Чаще всего массив обрабатывается в цикле for. Но при работе с массивами можно использовать и другие циклы. К типовым задачам обработки одномерных массивов, решае- мым в процессе их однократного просмотра, относятся: • задачи поиска элемента с заданными свойствами, в том числе максимумов и минимумов; • проверка соответствия элементов массива некоторому условию (подсчёт количества или суммы элементов, удовлетворяющих некоторому условию; проверка соответствия всех элементов массива некоторому условию; проверка массива на упорядо- ченность и др.); • задачи на удаление и вставку элементов массива; • задачи на перестановку всех элементов массива в обратном порядке и т. д. |