Обработка больших подпоследовательностей в строках (задание 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 раз.

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

Решение и ответ
f = open ('24var03.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)- 499):#в массиве n ищем подпоследовательности длиной 500 символов
    m = min(m, n[i + 499] - n[i] + 1)

print (m)

Ответ5678

ВАРИАНТ 4

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

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

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

Решение и ответ
 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 и Е. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых символ  встречается не более 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 и Е. Определите в прилагаемом файле минимальное количество идущих подряд символов, среди которых символ  встречается 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

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

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

Решение и ответ
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

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

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

Решение и ответ
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

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

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

Решение и ответ
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

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

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

Решение и ответ
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

РСЯ футер

© 2017 Компьютерный клуб "КОД". Все права защищены.