Разбор задания № 24 ЕГЭ по информатике

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

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

Попытка решить это задание просмотром текстового файла средствами поиска Word не увенчается успехом, поэтому не следует тратить на это время на экзамене. К данному заданию не прилагается никакого входного значения маленького размера, поэтому тесты нужно придумать самостоятельно. Составим несколько тестов сразу для проверки будущей программы. На экзамене это необходимо сделать:

Составим алгоритм для решения задачи. Считаем для начала все содержимое файла в одну строку. Заведем 2 переменные: tek_len в которой будем хранить текущую длину последовательности, не содержащую символов 000 и max_len – хранящую количество элементов в самой длинной из всех последовательностей, не содержащих данных символов.

Будем «идти» начиная с третьего символа, а не первого и "смотреть" на два предыдущих. Инициализировать переменные tek_len и max_len следует значениями 2, т.к. два нуля из трех войдут в текущую последовательность. Если текущий символ отличен от нуля, то к длине текущей последовательности добавляем 1. Если же текущий символ равен нулю и два предыдущих равны нулю, то следует сравнить max_len и tek_len.

Если значение текущей длины превысит значение максимальной длины, то в max_len нужно записать tek_len, а затем начинаем новую последовательность и в переменную tek_len кладем значение 2 (как в начале программы). Далее следует перейти к очередному символу, стоящему справа пока не обработаем всю строку. Выйдя из цикла необходимо еще раз сравнить значения max_len и tek_len и в max_len записать большее.

Программа представлена на языке программирования Python.

f = open('24.txt', 'r') # открываем файл в режиме чтения
s = f.read() # считываем данные из файла в строку s
max_len = tek_len = 2 # инициализация начальных значений
for i in range(2, len(s)):
   if s[i] == '0' and s[i - 1] == '0' and s[i - 2] == '0':
      max_len = max(max_len, tek_len)
      tek_len = 2 # начинаем новую последовательность
   else:
      tek_len += 1
max_len = max(max_len, tek_len)
print(max_len)

В результате получили значение 7684. Чтобы убедится в том, что программа работает действительно корректно, вернемся к составленным тестам и проверим работоспособность программы на этих тестах. Для этого закомментируем две первые строки и добавим ручной ввод строки s:

# f = open('24.txt', 'r')
# s = f.read()
s = input()
max_len = tek_len = 2 # инициализация начальных значений
for i in range(2, len(s)):
   if s[i] == '0' and s[i - 1] == '0' and s[i - 2] == '0':
      max_len = max(max_len, tek_len)
      tek_len = 2 # начинаем новую последовательность
   else:
      tek_len += 1
max_len = max(max_len, tek_len)
print(max_len)
Таблица проверки

Программа "прошла" по всем тестам, а значит можно смело утверждать, что полученный ответ (7684) является верным. Программу можно сократить на одну строку, делая безусловное сравнение переменных max_len и tek_len при каждой итерации:

f = open('24.txt', 'r')
s = f.read()
max_len = tek_len = 2 # инициализация начальных значений
for i in range(2, len(s)): # цикл по символам строки
   if s[i] == '0' and s[i - 1] == '0' and s[i - 2] == '0':
      tek_len = 2 # начинаем новую последовательность
   else:
      tek_len += 1
max_len = max(max_len, tek_len)
print(max_len)

Для полного понимания работы программы можно воспользоваться механизмом трассировки (ручного прогона программы).