В. Ю. Наумов Введение в информатику
 Скачать 2.05 Mb.
|
|
C и B используются переменные Nb и Nc, которые после окончания цикла будут равны, соответственно, числу элементов массива B и C. Одними из самых важных алгоритмов поиска в массивах являются алгоритмы отыскания экстремальных элементов в них. Простейшими примерами экстремальных элементов являются максимальный и минимальный по значению. Алгоритм поиска максимума и его места расположения (индекса) достаточно прост. Упрощенно его можно представить следующим образом: пусть есть кучка камней и нужно найти наибольший среди них. Для этого берем в левую руку первый камень и считаем что он самый большой. Далее берем в правую руку следующий камень и сравниваем его с тем, что находится в левой. Если камень в правой руке больше того, что в i=0; i A[i] > max max = A[i] Imax = i max=A[0] Рис. 4.8. Поиск максимума и его индекса 112 левой, то освобождаем левую руку и перекладываем в нее содержимое правой. Если ситуация обратная (в правой руке камень меньше чем в левой), то все оставляем без изменения. Правую руку освобождаем и вытаскиваем ею следующий камень для анализа. И так продолжаем до тех пор, пока не переберем все камни в куче. На языке алгоритма это будет выглядеть так (рис. 4.8): … int max=a[0], imax=0; for (int i=0; i { max=a[i]; imax=i; } … Алгоритм поиска минимума точно такой же, только знак «>» меняется на «<» и переменным даются имена, отражающие суть того, что ведется поиск минимального элемента (min и Imin). Не всегда поиск элементов происходит по одному условию. Иногда этих условий несколько. Если их совокупность можно объединить операциями алгебры логики и просто заключить в один предикатный узел, то все достаточно просто. Однако иногда не удается просто так включить сложное условие, поскольку может нарушаться свойство массовости алгоритма. Для этого поступают в каждом конкретном случае по-своему. Для примера рассмотрим достаточно типичную задачу такого характера: ПРИМЕР Найти наименьший элемент среди нечетных элементов массива. Для этой задачи составим тестовый пример: вход: 8 1 2 3 6 7 4 10 1 5 A выход: min = –7; Imin = 6. Если попытаться применить алгоритм, описанный ранее с добавлением в условие требования нечетности элемента, то результатом 113 будет min = –8, что явно неверно. Это связано с тем, что хотя и накладывается условие нечетности на элементы, оно не применимо к точке входа (к первому элементу массива). Для корректной работы алгоритма требуется правильно задать первый элемент, принимаемый за минимум. Для этого его сначала надо найти. В качестве алгоритма решения задачи можно предложить такой (блок-схема на рис. 4.9): int imin=0; while (a[imin]%2==0 && imin } else cout<<”\n no odd array elements”; Здесь при помощи цикла с предусловием сначала ищется первый нечетный элемент, после чего первый цикл прерывается и начинается второй с того места, где закончился предыдущий. А место это как раз находится там, где встретился нечетный элемент массива. Второй цикл – обыкновенный алгоритм поиска минимума с дополнительным условием нечетности. Данный алгоритм предполагает наличие хоть одного нечетного элемента в составе массива. 114 Для решения данной задачи можно предложить немного иной алгоритм, суть которого сводится к использованию всего одного цикла и переменной логического типа. Приведем решение задачи альтернативным способом целиком (рис. 4.10). A[Imin]%2==0 && Imin < N Imin = Imin+1 Imin = 0 i = Imin+1; i< N: i++ min = A[Imin] A[i] < min && A[i]%2!=0 min = A[i] Imin = i Imin < N ‘В массиве нет нечетных элементов’ Рис. 4.9. Поиск минимального среди нечетных в два последовательных цикла 115 Flag = FALSE A[i]%2!=0 i=0; i Min = A[ i ] IMin = i Flag = TRUE IMin = i A[ i ] < Min Min=A[ i ] Flag Вывод Min, IMin ‘В массиве все элементы четные’ Ввод A[i] i=0; i Начало Конец Рис. 4.10. Поиск минимального среди нечетных в один цикл 116 Программа будет такой: #include { int n,a[15]; cout<<”\nInput count of array’s elements”; cin>>n; for (int i=0; i } bool flag=false; int min, imin; for (int i=0; i { if (a[i] } } else { flag=true; min:=a[i]; imin:=i; } } if (flag) cout<<”\nmin=a[“< 4.4. Обработка массивов по индексам Достаточно часто критерием для обработки ячейки массива становится не ее содержимое, а месторасположение, т. е. индекс. Напри- мер, нужно взять и поменять местами последний элемент массива и средний элемент. Адрес последнего элемента – N. А вот со средним не все так однозначно, ибо для массива нечетной длины средний элемент один и 117 его индекс N/2+0,5, а для массива с четным количеством элементов серединой будут две ячейки: N/2 и N/2+1. Какую из них выбрать – зависит от условий задачи. Для простоты возьмем (N/2+0,5)-ю ячейку. Еще одной особенностью данной задачи является операция перестановки. Для обмена значениями разных ячеек требуется не потерять их. Для этого обычно используют третью переменную. Алгоритм подобен задаче обмена содержимым двух стаканов, скажем, с соком и с водой. Очевидно, что для исполнения задуманного нам потребуется третий, пустой стакан. Точно так же происходит обмен значениями произвольной пары переменных. Схема обмена представлена на рис. 4.11. В качестве еще одной иллюстрации описанной ситуации можно привести игру «пятнашки», в которой для возможности перемещения фишек предусмотрено пустое поле. Итак, перестановка последней ячейки массива и его среднего элемента может быть осуществлена следующим образом: int x = a[n-1]; a[n-1]= A[n/2]; a[n/2]= x; Здесь середина массива определяется как N/2 так как индекс массива всегда целое число, а операция деления «/» двух целых чисел засчет неявного приведения типов также вернет целое число. В качестве еще одного примера обработки элементов массива стоящих на определенных местах, можно привести алгоритм возведения в квадрат каждого второго элемента. Это можно сделать, как минимум, X Y Z 2 1 3 X ↔Y ? X ←Y Y←X Z←X X ←Y X ←Z X ↔Y !!! Рис. 4.11. Обмен значениями пары переменных в три действия 118 двумя способами. Первый способ предполагает перебор всех индексов массива и их анализ, а второй есть процесс прямого вычисления адреса интересующего элемента. Переборный вариант таков (рис. 4.12, а): for (int i=0; i (рис. 4.12, б). for (int i=0; i ПРИМЕР Переставить элементы массива в обратном порядке. Тестовый пример для этой задачи выглядит следующим образом: вход: i=0; i A[ i ] = A [ i ] 2 а) б) i=0; i 2 Рис. 4.12. Перебор всех индексов (а) и непосредственное вычисление (б) 119 0 3 5 9 11 7 6 A выход: 6 7 11 9 5 3 0 A Можно взять исходный массив и скопировать его во вспомогательный, а потом прочитать вспомогательный в исходный в обратном порядке. Но этот путь не является правильным, поскольку зря расходует память, ведь массивы занимают на порядки больше места, чем переменные простых типов. Поступим иначе. Будем читать массив одновременно с двух сторон, двигаясь к его центру; в процессе движения крайние элементы будем обменивать местами (если не остановимся на центре, а продолжим движение от одного края до другого, то, фактически, перестановка каждого элемента произойдет дважды и массив на выходе опять примет вид массива поданного на вход алгоритма). i=0; i –i-1] = buf A[i] = A[N –i-1] buf = A[i] а) i=0; i –1] = buf A[i] = A[N –1] buf = A[i] б) Рис. 4.13. Инверсия массива (а) и перестановка соседних элементов (б) 120 Реализация перестановки элементов такова (рис. 4.13, а): for (int i=0; i } Все очень просто. Для движения в прямом направлении используем индекс i, а для обратного прохода индекс вычисляется по формуле N–i–1. Действительно, проведем трассировку 16 алгоритма для описанного выше тестового примера и посмотрим, как ведут себя индексы: первая итерация: i=0, A[0] ↔A[6] (8–1-1 = 6) вторая итерация: i=1, A[1] ↔A[5] (8–2-1 = 5) третья итерация: i=2, A[2] ↔A[4] (8–3-1 = 4) Приведем еще один алгоритм парной перестановки элементов массива. ПРИМЕР Поменять местами соседние элементы массива. Вот что требуется сделать: вход: 0 3 5 9 11 7 6 A выход: 3 0 9 5 7 11 6 A Для решения задачи воспользуемся циклом с предусловием и алгоритмом обмена в три действия, при этом на каждой итерации меняя текущий индекс ячейки на 2. Вот такой алгоритм получается в результате (рис. 4.13, б): for (int i=0; i 16 Трассировка есть процесс записи значений переменных на каждом шаге работы программы 121 int buf = a[i]; a[i] = a[i-1]; a[i-1] = buf; } ПРИМЕР Произвести единичный циклический сдвиг элементов массива вправо. Под циклическим сдвигом понимается изменение положения каждого элемента на одну позицию (в данном случае вправо). Соответственно, последний элемент окажется за пределами массива, а на месте первого образуется вакансия. При циклическом сдвиге будет происходить перемещение содержимого последней ячейки в первую. Это можно легко понять, если представить массив в виде ленты транспортира. Тестовый пример таков: Вход: 0 3 5 9 11 7 6 A Выход: 6 0 3 5 9 11 7 A Алгоритм этого процесса следующий (рис. 4.14): int buf = a[n]; for (int i=n-1; i>1; i--) a[i] = a[i–1]; a[0] = buf; Стоит обратить внимание на факт использования вспомогательной буферной переменной для хранения элемента, который оказался вытесненным. Эффективно организовать алгоритм получается если i=N-1; i>1; i-- buf = A[N-1] A[ i ] = A[ i-1 ] A[0] = buf Рис. 4.14. Циклический сдвиг вправо 122 двигаться справа налево. Для этого цикл for пускается в обратную сторону. Если использовать прямой проход, то получится, что для корректной работы алгоритма потребуется не одна, а пара вспомогательных буферных переменных, да и число перестановок внутри цикла возрастет. Прямым проходом следует пользоваться при реализации циклического сдвига влево. Еще одним типом достаточно распространенных задач являются такие, у которых при решении требуется найти тот или иной индекс. ПРИМЕР Найти третий положительный элемент массива. Индекс третьего положительного будет храниться в переменной Ik3pol (рис. 4.15). int k=0, Ik3pol=0; for (int i=0; i { k++; if (k==3) k = 0; Ik3pol = 0 A[ i ]>0 i=0; i Ik3pol = i k == 3 Рис. 4.15. Поиск третьего положительного 123 Ik3pol=i; } Если в массиве меньше чем три положительных элемента, то переменная, хранящая индекс третьего положительного элемента Ik3pol останется равной нулю. Или, вот такая задача: ПРИМЕР Найти первый отрицательный элемент массива. Для ее решения можно воспользоваться алгоритмом предыдущей задачи, а можно немного упростить последовательность действий (на времени работы алгоритма на массивах малой длины это упрощение практически не отразится). Для этого воспользуемся тем свойством, что первый с начала отрицательный элемент является последним отрицательным с конца. Для использования этого свойства достаточно пустить цикл в обратном порядке; в результате получим последовательное изменение переменной IperOtr хранящей интересующий нас индекс при каждой IperOtr = 0 A[ i ]<0 i=N-1; i>=0; i-- IperOtr = i Рис. 4.16. Поиск первого отрицательного элемента 124 встрече отрицательного элемента. Последний раз такое изменение как раз произойдет на первом с начала элементе. Вот этот алгоритм (рис. 4.16): int IperOtr=0; for (int i=n-1; i>=0; i++) if (a[i]<0) IperOtr=i; Если в массиве все элементы положительные, то переменная IperOtr останется равной нулю. Можно рассмотреть целиком еще одну задачу, которая использует некоторые из вышеописанных алгоритмов. ПРИМЕР В одномерном массиве переставить в обратном порядке элементы, заключенные между максимумом минимумом. Решим задачу, воспользовавшись пошаговой детализацией алгоритма (рис. 4.17, а). Тестовый пример к этой задаче может быть, например, таким: вход: 2 5 10 2 4 5 7 9 1 3 0 2 7 Max=10, Imax=2, Min=0, Imin=10, Left=3, Right=9. выход: 2 5 10 3 1 9 7 5 4 2 0 2 7 Чтобы решить эту задачу, потребуется сразу после ввода массива найти положение максимума и минимума Imax и Imin (рис. 4.17, б). Сам же ввод (шаг 1-2) и вывод (как исходного (шаг 2-3), так и преобразованного (шаг 6-7)) здесь не расписывается, поскольку это стандартные алгоритмы и их блок-схемы изображены, например, на рис. 4.3. 125 Зная положение максимума и минимума теперь нужно определить, что из них встречается раньше для того, чтобы корректно задать границы изменения переменной цикла. Левая граница получила название Left, а правая – Right (рис. 4.17, в). Начало Конец Ввод массива A Вывод массива A до преобразования Поиск Imax и Imin Задание Left и Rigth Перестановка элем-ов между Left и Rigth Вывод массива A после преобразования 1 2 3 4 5 6 7 Imin = 0 A[ i ]>A[ Imax ] i=1; i Imin = i Imax = 0 A[ i ] Left= Imax + 1 Imax < Imin Right= Imin - 1 Left= Imin + 1 Right= Imax - 1 Шаг 4-5 Задание Left и Rigth а) в) б) Р ис. 4.17. Перестановка в обратном порядке элементов, расположенных между максимумом и минимумом: а) – общий алгоритм; б) – поиск Imin и Imax; c) – задание левой и правой границ 126 Далее следует сам алгоритм перестановки (шаг 5-6). Здесь можно воспользоваться перестановкой, описанной ранее, а можно рассмотреть несколько иную последовательность действий. Суть модифицированного алгоритма заключается в том, что не нужно следить за корректностью формул правой (Rigth) и левой (Left) границы диапазона. Нужно правильно задать начальные значения этим границам. Далее на каждой итерации правый индекс будет декрементироваться, а левый – инкрементироваться. Продолжаться это будет до тех пор, пока значения Left и Right не пересекутся (рис. 4.18, а). Альтернативный алгоритм тоже приводим, в нем нужно внимательно следить за индексами (рис. 4.18, б). Вот такая получилась программная реализация: #include Left A[Left]=A[Right] A[Right]=buf Right = Right - 1 Шаг 5-6 Перестановка элем-ов между Left и Rigth i=left; i (Right-Left)/2 buf=A[i] A[ i ]=A[Right-i+1] A[Right-i+1]=buf Шаг 5-6 Перестановка элем-ов между Left и Rigth ( альтернативная версия) а) б) Рис. 4.18. Перестановка в обратном порядке элементов между Left и Right: а) – с изменением границ и б) – непосредственно вычисляя граничные индексы 127 { int n,a[15]; cout<<”\nInput count of array’s elements”; cin>>n; for (int i=0; i } cout<<”\nArray a:”; for (int i=0; i } else { left=imin+1; right=imax-1; } while (left } cout<<”\nArray a:”; for (int i=0; i 128 4.5. Алгоритмы с использованием вложенных циклов Достаточно часто используются алгоритмы, для которых одного прохода по массиву недостаточно. Такие алгоритмы уже рассматривались ранее. Однако есть более сложные последовательности действий, в которых для каждого прохода требуется свой проход. В этом случае возникает вложенный цикл. Алгоритмы, использующие вложенные циклы, довольно сложны, но, в то же время, отличаются важностью. Рассмотрим наиболее распространенные из них. Самой часто встречающейся задачей, требующей использования вложенных циклов, является задача упорядочивания, или сортировки. Так, если дан, например, массив, состоящий из фамилий студентов, то логично их расположить в алфавитном порядке для удобства дальнейшего поиска. Такое упорядочивание будет называться алфавитным. Рассмотрим, как произвести сортировку числового массива. Вообще все сортировки можно свести к числовым. В случае с алфавитной ее разновидностью это легко сделать, если вспомнить, что в алфавите каждая буква имеет свой порядковый номер. Итак, у нас есть массив, произвольно заполненный числами. Требуется содержимое массива упорядочить по возрастанию, т. е. от меньшего к большему. Одним из самых простых методов сортировки является сортировка методом линейного поиска. Для этого просматриваем массив, находим в нем максимальный элемент, запоминаем его позицию и отправляем найденный максимум в конец массива. Значение элемента с конца направляется на место максимума. Далее организуем еще один проход по массиву, но уже последний элемент не рассматриваем, так как он стал на свое место. Алгоритм поиска максимума повторяем, но теперь будет произведен обмен с предпоследней ячейкой. После второго прохода – уже |