Векторы и матрицы

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

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

1. Для поиска минимального значения подматрицы A' (i, j) для каждых i и j «просканировать» всю подматрицу. Это приводит к следующему решению (дадим лишь фрагмент программы — «тело» алгоритма):

Очевидно, для решения задачи потребуется порядка (тп)² операций сравнения и присваивания, то есть трудоемкость алгоритма полиномиальная, четвертого порядка от линейного размера матрицы.

2. Нетрудно видеть, что при движении по матрице слева направо и сверху вниз достаточно сравнивать значение каждого элемента с уже измененными его «соседями» слева и сверху, так как они уже содержат в себе минимальное значение среди элементов соответствующих подматриц, с его собственным значением. Особый случай — первая строка, где сравнение идет только с соседом справа, и первый столбец, где сравнение идет только с соседом сверху. Полное решение задачи может выглядеть следующим образом:

3. Тот же алгоритм с использованием технологии модульного программирования более лаконичен и нагляден:

4. Еще более лаконичное решение можно получить, если не выделять в отдельные алгоритмы обработку первой строки и первого столбца. Для этого достаточно «окаймить» матрицу сверху и слева достаточно большими числами, например, 10³⁸ (при типе элементов матрицы Real). Приведем фрагменты программы, использующей описания и блоки предыдущего варианта:

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

Задачи по теме «Векторы и матрицы»

5.1 (7 б.) Строки матрицы А(т, п) заполнены не полностью в массиве L(m) указано количество элементов в каждой строке. Переслать элементы матрицы построчно в начало одномерного массива Т(т п), подсчитать их количество.

5.2 (8 б.) Улитка. Матрицу М(т, п) заполнить натуральными числами от 1 до т п по спирали, начинающейся в левом верхнем углу и закрученной по часовой стрелке.

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

5.4 (7 б.) Куб состоит из п³ прозрачных и непрозрачных элементарных кубиков. Имеется ли хотя бы один просвет по каждому из трех измерений? Если это так, вывести координаты каждого просвета.

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

5.5 (8 б.) Используя ту же структуру данных, что и в предыдущей задаче, построить полностью непрозрачный куб, используя ровно п² непрозрачных элементарных кубиков.

5.6 (8 б.) В матрице А(т, п) каждый элемент заменить минимальным среди элементов подматрицы A'(i,j), расположенной в левом верхнем углу матрицы А.

5.7 (8 б.) Нарастающий итог. Каждый элемент матрицы А(т,п) заменить суммой элементов подматрицы A'(i,j), расположенной в левом верхнем углу матрицы А.

5.8 (9 б.) Многочлены Р_т(х) и Q (x) заданы массивами своих коэффициентов. Найти частное и остаток от деления Р_т(х) на Q (x) (в виде массивов коэффициентов).

5.9 (8 б.) Ввод элементов матрицы А(т, п) осуществляется в произвольном порядке тройками чисел < i, j, >. Признаком конца ввода служат три нуля: < 0,0,0 >. Проверить корректность такого ввода: все ли элементы введены, нет ли попытки повторного ввода или указания несуществующих координат i и j.

Указание. Разрешается выделение дополнительного (рабочего) массива такой же размерности, что и исходный массив, например, логического типа для хранения признаков «заполненности» элементов матрицы.

При попытке повторного ввода пользователю предоставляется выбор: оставить старое значение или заменить его новым. По завершении ввода матрица распечатывается; при этом невведенные элементы замещаются пробелами или другими символами.

5.10 (8 б.) Матрица А вводится извне (с клавиатуры, из файла) построчно; число строк велико и заранее неизвестно, но различных строк не более т. Расположить ее в выделенном массиве; при этом повторяющиеся строки включать единожды.

5.11 (7 б.) Задача Иосифа [20]. По кругу располагаются п человек. Ведущий считает по кругу, начиная с первого, и выводит («казнит») m-го человека. Круг смыкается, счет возобновляется со следующего после «казненного»; так продолжается, пока «в живых» останется только один человек. Найти номер оставшегося «в живых» человека, а также для заданного п найти такое т > 1, при котором «в живых» останется первый.

5.12 (8 б.) Матрицу А(т, п) заполнить следующим образом. Для заданных k и l элементу присвоить значение 1; элементам, окаймляющим его (соседним с ним по вертикали, горизонтали и диагоналям) — значение 2; элементам следующего окаймления — значение 3 и так далее до заполнения всей матрицы. Примечание. Алгоритм не изменится, если координаты элемента (несуществующего) k и l находятся за пределами матрицы.

5.13 (8 б.) Работа комбайнера. Матрицу К(т, п) заполнить следующим образом. Элементам, находящимся на периферии (по периметру матрицы), присвоить значение 1; периметру оставшейся подматрицы — значение 2 и так далее до заполнения всей матрицы.

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

5.15(8 б.) Сглаживание. Каждый элемент вектора А(п) (кроме двух крайних) заменить выражением:

5.16 (9 б.) Замочная скважина. Даны мозаичные изображения замочной скважины и ключа. Пройдет ли ключ в скважину? То есть даны матрицы K(m ,n ) и L(m ,n ), т >т₂, n > п₂, состоящие из нулей и единиц. Проверить, можно ли наложить матрицу L на матрицу К (без поворота, разрешается только сдвиг) так, чтобы каждой единице матрицы L соответствовал нуль в матрице К, и если можно, то как (на сколько и в каком направлении следует подвинуть матрицу L по матрице К до выполнения условия)?

(12 б.) Развитие задачи. «Ключ» разрешается поворачивать на угол, кратный 90°; его можно также зеркально отображать.

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

5.18 (7 б.) Содержимое квадратной матрицы А(п, п) повернуть на 90° по часовой стрелке, считая центром поворота центр симметрии матрицы.

5.19 (6 б.) В каждом столбце и каждой строке матрицы Р(п, п) содержится строго по одному нулевому элементу. Перестановкой строк добиться расположения всех нулей по главной диагонали матрицы.

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

5.21 (86.) Рациональное алгебраическое выражение , задано массивом А(п) коэффициентов а и массивом К(n) соответствующих показателей степеней k Привести в нем подобные члены и сформировать массив коэффициентов полученного многочлена Р_т(х) (по возрастанию степеней х).

5.22 (6 б.) Касса. В массиве К(п) в порядке убывания представлены достоинства денежных знаков (купюр и монет) валютной системы некоторой страны. Реализовать выдачу в этой системе заданной суммы т минимальным числом денежных знаков.

5.23 (10 б.) Соседи. Из элементов массива A(2n) получить массивы В(п) и С(п) следующим образом. Выбрать в массиве А два наиболее близких по значению элемента; меньший из них поместить в массив В, а больший — в массив С. Продолжить выбор из оставшихся элементов до полного заполнения массивов В и С.

5.24 (8 б.) Колокол. В массиве А(п) наименьший элемент поместить на первое место, наименьший из оставшихся — на последнее место, следующий по величине — на второе место, следующий — на предпоследнее и так далее — до середины массива.

5.25 (7 б.) Матрица К(т, т) состоит из нулей и единиц. Найти в ней номера (индексы) хотя бы одной строки или хотя бы одного столбца, не содержащих единицы, либо сообщить, что таковых нет.

5.26 (6 б.) С внешнего устройства (с клавиатуры, из файла) вводятся последовательно числа, количество которых велико и заранее неизвестно. Требуется сохранять и в процессе ввода каждого числа распечатывать не более т последних введенных чисел (в порядке их поступления).

5.27 (7 б.) На внешнем носителе (в файле) построчно подготовлены элементы матрицы А(т, п). Известно, что в ее первом столбце не более k ненулевых элементов (k << т).

Ввести строки, для которых а 0, и сформировать из них в памяти матрицу B(k, n). Вся матрица А(т, n) слишком велика и «замусорена», чтобы хранить ее в памяти.

5.28 (7 б.) На внешнем носителе (в файле) построчно подготовлены элементы матрицы А(т, п). Для заданных k и l ввести элементы k -йи l -йстрок (пропуская промежуточные) и найти их скалярное произведение:

- Вся матрица слишком велика, чтобы хранить ее в памяти.

5.29 (7 б.) Матрица А(т, п) вводится построчно; строки поступают в произвольном порядке: указывается номер строки и значения ее элементов. Проверить корректность такого ввода: все ли строки введены и не было ли попытки повторного ввода одной и той же строки.

Разрешается использование одномерного рабочего массива для хранения номеров введенных строк или логических или двоичных переменных — признаков того, что соответствующая строка определена (введена) индикатором определенности строк.

5.30 (8 б.) Латинский квадрат. Латинским квадратом порядка п называется квадратная таблица размером п п, каждая строка и каждый столбец которой содержат все числа от 1 до п. Проверить, является ли заданная целочисленная матрица латинским квадратом.

5.31 (8 б.) Магический квадрат. Магическим квадратом порядка п называется квадратная таблица размером п п, состоящая из чисел 1,2,..., п² так, что суммы по каждому столбцу, каждой строке и каждой из двух диагоналей равны между собой. Проверить, является ли заданная целочисленная квадратная матрица магическим квадратом.

5.32 (15 б.) Развитие задачи. Реализовать любой алгоритм построения магического квадрата заданного размера.

5.33 (9 б.) В трехмерном массиве К(l, т, п), состоящем из нулей и единиц, хранится сеточное изображение некоторого трехмерного тела. Получить в двумерных массивах три проекции (тени) этого тела.

5.34 (10 б.) Многочлены Р (х) и Q_m(x) заданы своими коэффициентами. Определить коэффициенты их композиции — многочлена P_n(Q_m(x)).

5.35 (8 б.) Отсев. Удалить в заданном массиве Х(п) «лишние» (кроме первого) элементы так, чтобы оставшиеся образовали возрастающую последовательность (за один просмотр массива).

5.36 (8 б.) Среднестатистическим назовем элемент массива, если для него модуль разности его значения и среднего арифметического элементов массива достигает минимума. Аналогично, уникальным будем называть элемент, для которого такой модуль разности достигает максимума. В заданном массиве Х(т) найти номера (индексы) среднестатистического и уникального элементов.

5.37 (9 б.) Автостоп — 3. Из пункта А в пункт В, между которыми s км, выехал велосипедист с постоянной скоростью v₀ км/ч. Одновременно с ним в том же направлении другой путник решил добраться «автостопом» — на разных видах попутного транспорта. Перед каждым участком пути он минут «голосует», затем движется t часов со скоростью v км/ч (величины , t , v , i=l,..., п. заданы в соответствующих массивах). В каких точках пути (в какие моменты времени) путники смогут помахать друг другу рукой?

Линейный поиск

В задачах этого раздела требуется найти в массиве элемент, группу элементов или фрагмент массива, которые отвечают заданным требованиям. При этом, как правило, нет необходимости сортировать массив или выделять дополнительные разные массивы размерности того же порядка, что и заданный. Еслии требуется найти фрагмент массива, обладающий какими либо свойством («цепочку» элементов), следует в качестве результата показать не только сам фрагмент, но и его местонахождение (индексы первого и последнего элементов фрагменты) в массиве.

Если исходный массив упорядочен, целесообразно проверить. при вводе упорядоченность и применять бинарный подход(метод дихотомии, или метод деления пополам).

Пример. Дана матрица А(т, п), состоящая из нулей и единиц. Требуется найти в ней строку, содержащую хотя бы один ноль.

Встречаются следующие подходы к решению.

1. Переставить строки матрицы, упорядочив их по возрастанию количества единиц. Тогда если первая строка содержит нули, она и будет искомой — самой «нулевой».

2. Подсчитать сумму элементов каждой строки матрицы; среди строк выбрать такую, для которой сумма меньше п.

3. Подсчитать количество нулей в каждой строке и выбрать такую строку, в которой оно больше нуля.

4. Найти в матрице первый попавшийся нуль. Строка, его содержащая, и будет искомой.

Все четыре подхода должны дать правильный результат, но сильно различаются по эффективности. Кроме того, первый подход носит «хирургический» характер, так как матрица в результате такого «поиска» искажается до неузнаваемости и становится непригодной для других приложений.

Рассмотрим житейскую ситуацию с подобной задачей. На оккупированной врагом территории действует группа партизан. Юный разведчик получает задание: проверить, не занята ли некоторая деревушка фашистами, то есть не найдется ли среди домов этой деревни такой дом, в котором есть хотя бы один фашист?

Какой из подходов вы предложите разведчику? В первом варианте ему, очевидно, пришлось бы переселить все семьи (вместе с расквартированными фашистами) по убыванию количества фашистов. Как отнесутся к этому испытуемые? Во втором и в третьем случаях разведчик должен тщательно обследовать все дворы, подсчитывая хозяев или «гостей», и лишь в четвертом случае разведка ведется до обнаружения первых признаков наличия «гостей», а затем — «дай бог ноги». Очевидно, когда речь идет о жизни и смерти, мы выбираем единственно разумное решение, а компьютер — «он железный», пусть работает, на модельных примерах результат будет найден в мгновение ока даже при самом неэффективном алгоритме. Итак, реализуем четвертый подход — поиск в матрице строки, содержащей хотя бы один нуль.

Тестирование. При испытании программы ее надо обязательно) проверить на следующих (небольших) матрицах:

■ не содержащих нулей;

■ содержащих нули во всех строках;

■ содержащих нуль в первой строке.

Кроме того, для настройки ввода-вывода надо предложить матрицу из 20 строк и матрицу из 40 столбцов.

Задачи по теме «Линейный поиск»

6.1 (7 б.) Седловой точкой в матрице называется элемент, являющийся одновременно наибольшим в столбце и наименьшим в строке: . Седловых точек может быть несколько (в этом случае они имеют равные значения). В матрице А(т,п) найти седловую точку и ее координаты р, q либо установить, что такой точки нет.

6.2 (7 б.) В матрице К(п) первый элемент каждой строки — шифр детали, остальные элементы — характеристики этой детали. Выявить, распечатать и удалить из матрицы номера строк с совпадающими шифрами и несовпадающими характеристиками. Вывести также оставшуюся после резекции матрицу.

6.3 (9 б.) Задано п линейных функций: .Найти минимум «верхней огибающей» этих функций, то есть кусочно-линейной функции .

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

6.4 (8 б.) Поле размером т п заполнено прозрачными и непрозрачными кубиками. Найти все столбцы поля, все непрозрачные кубики которых невидимы для наблюдателя, расположенного слева.

6.5 (9 б.) Поле размером т п заполнено прозрачными и непрозрачными кубиками. Удалить (сделать прозрачными) все непрозрачные кубики, видимые хотя бы с одной из четырех сторон (видимость анализируется до удаления какого-либо кубика).

6.6 (10 б.) В заданном массиве А(п) найти i и j такие, что

максимально.

6.7 (8 б.) В массиве А(1), все элементы которого различны, найти и удалить п наименьших элементов, «поджимая» массив к началу и сохраняя порядок следования остальных элементов (n<< l).

6.8 (7 б.) В массиве T(k) найти первый и последний нулевые элементы.

6.9 (7 б.) В массиве L(m) найти наиболее длинную цепочку, состоящую из одних нулей.

6.10 (10 б.) Матрица L(n, k) состоит из нулей и единиц. Найти в ней самую длинную цепочку подряд стоящих нулей по горизонтали, вертикали или диагонали.

6.11 (9 б.) В целочисленном массиве К(п) много повторяющихся элементов. Найти (в процентах) частоту появления каждого из т наиболее часто встречающихся элементов (т «п).

6.12 (8 б.) Даны два целочисленных массива К(т) и L(n). Найти наибольший элемент массива К, не имеющий себе равных в массиве L.

6.13 (8 б.) Среди элементов массива Z(m) найти k (к «т) наибольших. Поиск осуществить за один проход (просмотр) массива Z

6.14 (7 б.) В целочисленном массиве L(n) найти наиболее длинную цепочку одинаковых подряд стоящих элементов.

6.15 (9 б.) В массиве M(k) много совпадающих элементов. Найти количество различных элементов в нем (не упорядочивая массива).

6.16 (6 б.) Элементы массива М(п) упорядочены по неубыванию (см. раздел 15). Для заданного х найти наименьшее k такое, что т_к < х < т_к+1, либо показать (выдать сообщение), что такового нет. Для поиска полезно применить метод дихотомии (метод деления отрезка пополам).

6.17 (5 б.) В каждой строке матрицы А(п, п) найти наибольший элемент и поменять его местами с соответствующим диагональным элементом.

6.18 (8 б.) Последовательность а , а₂,...,а_к, называется пилообразной, если а < а_г > а₃ < а₄ >…> а_к либо а > а_г < < а₃ > а₄ <... < а_к. В массиве А(m) найти самую длинную пилообразную последовательность.

6.19 (7 6.) Последовательность а , а_г,...,а_к называетсямонотонной, если а < а₂ <.... < а_к или а >а_г>... > а_к. В массиве А(т) найти самую длинную монотонную последовательность.

6.20 (6 б.) Утверждается, что массив А(т) целиком (как последовательность) встречается в массиве В(п), п>т. Найти место массива А в массиве В или показать, что его в массиве В нет.

6.21 (9 б.) Найти все числа, каждое из которых встречается в каждой строке матрицы А(т, п).

6.22 (7 б.) Найти все числа из массива В(п), встречающиеся более чем в одной строке матрицы А(т, п).

6.23 (8 б.) Найти все числа, встречающиеся в массиве Р(т) строго два раза (не упорядочивая самого массива).

6.24 (7 б.) В массиве Z(n ) найти наиболее длинную цепочку стоящих подряд попарно различных элементов.

6.25 (8 б.) В массиве Р(п) найти самую длинную последовательность, которая является арифметической или геометрической прогрессией.

6.26 (8 б.) Медиана. В массиве А( 2 п + 1 ), не содержащем одинаковых элементов, найти средний по величине элемент, то есть такой, что в массиве А ровно п элементов меньше его и столько же элементов больше его. Массив А сохранить (не сортировать), дополнительных массивов не использовать.

6.27 (7 б.) Результаты забега в массовом кроссе представлены целочисленной матрицей К(п,4), где п — число участников; k k — момент старта i-го участника в минутах и секундах соответственно; k k — аналогично момент финиша, i = 1,2,..., п. Найти номера (индексы) трех призеров забега и их результаты (за один просмотр матрицы).

6.28 (7 б.) В массиве Н(п) хранятся значения высот некоторого профиля местности (ее вертикального сечения) с постоянным шагом по горизонтали. Найти области (номера точек измерения высоты), невидимые для наблюдателя, находящегося в точке h .

6.29 (7 б.) Имеются результаты п ежедневных измерений количества выпавших осадков. За какую из недель (отрезок времени длиной 7 дней), считая с начала периода измерений, выпало наибольшее количество осадков?

6.30 (6 б.) Дана таблица выигрышей денежной лотереи: К(п) — массив номеров выигравших билетов (упорядочен по возрастанию); S(n) — суммы выигрышей. Определить суммарный выигрыш для пачки купленных билетов с номерами 1 ,1 ,...,1 .

6.31 (9 б.) Крестики-нолики. Клеточное поле размером т п есть результат игры в крестики-нолики на «бесконечном» поле. Проверить, не закончена ли игра выигрышем «крестиков»? Считается, что «крестики» выиграли, если на поле найдется по горизонтали, вертикали или диагонали цепочка, состоящая подряд из 5 крестиков.

6.32(8 б.) Проверить, не является ли заданная матрица А(т,п) осе- или центросимметричной. При отрицательном ответе — найти хотя бы одну группу элементов-нарушителей симметрии.

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

(12 б.) Развитие задачи. Числа хранятся в линейном односвязном списке (см. п. 15) или в файле с последовательным доступом. Найти наиболее эффективные алгоритмы для случаев прямого и последовательного доступа с возможностью использовать рабочий массив размерностью п или без нее.

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

6.35 (10 б.) Черный квадрат. В матрице А(т,п), состоящей из нулей и единиц, найти квадрат заданного размер; (квадратную подматрицу), состоящий целиком из нулей

(16 б.) Развитие задачи. Найти квадрат наибольшей размера.

Часть III