Уведомления

Группа в Telegram: @pythonsu

#1 Март 28, 2021 10:51:56

Lee
Зарегистрирован: 2021-03-21
Сообщения: 20
Репутация: +  0  -
Профиль   Отправить e-mail  

Задача егэ

Тек­сто­вый файл со­сто­ит не более чем из 106 сим­во­лов A, B и C. Опре­де­ли­те мак­си­маль­ную длину це­поч­ки вида ABABAB… (со­став­лен­ной из фраг­мен­тов AB, по­след­ний фраг­мент может быть не­пол­ным. Я написал вот такую программу, но она не работает. Исправьте пожалуйста!
Заранее спасибо 

[code python]
c=1
max=0
s='abababbacccbaab'
x=s.replace('ab' ,'g')
for i in range(len(x)-1):
	if x[i]=='g'and x[i+1]=='g':
		c=c+2
if max<c:
	max=c
	c=1
print(c,x) [/code]

Отредактировано Lee (Март 28, 2021 12:02:56)

Офлайн

#2 Март 28, 2021 12:20:54

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 9726
Репутация: +  843  -
Профиль   Отправить e-mail  

Задача егэ

Да она не так делается.

Надо один раз по строке идти и считать. Также есть состояния такие “видел букву A только что”, “видел букву B только что”, “не видел ни A ни B только что”. Соответственно, в каждой ситуации происходит либо наращивание переменной длины, либо сброс переменной длины. Если у тебя ситуация “видел букву B только что” и тут у тебя на входе буква B, то явно цепочка закончилась и нужно сравнить подсчитанную длину с максимальной длиной. Если же у тебя ситуация “видел букву B только что” и тут у тебя на входе буква A, то явно цепочка продолжается и нужно увеличить подсчитанную длину на единицу и продолжать дальше.



Офлайн

#3 Март 28, 2021 21:13:03

Lee
Зарегистрирован: 2021-03-21
Сообщения: 20
Репутация: +  0  -
Профиль   Отправить e-mail  

Задача егэ

А можете написать пожалуйста?

Офлайн

#4 Март 28, 2021 22:55:23

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 9726
Репутация: +  843  -
Профиль   Отправить e-mail  

Задача егэ

Lee
Тек­сто­вый файл со­сто­ит не более чем из 106 сим­во­лов A, B и C. Опре­де­ли­те мак­си­маль­ную длину це­поч­ки вида ABABAB… (со­став­лен­ной из фраг­мен­тов AB, по­след­ний фраг­мент может быть не­пол­ным.

Функция, которая для строки вычисляет максимальную длину цепочки из AB, включая неполные цепочки
  
>>> def f(text):
...     (ST_NO_AB,
...      ST_WAS_A,
...      ST_WAS_B,
...      ST_END) = (0, 1, 2, 3)
...     state = ST_NO_AB
...     curlen = maxlen = 0
...     it = iter(text)
...     while True:
...         c = next(it, None)
...         if state == ST_NO_AB:
...             if c is None:
...                 state = ST_END
...             elif c == 'A':
...                 curlen += 1
...                 state = ST_WAS_A
...             elif c == 'B':
...                 pass
...         elif state == ST_WAS_A:
...             if c is None:
...                 state = ST_END
...             elif c == 'B':
...                 curlen += 1
...                 state = ST_WAS_B
...             elif c == 'A':
...                 pass
...             else:
...                 if curlen > maxlen:
...                     maxlen = curlen
...                     curlen = 0
...                 state = ST_NO_AB
...         elif state == ST_WAS_B:
...             if c is None:
...                 state = ST_END
...             elif c == 'A':
...                 curlen += 1
...                 state = ST_WAS_A
...             elif c == 'B':
...                 pass
...             else:
...                 if curlen > maxlen:
...                     maxlen = curlen
...                     curlen = 0
...                 state = ST_NO_AB
...         elif state == ST_END:
...             if curlen > maxlen:
...                 maxlen = curlen
...             break
...     return maxlen
... 
>>> f('')
0
>>> f('C')
0
>>> f('A')
1
>>> f('B')
0
>>> f('AB')
2
>>> f('BA')
1
>>> f('ABAB')
4
>>> f('ABABA')
5
>>> f('AA')
1
>>> f('BB')
0
>>> f('ABCABACABABA')
5
>>> f('ABCABABACABAB')
5
>>>

Это для открытия и чтения файла фрагмент
  
with open('file.txt', encoding='utf-8') as fin:
    out = f(fin.read())
    print(out)

Можно там, наверное, и по-школьному написать, типа два элемента у тебя есть и предыдущий равен тому-то, а текущий равен тому-то. А потом после цикла ещё проверять, не закончилась ли строка на последней цепочке во время подсчёта её длины. Да и вообще там цикл с инвариантом можно сделать. Это было бы идеально для школьника. Но я думаю, если на тебя обрушатся десятки таких задач из реального мира, мало какие из них будут такими удобными. И чаще тебе придётся детерминированный конечный автомат (ДКА) писать, чтобы гарантированно выполнить задачу.



Отредактировано py.user.next (Март 28, 2021 23:16:54)

Офлайн

#5 Апрель 1, 2021 00:56:22

Lee
Зарегистрирован: 2021-03-21
Сообщения: 20
Репутация: +  0  -
Профиль   Отправить e-mail  

Задача егэ

Спасибо!

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version