Задание 24. Подстроки

: Сборник ЕГЭ-2024; 29 февраля 2024; Просмотров: 961

Обработка больших подпоследовательностей в строках (задание 24)

Рейтинг: 5 / 5

В сборнике 2024 года появились задания на нахождение довольно больших подпоследовательностей в строках. Эти задания при решении простым перебором вариантов выполняться будут довольно долго. Поэтому нужна оптимизация алгоритма. Одним из способов решения таких заданий является переход от самих элементов последовательностей к их индексам и созданию массива с номерами нужных нам элементов.

ВАРИАНТ 1

Текстовый файл состоит из символов A, B, C, D, E, F и G.

Определите в прилагаемом файле минимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ А встречается ровно 2024 раза.

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var01.txt')
s = f.readline()
f.close()

n = []#создаем пустой массив для индексов букв А
m = float('inf')# потолок для минимума
for i in range(len(s)):# в строке s ищем буквы А и их индексы добавляем в n
if s[i] == 'A':
n.append(i)

for i in range (len(n)- 2023):#в массиве n ищем подпоследовательности длиной 2024 символа

m = min(m, n[i + 2023] - n[i] + 1)# 2024 = 2023 - 0 + 1

print (m)

Ответ: 7001

ВАРИАНТ 2

Текстовый файл состоит из символов A, B, C, D, E, F и G.

Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ А встречается не более 350 раз.

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var02.txt')
s = f.readline()
f.close()

n = []#создаем пустой массив для индексов букв А
m = 0# пол для максимума

for i in range(len(s)):# в строке s ищем буквы А и их индексы добавляем в n

if s[i] == 'A':
n.append(i)

for i in range (len(n)- 349):#в массиве n ищем подпоследовательности длиной 350 символов
m = max(m, n[i + 349] - n[i] + 1)# 350 = 349 - 0 + 1

print (m)

Ответ: 88024

ВАРИАНТ 3

Текстовый файл состоит из символов A, B, C, D и E.

Определите в прилагаемом файле минимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ А встречается не менее500 раз.

Для выполнения этого задания следует написать программу.

Решение и ответ

аналогично 2 варианту

Ответ: 5678

ВАРИАНТ 4

Текстовый файл состоит из символов A, B, C, D, E, F и G.

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var04.txt')
s = f.readline()
M = 0 #обнуляем длину максимальной подпоследовательности
s = s.replace('E', ' ') #заменяем буквы Е пробелами

for word in s.split(): #цикл по словам строки s
n = [] #для каждого слова создаем пустой массив с номерами букв А
for i in range (len(word)): # цикл по слову
if word[i] == 'A':
n.append(i) #добавляем в массив номера букв А

for i in range(len(n) - 701): # ищем в словах подпоследовательности с максимальным количеством символов и содержащие ровно 700 букв А

M = max(M, n[i + 701] - n[i] - 1 ) # находим длину максимальной подпоследовательности из 700 символов + символы справа и слева до букв А

print(M)

Ответ: 12812

ВАРИАНТ 5

Текстовый файл состоит из символов A, B, C, D и Е. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых символ A встречается не более 3 раз.

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var05.txt')
s = f.readline()
f.close()

n = []#создаем пустой массив для индексов букв А
m = 0 # пол для максимума

for i in range(len(s)):# в строке s ищем буквы А и их индексы добавляем в n
if s[i] == 'A':
n.append(i)

for i in range (len(n)- 2):#в массиве n ищем подпоследовательности длиной 3 символов

m = max(m, n[i + 2] - n[i] + 1)

print (m)

Ответ: 501

ВАРИАНТ 6

Текстовый файл состоит из символов A, B, C, D и Е. Определите в прилагаемом файле минимальное количество идущих подряд символов, среди которых символ A встречается 35 раз.

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var06.txt')

аналогично 5 варианту

Ответ: 40

ВАРИАНТ 7

Текстовый файл состоит из символов A, B, C, D и Е. Определите в прилагаемом файле минимальное количество идущих подряд символов , среди которых комбинация символов AВ встречается ровно 21 раз.

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var07.txt')
s = f.readline()
f.close()

n = []#создаем пустой массив для индексов букв А
m = float('inf') # пол для максимума

for i in range(len(s)-1):# в строке s ищем буквы А и их индексы добавляем в n
if s[i]+ s[i+1] == 'AB':
n.append(i)

for i in range (len(n)- 20):#в массиве n ищем подпоследовательности длиной 21 символ

m = min(m, n[i + 20] - n[i] + 2)# поскольку массив был только по индексам А, к границе прибавляем еще одну букву В

print (m)

Ответ: 55

ВАРИАНТ 8

Текстовый файл состоит из символов A, B, C, D и Е. Определите в прилагаемом файле максимальное количество идущих подряд символов , среди которых комбинация AB встречается ровно 21 раз.Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var08.txt')

p= f.readline()
f.close()
N = 0 #нижняя граница максимума

for i in range(len(p)):
n = 1 #количество символов всего
k = 0 #количество сочетаний АВ
for j in range (i+1, len(p)):
n += 1
if p[j-1]+p[j] == 'AB': #поиск сочетаний АВ
k += 1
if k == 22:
N = max(n-1, N) # убираем одну букву из сочетания АВ и ищем максимум
break

print(N)

Ответ: 10007

ВАРИАНТ 9

Текстовый файл состоит из символов арабских цифр (0, 1, 2, 3, ....9). Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых нет символов 0, стоящих рядом.

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var09-12.txt')
s= f.readline()
f.close()
s = s.replace('00', '0 0')
s = s.split(' ')

print( max(map(len, s)))

Ответ: 977

ВАРИАНТ 10

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var09-12.txt')
s= f.readline()
f.close()
m=0

s = s.split('000')
for i in s:
m = max(m, len(i))
print (m+4)#добавляем к слову первые 00 и последние 00

или

s = s.replace('000', '00 00')
s = s.split(' ')
print (max (map (len, s)))

Ответ: 7684

ВАРИАНТ 11

Для выполнения этого задания следует написать программу.

Решение и ответ

f = open('24var09-12.txt')
p = f.readline()
f.close()
m=k=1 #минимальное количество символов в подпоследовательности

for i in range(1,len(p)):
if not (p[i-1] + p[i] == '12' or p[i-1] + p[i] == '21'):
k+=1
else:
m = max (k,m) #запоминаем максимальную длину подпоследовательности
k = 1

print(m)

или

s = s.replace('12', '1 2')
s = s.replace('21', '2 1')
s = s.split(' ')

print (max (map (len, s)))

Ответ: 532

ВАРИАНТ 12

Для выполнения этого задания следует написать программу.

Решение и ответ

f = open('24var09-12.txt')
p= f.readline()
f.close()
m=k=1 #минимальное количество элементов в подпоследовательности

for i in range(1,len(p)):
if not (p[i-1] + p[i] == '12' or p[i-1] + p[i] == '21' or p[i-1] + p[i] == '13' or p[i-1] + p[i] == '31'):
k+=1
else:
m = max(k,m)
k = 1

print(m)

или

s = s.replace('12', '1 2')
s = s.replace('21', '2 1')
s = s.replace('13', '1 3')
s = s.replace('31', '3 1')
s = s.split(' ')

print (max (map (len, s)))

Ответ: 339

ВАРИАНТ 13

Текстовый файл состоит не более чем из 10⁶символов X, Y и Z. Определите максимальное количество идущих подряд символов, расположенных в алфавитном порядке (возможно с повторением символов).

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var13-17.txt')
p=f.readline()
f.close()
m=k=1

for i in range(1,len(p)):
if p[i]>= p[i-1]:
k+=1
else:
m=max(k,m)
k=1

print(m)

или

s = s.replace('Y X', 'Y X')
s = s.replace('Z X', 'Z X')
s = s.replace('Z Y', 'Z Y')
s = s.split(' ')
print (max (map (len, s)))

Ответ: 15

ВАРИАНТ 14

Текстовый файл состоит не более чем из 10⁶символов X, Y и Z. Определите максимальное количество идущих подряд символов, расположенных в обратном алфавитном порядке (возможно с повторением символов).

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var13-17.txt')
p=f.readline()
f.close()
m=k=1

for i in range(1,len(p)):
if p[i]<= p[i-1]:
k+=1
else:
m=max(k,m)
k=1

print(m)

Ответ: 19

ВАРИАНТ 15

Текстовый файл состоит не более чем из 10⁶символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых нет символа Z.

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var13-17.txt')
p=f.readline()
f.close()
m=k=0 #если Z первая, то длина подпоследовательности равна 0

for i in p:
if i!='Z':
k+=1
else:
m=max(k,m)
k=0

print(m)

Ответ: 34

ВАРИАНТ 16

Текстовый файл состоит не более чем из 10⁶символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых символ Z встречается не более 1 раза.

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var13-17.txt')

p=f.readline()
f.close()
m=n=0
a='' #подстрока а
for i in p:
a+=i
if i == 'Z':
n+=1
if n==2:
m=max(m,len(a)-1) # максимальное количество символов из текущего значения и длины а
a = a[a.find('Z')+1:] # удаляем слева все символы, включая первую Z
n=1 # осталось символов Z в строке

print(m)

Ответ: 43

ВАРИАНТ 17

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var13-17.txt')
p=f.readline()
f.close()
m=n=0
a='' #подстрока а
for i in p:
a+=i
if i == 'Z':
n+=1
if n==3:
m=max(m,len(a)-1) # максимальное количество символов из текущего значения и длины а
a = a[a.find('Z')+1:] # удаляем слева все символы, включая первую Z
n=2 # осталось символов Z в строке

print(m)

Ответ: 50

ВАРИАНТ 18

Текстовый файл состоит не более чем из 10⁶символов арабских цифр (0, 1, 2, ..., 9). Определите максимальное количество идущих подряд одинаковых цифр.

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var18-20.txt')

p=f.readline()
f.close()
m=k=1
for i in range(1,len(p)):
if p[i-1]== p[i]:
k+=1
else:
m=max(k,m)
k=1

print(m)

Ответ: 47

ВАРИАНТ 19

Текстовый файл состоит не более чем из 10⁶символов арабских цифр (0, 1, 2, ..., 9). Определите максимальное количество идущих подряд цифр, среди которых каждые две соседние различны .

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var18-20.txt')

p=f.readline()
f.close()
m=k=1

for i in range(1,len(p)):
if p[i-1]!= p[i]:
k+=1
else:
m=max(k,m)
k=1

print(m)

Ответ: 120

ВАРИАНТ 20

Текстовый файл состоит не более чем из 10⁶символов арабских цифр (0, 1, 2, ..., 9). Определите максимальное количество идущих подряд цифр, расположенных в строго возрастающем порядке.

Для выполнения этого задания следует написать программу.

Решение и ответ

f=open('24var18-20.txt')

p=f.readline()
f.close()
m=k=1

for i in range(1,len(p)):
if p[i-1] < p[i]:
k+=1
else:
m=max(k,m)
k=1

print(m)

Ответ: 8

Rating:

( 1 Rating )

Обработка больших подпоследовательностей в строках (задание 24)

РСЯ футер