[МУЗЫКА] [МУЗЫКА] Рассмотрим различные алгоритмы удаления элементов из массива. Например, решим следующую задачу. Нам дан массив X, длина которого равна k. Нам нужно из этого массива удалить элементы, которые расположены между первым минимальным и первым максимальным элементом. При этом дополнительный массив мы с вами использовать не будем. Начнем с постановки задачи. Исходные данные — это длина массива и сам этот массив. Результатом является тот же самый массив, длина которого изменится после удаления. И при этом у нас есть еще случай, когда у нас удаление невозможно, то есть когда наш минимальный и максимальный элементы расположены так, что между ними нет никаких элементов. При ограничениях на исходные данные таких, что длина массива должна быть натуральным числом и не превышать максимально возможной длины. Далее рассмотрим пункт «Связь». Для того чтобы решить нашу задачу, нам нужно найти номер минимального и номер максимального элемента, и затем рассмотреть, какие случаи у нас здесь возможны. Минимальный и максимальный элементы могут быть расположены разным образом. Во-первых, минимальный элемент может располагаться в массиве раньше, чем максимальный, либо наоборот. Также эти два элемента могут располагаться рядом, причем раньше может располагаться минимальный или раньше максимальный. И также есть вариант, когда эти два номера совпадают. Следовательно, нам нужно сначала найти эти номера, затем проанализировать взаимное расположение элементов и только потом уже решать задачу. После того, как эти номер найдены, нам важно ни где именно располагаются минимум и максимум, а какой из этих номеров меньше. Поэтому после нахождения мы можем выбрать минимальный из номеров, выбрать максимальный из номеров, присвоить их значения некоторым переменным и дальше рассматривать не все эти многочисленные случаи, а общий случай. Итак, в нашем пункте «Связь» мы должны написать, что, во-первых, мы должны найти первый максимальный элемент. Будет существовать номер максимума такой, что все элементы массива будут меньше или равны элементу с этим номером, но при этом этот максимум будет первым, то есть до него не будет существовать ни одного элемента, который был бы ему равен. Теперь аналогичную «Связь» мы записываем для минимального элемента, будет существовать номер минимума такой, что все элементы массива у нас меньше или равны этому элементу, но при этом до него нет ни одного элемента, который был бы ему равен. И теперь мы должны записать, собственно, удаление. Что мы должны сделать? Мы должны рассмотреть все элементы, которые расположены после максимального из этих номеров и сдвинуть их так, чтобы они расположились за элементом, номер которого минимален. И мы с вами делаем вычисления k1, которое будет минимальным из этих номеров, и k2, которое будет максимальным из них. И затем осуществляем, собственно, сдвиг. Вот здесь я попыталась изобразить картину, которая у нас получится. Оранжевым цветом выделены номера, которые я нашла: k1 и k2, и все элементы, начиная с k2 номера и до последнего будут перемещаться, располагаясь после элемента с номером k1. И затем длина массива будет уменьшена. Рассмотрим, по какому плану мы будем с вами решать эту задачу. То есть сначала я намечаю, какие действия и в каком порядке я должна буду выполнить, чтобы решить свою задачу. Вначале я должна ввести исходные данные. Затем я должна определить k1 и k2 — это номера минимума и максимума, и я должна упорядочить эти номера так, чтобы меньший из номеров оказался в переменной k1. Далее я проверяю, можно ли произвести удаление. Если элементы соседние или их номера одинаковые, тогда мы выводим сообщение о том, что удаление невозможно. В противном случае я делаю удаление путем сдвига, затем уменьшаю длину массива на количество удаленных элементов, и после этого я вывожу все те элементы, которые у меня остались. Некоторые фрагменты этого алгоритма мы с вами уже рассматривали и здесь есть такой новый пункт, как упорядочение номеров. В случае, если у меня k1 будет больше чем k2, мне нужно переставить значения в этих ячейках. Рассмотрим отдельно, как производится перестановка значений переменных. Предположим, у меня есть две переменных a и b со следующими значениями. Если попробовать записать два присваивания: a присвоить b, а b присвоить a, то этот вариант недопустим. Потому что, как только мы a присвоили b, значение, которое до этого было в ячейке a, у нас окажется утеряно, и для того чтобы действительно переставить значения переменных, мы должны завести третью дополнительную переменную. Итак, путь у меня есть две переменных: первая — a, а вторая — b, значения соответственно равны 2 и 5. Первым делом я беру дополнительную переменную и копирую туда значение из переменной a. 2 попадает в переменную c. Затем я могу a присвоить b. 5 из b копируется в переменную a. Теперь я беру 2, которая сейчас сидит в переменной c, то есть значение исходной переменной a, и перемещаю ее в переменную b. Теперь значения переменных поменялись местами. Обращаю ваше внимание, как легко запомнить порядок действий при перестановке значений переменных. Наши действия начинаются с дополнительной переменной, то есть сначала дополнительной переменной мы присваиваем значение, допустим, переменной a. Далее действия происходят по кругу: c присвоить a, потом a присвоить b, потом b присвоить c, то есть круг замкнулся, завершилось все на переменной c. Второй допустимый вариант перестановки — это начать с переменной b, то есть мы c присваиваем b, затем b присваиваем a, и потом a присваиваем c. Оба этих варианта абсолютно равнозначные. Итак, производим мы с вами удаления путем сдвига, то есть мы остающиеся элементы должны сдвинуть на соответствующие места. Мы можем производить удаления различными способами. Первый способ — это напрямую применить тот алгоритм, который мы с вами изучали в предыдущих задачах. Мы вводим переменную для количества оставшихся элементов, затем мы делаем цикл от k2 до k, то есть мы рассматриваем элементы, расположенные после большего из номера минимума и номера максимума, и на каждом шаге мы увеличиваем число оставшихся элементов, и на это место записываем тот элемент, который мы рассматривали на этом шаге. После того как цикл завершен, конечная длина массива у нас равна числу перемещенных элементов. Второй способ использует меньше переменных и учитывает тот факт, что мы каждый из остающихся элементов сдвигаем на определенное одинаковое число ячеек. У нас удаляется k2 − k1 − 1 элемент, то есть это количество элементов, расположенных между номерами k1 и k2. Чтобы лучше понять, как работает второй вариант, произведем для него трассировку, то есть подставим несколько значений переменных и посмотрим, какие присваивания у нас при этом будут получаться. При i = k2 подставляем в нашу формулу i = k2, дальше сокращаем все то, что может сократиться, и получаем, что X[k1 + 1] = X[k2]. То есть первый остающийся элемент располагается сразу за элементом с номером k1. На следующем шаге, когда i = k2 + 1, мы подставляем это значение в нашу формулу, сокращаем все то, что можно и получаем, что X[k1 + 2] = X[k2 + 1], то есть, иными словами говоря, второй остающийся элемент располагается через ячейку от элемента с номером k1. И после того как все шаги цикла пройдены, мы уменьшаем длину массива на количество удаленных элементов. И теперь запишем наш алгоритм в более подробном виде: не план действий, а каждое действие подробно. Начинаем мы с того, что вводим исходные данные, затем нам нужно найти номер минимума и номер максимума, этот алгоритм нам уже известен, я не буду его подробно комментировать. То есть мы рассматриваем начальные значения номеров, равные 1. Далее, от второго до последнего элемента, каждый текущий элемент сравниваем с минимальным и максимальным. Если нужно, то меняем соответствующий номер. И после того как этот цикл завершен, у меня в k1 находится номер максимума, а в k2 находится номер минимума. Теперь я должна проверить, правильно ли, то есть по возрастанию ли расположены эти значения. Если k1 окажется больше чем k2, то я произвожу перестановку значений этих переменных, чтобы в дальнейшем рассматривать общий случай, а не каждый случай отдельно. Теперь я произвожу анализ того, будет ли у меня результат. Если у меня k2 − k1 ≤ 1, иными словами говоря, если k1 = k2 или они отличаются ровно на 1, то есть это соседние ячейки, тогда Я вывожу сообщение о том, что нет удаления. В противном случае я должна сделать цикл, который будет перемещать оставшиеся элементы. Я делаю цикл от i: = k2 до конца массива, используя второй вариант удаления, перемещаю каждый элемент на соответствующее число ячеек, завершаю цикл, уменьшаю длину массива, затем вывожу оставшиеся элементы, закрываю условную конструкцию и завершаю весь алгоритм. Рассмотрим программу, которая реализует алгоритм удаления элементов, расположенных между первым минимальным и первым максимальным элементом исходного массива. Вначале мы с вами вводим длину нашего массива, затем сами элементы, для контроля выводим элементы на экран и начинаем вычислять номера минимального и максимального элемента. k1 у нас будет номер максимального элемента, а k2 — номер минимума. По нашему алгоритму найдётся первый минимум и первый максимум, так как у нас с вами используется и в том, и в другом случае строгое неравенство. Чтобы уменьшить количество рассматриваемых случаев, мы с вами упорядочиваем наши номера элементов так, чтобы k1 ≤ k2. В случае, если это не так, то есть k1 > k2, мы производим перестановку через третью переменную. Если разность между k2 и k1 будет меньше или равна единице, то в этом случае у нас не будет удаления. Этот случай предусматривает варианты, когда эти номера равны или они расположены рядом друг с другом. В противном случае делаем удаление. Мы рассматриваем элементы с номерами от k2 до k и на каждом шаге двигаем очередной элемент ближе к началу массива. Трассировку мы с вами рассматривали чуть раньше. Далее, мы уменьшаем количество элементов в массиве на число удалённых элементов и выводим то, что у нас осталось. Давайте попробуем запустить нашу программу. и проверить различные варианты тестов. Первый вариант будет такой: мы возьмём пять элементов и возьмём элементы, равные 0 −1 5 3 и −2 Вначале у нас выводится исходный массив, а затем то, что осталось после удаления элементов. Мы с вами видим, что удаляются элементы, расположенные между элементами, равными 5 и −2. То есть в этом случае у нас максимальный элемент располагался раньше минимального. Давайте попробуем сделать наоборот. Возьмём пять элементов массива, равные −1 2 3 4 и 6. В данном случае у нас минимум был первым элементом, а максимум — последним. И эти элементы — это единственное, что осталось в нашем массиве. Теперь попробуем взять три элемента, и возьмём все элементы, равные друг другу, например 1 1 1. В данном случае у нас нет удаления, потому что и минимум, и максимум у нас совпадают, они находятся на первом месте. Теперь попробуем получить случай, когда у нас минимум и максимум расположены рядом. Допустим, у нас четыре элемента, и они равны 1 10 −3 и 6. В данном случае у нас тоже нет удаления, потому что у нас 10 (максимальный элемент) и −3 (минимальный) расположены рядом. То есть мы с вами видим, что в данном случае у нас алгоритм работает при любых наборах исходных данных. При наборах исходных данных, которые обеспечивают случаи, когда удаления нет, и когда оно есть. [МУЗЫКА] [МУЗЫКА]
