[МУЗЫКА] Рассмотрим, как можно проверить присутствие одновременно двух элементов в одномерном массиве. В этой задаче нам дана матрица A и массив B. В каждой строке нашей матрицы нам нужно поменять местами первый четный и последний нечетный элемент, если оба эти элемента будут присутствовать в нашем одномерном массиве. Начнем с постановки задачи. Для матрицы нам дано количество строк и столбцов, также даны сами элементы, а для массива B дана длина и элементы массива B. Все эти данные — целого типа. Далее у нас результатом может быть либо матрица A, в которой расположение некоторых элементов изменилось, либо сообщение о том, что у нас нет обмена в строке с некоторым номером. То есть для каждой строки, в которой обмена не было, мы будем выводить соответствующее сообщение. И ограничения на исходные данные — это ограничение на число строк и столбцов матрицы, а также на длину массива — они у нас совершенно стандартные. Далее рассмотрим пункт «связь». Мы должны рассмотреть каждую строку нашей матрицы последовательно. Для каждой строки мы должны найти номер столбца, где содержится первый четный элемент, и следующая строчка нашей связи касается именно этого элемента. У нас для этой строки будет существовать индекс j1, такой, что элемент строки, расположенной в j1-м столбце будет кратен двум. И при этом у нас не будет элементов, кратных двум, которые расположены до этого элемента. То есть j1 — это номер столбца, где у нас расположен первый четный элемент в текущей строке. Теперь нам нужен последний нечетный элемент этой же строки, назовем этот индекс j2. На этом месте расположен элемент, не кратный двум, то есть нечетный, и при этом если мы рассмотрим элементы, расположенные за этим элементом в этой строке, у нас с вами нечетных элементов среди них не будет. То есть j2 — это номер соответствующего столбца. Дальше мы должны сказать, что если оба эти элемента присутствуют в одномерное массиве, то есть существуют два индекса x и y, такие, что элемент на x-том месте равен у нас элементу матрицы, который является первым четным элементом, а на y-вом месте элемент равен последнему нечетному элементу этой строки, то тогда мы произведем перестановку через третью переменную, этот алгоритм нам с вами уже известен. И теперь мы с вами должны записать алгоритм. Вначале мы вводим все исходные данные, а затем мы с вами должны последовательно перебирать все номера строк в нашей матрице. Далее мы должны найти номер первого четного и последнего нечетного элемента. Для этого мы берем индексы j1 и j2 и присваиваем им начальное значение, равное 0. Эти индексы у нас с вами либо изменятся на какой-то номер в пределах от 1 до m, либо останутся равными 0. То есть, иными словами говоря, по конечному значению этих номеров мы сможем определить, нашли ли мы те два элемента, которые мы искали. Теперь мы должны найти индексы этих столбцов. Перебираем все столбцы последовательно, от 1-го до ma-го и проверяем, какой элемент находится на текущем месте. Если он четный, то тогда мы проверяем, первый ли это четный элемент. Если j1 не успело измениться с 0 на некоторое другое значение, то тогда мы запоминаем этот индекс и закрываем наше внутреннее условие. При этом мы понимаем, что данное присваивание может выполниться либо один раз, когда мы нашли первый четный элемент, либо не выполниться вовсе ни разу, если четных элементов у нас нет. Теперь мы рассматриваем условие, противоположное первому: если у нас элемент не является кратным двум, то есть он нечетный, то мы запоминаем j2. j2 будет меняться у нас при каждом нечетном элементе, то есть в конце концов это будет индекс последнего нечетного. Завершаем наше условие и закрываем цикл по столбцам. Для дальнейших действий нам нужно проверить, что мы нашли оба этих индекса, то есть и j1 и j2 у нас отличны от 0. В случае, если какой-нибудь из этих индексов не найден, то есть остался равным 0, тогда мы выводим сообщение о том, что нет обмена в текущей строке. Номер строки у нас будет выведен. Теперь, в противном случае, когда мы оба этих индекса нашли, мы должны проверить, что оба таких элемента присутствуют в массиве B. Здесь можно было бы пойти стандартным путем и проверить отдельно для каждого из этих элементов, присутствует он или нет. Но мы с вами поступим более рациональным способом. Мы с вами возьмем два флага булевских, которые будут показывать, найден ли первый и второй элемент. И как только мы с вами найдем элементы, равные обоим этим элементам в нашем одномерном массиве, так мы сможем завершить цикл, то есть это будет тоже досрочный выход. И в этом случае нам придется пройти по массиву B всего-навсего один раз. Итак, возьмем флаг 1 и флаг 2 и присвоим им начальные значения, равные false. Возьмем также t, равное 1 — это будет текущий номер элемента в массиве B. Теперь мы устраиваем цикл с досрочным выходом. Пока t меньше или равно nb, то есть массив B еще не кончился, и какой-нибудь из флагов, хотя бы один, равен false, то есть мы не нашли какой-нибудь из элементов. Если оба флага стали равным true, то в этом случае наш цикл сразу завершится. Теперь мы проверяем, не найден ли сейчас, на данном шаге, элемент, который равен какому-нибудь из наших: первому четному или последнему нечетному. Если у нас A[i, j1] равно текущему элементу массива B, то мы меняем на истину флаг 1. Если наш текущий элемент одномерного массива равен A[i1, j2], то мы меняем флаг 2. И затем выбираем следующий элемент в нашем массиве. При выходе из этого цикла нам нужно, чтобы оба наших элемента матрицы присутствовали в одномерном массиве. То есть наши оба флага должны превратиться в истину. Если оба флага истинны, то тогда мы производим обмен через третью переменную. Этот алгоритм мы с вами рассматривали, когда изучали методы сортировки. Начинаем с дополнительной переменной и затем по кругу переставляем значения наших переменных. Далее мы просматриваем противоположное условие. Если хотя бы один из этих элементов не найден, то мы снова выводим сообщение о том, что в нашей i-той строке нет обмена. Завершаем наше условие того, что оба элемента найдены, далее закрываем условие того, что у нас были четный и нечетный элемент в текущей строке и закрываем наш цикл, который у нас рассматривал нашу матрицу. Затем мы с вами выводим полученную матрицу на экран. Теперь посмотрим, как выглядит у нас программа, которая реализует этот алгоритм. Здесь у нас опять есть константа — максимальная длина массива, она равна 20, два типа для матрицы и для массива, оба эти массива, и одномерный, и двумерный — это массивы целых чисел. Далее мы объявляем переменные. Все те переменные, которые были у нас длинами и счетчиками, индексы j1 и j2, переменную для обмена, а также матрицу и массив. Кроме того, мы должны объявить два флага, при помощи которых мы проверяли присутствие. Затем производится ввод матрицы и массива. Этот момент можно посмотреть в предыдущей задаче, которую мы рассматривали на этом же занятии. Я не буду повторять этот фрагмент, потому что он совершенно аналогичен. После этого мы начинаем реализовывать наш алгоритм. Рассматриваем последовательно каждую строку нашей матрицы. Внутри этого цикла много действий, поэтому мы снова используем составной оператор, который начинается с ключевого слова begin. Затем мы ищем номера первого четного и последнего нечетного элемента текущей строки, берем два индекса j1 и j2, которые инициализируются нулем и далее проходим внутри этой строки по всем столбцам. Если у нас с вами элемент является четным, то мы проверяем, первый ли это такой элемент. Если это первый четный, то тогда мы с вами должны запомнить его индекс. В противном случае мы с вами j2 присваиваем j, то есть запоминаем индекс последнего нечетного элемента. Далее проверяем: если хотя бы какой-то из этих индексов остался равным 0, то мы выводим сообщение о том, что в этой строке обмена нет. В противном случае мы проверяем присутствие обоих найденных элементов в одномерном массиве. Два flag инициализируются «ложью». Текущий номер элемента в массиве b имеет начальное значение, равное единице. Организуем цикл с досрочным выходом: «пока» t ≤ nb, то есть мы не дошли до конца массива b, и хотя бы какой-нибудь flag равен false, то есть не найден хотя бы один из двух наших элементов, мы выполняем следующие действия. Если найден элемент, равный a [i, j1], то мы меняем первый flag на истину. Если сейчас мы нашли элемент, равный a [i, j2], то тогда меняем на истину второй flag. И затем увеличиваем текущий номер элемента в массиве b на 1. Далее проверяем, верно ли, что оба flag у нас поменялись на «истину». Если это не так — хотя бы какой-то flag равен false, то тогда мы выводим сообщение о том, что в этой строке у нас обмена нет. В противном случае мы производим обмен. Закрываем наше условие. Сначала последнее, затем предпоследнее. И закрываем наш внешний цикл. Вывод матрицы мы с вами рассматривали также в одной из предыдущих задач. Кроме того, он был рассмотрен отдельно в той лекции, где мы с вами впервые столкнулись с матрицами. Поэтому я с вашего разрешения повторять его не буду. И на этом наша программа заканчивается. Рассмотрим, как работает программа для реализации следующего алгоритма. Для каждой строки данной матрицы нам нужно поменять местами первый четный и последний нечетный элемент в том случае, когда оба этих элемента присутствуют в заданом одномерном массиве. Вначале мы с вами вводим исходные данные для массива и для матрицы. Этот фрагмент у нас с вами встречался уже несколько раз, поэтому мы не будем на нем подробно останавливаться. И далее начинаем решать задачу. Сначала мы последовательно перебираем все номера строк в нашей матрице. И нам с вами нужно определить, на каком месте находится первый четный и последний нечетный элемент. Инициализируем нулем оба номера этих элемента. Далее мы с вами перебираем все элементы текущей строки, то есть перебираем последовательно все номера столбцов. И проверяем, какой у нас элемент. Если элемент четный, тогда мы с вами должны проверить, первый ли он. Если это первый четный элемент, то тогда мы должны запомнить его индекс. И вот здесь есть важная подробность, на которую следует обратить внимание. Несмотря на то, что у нас в ветви «если» в первом условии присутствует только одно действие, тем не менее мы используем составной оператор begin end. С чем это связано? Дело в том, что наше «иначе» в данном случае должно относиться не к ближайшему второму «если», а к первому. Поэтому мы вынуждены использовать составной оператор. Иначе если элемент наш нечетный, то тогда мы запоминаем его номер. Далее мы проверяем, найдены ли наши элементы. Если хотя бы какой-то из номеров у нас остался равен 0, то значит в данной строке обмена нет. В противном случае мы должны проверить, присутствуют ли оба наших элемента в нашем одномерном массиве. Здесь мы используем два flag для проверки присутствия. Мы проходим по массиву B, пока не кончились его элементы, и пока хотя бы один из flag остается равным false. Если текущий элемент равен у нас a [i, j1], то мы меняем первый flag, если он равен a [i, j2], то второй, и выбираем следующий элемент. В том случае, когда хотя бы один из flag остался равным false, мы сообщаем о том, что нет обмена в этой строке. В противном случае мы с вами меняем местами наши два элемента и закрываем наше условие, а также закрываем все циклы. После чего выводим матрицу после обработки. Запустим нашу программу и посмотрим, на каких тестовых примерах мы можем проверить ее работоспособность. Первый тест: допустим, мы с вами возьмем матрицу размером 2 x 3, введем элементы так, чтобы в первой строке были и четные, и нечетные элементы. Допустим, 1 2 3. А во второй строке, к примеру, только четные: 4 6 8. И длину массива b возьмем, равную 4, и зададим элементы 1 2 3 4. В данном случае во второй строке обмена нет, потому что там нет ни одного нечетного элемента. А в первой строке он есть: элемент, равный 2 (первый четный), меняется с 3 (с последним нечетным). Теперь давайте запустим программу еще раз. Возьмем матрицу, допустим, размера 3 x 3. Введем элементы 1 2 3 4 5 6 7 8 и 9. А массив b возьмем, состоящим из четырех элементов, и введем туда данные: 7 8 9 0. Что мы в данном случае получим? В первой строке обмена нет, потому что у нас ни первый четный, ни последний нечетный не присутствуют в нашем одномерном массиве. Во второй строке у нас то же самое, а в последней строке обмен состоялся. Теперь давайте попробуем придумать матрицу, в которой обмен будет происходить в каждой строке. Допустим, я возьму матрицу 2 x 2, возьму ее элементы, равные 1 2 3 и 4. И сделаю так, чтобы все эти элементы присутствовали в одномерном массиве. В данном случае у нас с вами есть обмен в каждой строке. То есть мы с вами придумали наборы исходных данных – тесты – при помощи которых мы можем проверить, что наша программа работает правильно во всех возможных случаях. То есть наши тесты составлены так, чтобы можно было проверить, как выполняется каждое из проверяемых в программе условий. В данном случае у нас получилось, что при прохождении по всем условиям, результаты верны. То есть наша программа работает правильно. [МУЗЫКА] [МУЗЫКА]