[МУЗЫКА] [МУЗЫКА]
Продолжаем изучение алгоритма с досрочным выходом из цикла.
Рассмотрим задачу формирования нового массива,
в котором будут содержаться элементы исходного массива и каждый элемент
попадает в новый массив ровно один раз.
Например, рассмотрим массив a, состоящий из следующих элементов.
Во-первых, мы с вами должны записать первый элемент в новый массив b.
Затем мы последовательно рассматриваем элементы массива a и для каждого из них
проверяем, есть ли уже такой элемент в массиве b.
Например, второй элемент, равный 4 до сих пор не встречался в нашем новом массиве и,
следовательно, он будет туда записан на второе место.
Затем у нас 2.
Двойки у нас тоже еще не было и она занимает третье место в исходном массиве.
Далее у нас 1, мы видим,
что единица в нашем новом массиве уже есть и тогда мы ее туда записывать не станем.
Далее 2.
Двойка у нас тоже уже была.
Теперь рассматриваем элемент, равный 0.
Нуля нет, значит, мы его добавим в наш новый массив.
Далее у нас элемент равен −3.
−3 — это тоже новый элемент и он попадет в наш массив на очередное место.
И последний элемент, равный 0, уже был в нашем массиве.
Замечу, что здесь у нас всегда будет существовать результат,
потому что если исходный массив не пуст, то и новый массив не будет пустым.
Рассмотрим постановку задачи.
Нам дана длина массива и сам этот массив.
Результатом является наш новый массив, длина которого обозначена nb.
Проверяем исходные данные на допустимость.
Проверяем, что длина исходного массива —
это натуральное число и не превышает максимально возможной длины.
И затем рассмотрим пункт «Связь».
Мы будем записывать «Связь» следующим образом.
Для каждого элемента массива a, то есть для каждого номера в диапазоне от 1 до na,
будет существовать номер в массиве b, такой,
что элемент массива b равен элементу массива a.
Но при этом, если мы рассмотрим два различных индекса нашего нового массива,
то элементы на этих местах обязательно будут различны.
Теперь посмотрим, как записывается алгоритм решения этой задачи.
Формируем новый массив, состоящий из различных элементов исходного массива.
Вводим исходные данные.
Длине массива b присваиваем начальное значение, равное 0,
и начинаем перебирать все номера элементов в массиве a.
После того как мы выбрали номер, проверяем,
есть ли уже такой элемент в массиве b.
Берем текущий номер j, который будет индексом элемента в массиве b.
Вначале он равен 1 и проверяем в заголовке цикла два условия: пока ai ≠ bj,
то есть элементы разные, и j ≤ nb,
то есть мы не дошли до конца массива b, увеличиваем j на 1.
Наш цикл завершится в одном из двух случаев: или мы нашли элемент,
равный текущему, или мы вышли за границу массива.
Нам нужно, чтобы элемент отсутствовал в новом массиве,
то есть нас интересует случай, когда при выходе из цикла j будет больше nb,
тогда мы должны наш элемент массива a, расположенный на текущем месте,
записать в новый массив на очередное место.
То есть длина массива b увеличивается на 1 и на это место записывается наш элемент.
Закрываем наше условие, закрываем наш цикл и выводим результат.
Теперь рассмотрим, как будет выглядеть наш алгоритм, записанный в виде программы.
Для массива мы объявим тип.
Наш массив будет состоять из 20 максимум целых элементов.
Далее у нас есть два массива этого типа и, кроме того, мы здесь должны
еще объявить все счетчики которые у нас с вами были использованы в нашем алгоритме.
Далее мы вводим наши исходные данные.
Сначала мы запрашиваем длину массива.
Обратите внимание, что здесь у нас используется цикл с постусловием (repeat,
until) и мы будем повторять в нем два действия: мы будем выводить сообщение о
том, что нам нужна длина массива.
Затем мы будем считывать данные в переменную na.
И так мы будем продолжать наше действие до тех пор,
пока у нас na не будет положительным числом и не превышать
максимально возможного значения, равного 20.
Теперь мы вводим элементы массива.
Перебираем все номера элементов исходного массива от 1 до
значения длины и читаем их по одному.
После этого инициализируем нулем длину массива b.
Далее мы перебираем последовательно все номера элементов в массиве
a и на каждом шаге мы проделываем следующие действия.
Берем j = 1 и пока наши элементы разные и массив b не кончился,
мы выбираем следующий элемент в этом массиве.
Затем проверяем условие того, что наш элемент массива a не найден в массиве b,
то есть если j > nb, то тогда мы поделываем два действия: увеличиваем длину
массива b и записываем наш текущий элемент массива a в массив b на это место.
После чего наше условие закрывается, а затем завершается цикл.
Обращаю ваше внимание,
что при этом варианте вывода все элементы массива будут расположены в одной строке.
После этого программа завершается.
Рассмотрим программу, которая реализует алгоритм формирования нового массива b,
который содержит все элементы исходного массива a по одному разу.
Вначале мы вводим исходные данные для массива a, то есть количество
элементов и сами элементы, и затем мы формируем новый массив b,
который содержит все элементы исходного массива по одному разу.
Вначале количество элементов в массиве b = 0.
Далее мы проходим по всем номерам элементов в массиве a и проверяем,
что текущий элемент массива a отсутствует в массиве b.
Если j у нас будет больше nb, то это условие отсутствия, мы
увеличиваем длину массива b и записываем на очередное место элемент массива a.
В данном случае результат будет существовать всегда при непустом
исходном массиве.
Запустим нашу программу и введем те исходные данные,
которые мы использовали при рассмотрении этого алгоритма.
Итак, количество элементов массива a у нас было равно 8.
И элементы у нас были следующие: 1
4 2 1 2
0 −3 и 0.
Мы с вами видим, что массив получился состоящим из
следующих элементов: 1 4 2 (вторая 1 в массив не попала,
потому что такой элемент в нашем массиве уже есть, 2 также не попадает туда),
затем 0 −3 и второй 0 в массив также не записывается.
Если мы запустим программу еще раз и рассмотрим массив,
элементы которого не повторяются, допустим, три элемента: 2 5 и 0,
то в этом случае длина нового массива будет равна длине исходного массива.
То есть в этом случае наша программа также работает правильно.
[МУЗЫКА]
[МУЗЫКА]