Задача к ЕГЭ по информатике на тему «соседние элементы, проверка условий» №6

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от -10000 до 10000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти наибольшее количество одинаковых элементов, расположенных подряд. Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных. В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Cython 0.20). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в приведённых фрагментах. Индексация элементов в массиве начинается с нуля.

|Бейси-к-------------------------|Python------------------------------|А-лгори-тми-ческий-язы-к-| |--------------------------------|------------------------------------|-------------------------| |CON ST N ASIN TEGER = 30 |# допуск ается такж е |ал-г | |DIM A (0TON − 1)ASLON G |# испол ьзовать три |нач- | |DIM IASLON G |# ц елочисл енны е п еремен ны е i,t,k ц-елN = 30 | | T ASLON G |a = [] | ц елтабa[0 : N − 1] | | | | ------- | | KASLON G |n = 30 | ц-елi,t,k | |FORI = 0T ON − 1 |foriinrange (0,n) : | н-ц-дляiот0д-оN − 1 | | IN P U TA (I) | a.append (int(input ())) | вводa[i] | |N EXT I |... | к-ц- | |... | |... | | | | | -EN-D------------------------------------------------------------------кон-----------------------

Например, для исходного массива из 13 элементов 23453 -335 3355000 -6 267767744 программа должна вывести 3

В переменной $k$ мы будем хранить наибольшее количество идущих подряд элементов массива. Так как наименьшая длина такой последовательности равна 1 (сам элемент), изначально приравняем $k$ к единице.

Опишем кратко идею решения задачи: для каждого элемента массива мы будем подсчитывать, сколько до него идет подряд одинаковых чисел. После этого мы будем сравнивать получившееся количество с наибольшим количеством следующих друг за другом одинаковых элементов массива (с $k$ ) и обновим $k$ , если это понадобится.

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

Например, у нас есть такой массив: 1 1 1 0 0 0 0 4

Перед нулевым элементом массива нет никаких чисел, поэтому до него идет подряд 0 одинаковых чисел, $t = 1$ . $k = t$ , значит, $k$ не меняем. Перед первым элементом $a[1]$ = 1 расположен равный ему $a[0]$ = 1, тогда теперь у нас есть два одинаковых элемента, $t = 2$ . $k < t$ , тогда теперь $k = t = 2.$ Перед вторым элементом расположен тоже элемент, равный ему, но мы уже знаем, что для предыдущего элемента $t = 2$ . Значит, увеличим $t$ на единицу (добавив к последовательности одинаковых чисел второй элемент). $k < t$ , тогда $k = t = 3$ . Так как следующий элемент уже не равен предыдущему, начнем рассматривать новую последовательность чисел. Приравняем $t$ к 1 (теперь последовательность одинаковых чисел состоит из одного элемента, который мы сейчас рассматриваем). Следующий элемент $a[4]$ равен $a[3]$ , значит, увеличим значение $t$ на 1. $k > t » class=»math» width=»auto»>, <img decoding=$ оставляем таким же. $a[5 ] = a[4]$ , значит, увеличим $t$ еще на один. $k = t$ , оставляем таким же. Наконец, $a[6 ] = a[5]$ , увеличим $t$ , ведь теперь последовательность одинаковых чисел равна четырем. Так как $k > t » class=»math» width=»auto»>, <img decoding=$ . Следующий элемент $a[7]$ не равен $a [6]$ , для него $t = 1$ .

Обобщим наш алгоритм: для нулевого элемента $t = 1$ . Для каждого следующего элемента мы проверяем, равен ли он предыдущему. Если да, мы увеличиваем $t$ на 1, так как последовательность одинаковых элементов стала больше на один элемент и сравним $t$ с максимумом $k$ (если $t > k » class=»math» width=»auto»>, <img decoding=$ ). Если нет, мы только сравним $t$ с максимумом $k$ . После этого приравняем $t$ снова к 1, потому что теперь рассматриваем новую последовательность одинаковых чисел. Вне цикла выведем $k$ , в котором окажется длина максимальной последовательности одинаковых чисел.