Текст книги "Книга-тренажер: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс"

Глава 9. Теория игр

Задачи №19—21. Дерево игры и выигрышная стратегия

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

Все позиции в простых играх делятся на выигрышные и проигрышные.

Выигрышная позиция – это такая позиция, в которой игрок, делающий первый ход, может гарантированно выиграть при любой игре соперника. При этом алгоритм выбора очередного хода, приводящего к выигрышу, называется выигрышной стратегией. Считается, что игрок, обладающий выигрышной стратегией, не ошибается. Проигрышная позиция – это такая позиция, при которой игрок, делающий первый ход, проигрывает независимо от выбора очередного хода. Также следует различать сильный ход и слабый ход. Сильный ход – этот тот, который ведет к быстрой победе, слабый тот, который проигрывает. Ходы обычно состоят из арифметических действий. Ходы умножить или разделить увеличивают или уменьшают число кратно, а значит, ведут к более быстрой победе, чем ходы разности или суммы.

Пример 19—21.1

Игра: в кучке лежат 5 спичек; играют два игрока, которые по очереди убирают спички из кучки; условие: за один ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку.

Решение:

– Будем использовать метод построения дерева. Первый играющий может убрать одну спичку (в этом случае их останется 4) или сразу 2 (останется 3), эти два варианта отобразим при помощи дерева:

– если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну:

– если осталось 3 или 2 спички, то 1-ый игрок (в обеих ситуациях) выиграет своим ходом:

Проанализируем стратегию игры:

– если первый игрок своим первым ходом взял две спички, то второй сразу выигрывает; если же он взял одну спичку, то своим вторым ходом он может выиграть, независимо от хода второго игрока;

– итак, убрав всего одну спичку первым ходом, 1-ый игрок всегда может выиграть на следующем ходу – это и есть его выигрышная стратегия;

– тогда как второй игрок не может выиграть, независимо от действий первого: потому что, если первый игрок сначала убрал одну спичку, второй всегда проиграет.

Ответ: при правильной игре (стратегии игры) выиграет первый игрок; для этого ему достаточно своим первым ходом убрать одну спичку.

Пример 19—19

Два игрока, Петя и Ваня, играют в следующую игру.

Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.

В начальный момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Решение:

Составим уравнение 7+2*s=77, где 7 – это начальная позиция, а 2*s – это сильный первый ход Пети, тогда, решая это уравнение, имеем, что 2*s=70, s=35 – это значение, при котором Петя может выиграть первым ходом, если сделает ход *2. А по условию спрашивается, чтобы выиграл Ваня, значит, уменьшим значение s=35, но на сколько? На один ход, т.е. разделим на 2. 35/2=17,5. В какую сторону округляем? Если в меньшую сторону, то 17*2=34 – и Ваня с позиции 34 выиграть не сможет. Поэтому округляем до 18. s=18.

Решим данную задачу cпособом программирования на языке Python.

Введем обозначение позиций, что ниже. Первая позиция – это исходная, вторая – это ход Пети, третья – ход Вани, четвертая – ход Пети, пятая – ход Вани.

 
def f(x,y,p):
    if x + y >= 77 and p==3: # при p=3 и >77 Ваня побеждает на третьем ходу, где p – номер хода участника игры
        return True
    if x +y <77 and p==3: # Ваня проигрывает, если не достигли 77
        return False
    return f (x+1,y, p+1) or f (x*2,y, p+1) 
      or f (x,y+1, p+1) or f (x,y*2, p+1) # расписаны всевозможные варианты ходов
for i in range (1, 50+1):
    if f(7,i,1): # вызов функции из начальной позиции
        print(i)
        break
 

Ответ: 18.

Пример 19—20

Для игры, описанной в предыдущем задании, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

– Петя не может выиграть за один ход;

– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Решение:

Используя преемственность предыдущей задачи, а именно, что при S=35 – Петя выигрывает первым ходом, а у нас по условию нужно, чтобы он выиграл вторым ходом, что нужно сделать c 35? S=35—1=34. Или можем рассуждать так: 8 (первый ход 7+1) +2*s (второй ход *2) =76, тогда s=34. Давайте составим дерево и проверим, действительно ли Петя выиграет вторым ходом при позиции (7, 34).

По рисунку видим, что Петя ходит из позиции 7,34 в позицию в 8,34, т.к. он делает специально сильный ход, чтобы Ваня не смог выиграть на первом ходу. Далее Ваня из позиции 8,34 ходит в (9, 34), (8, 68), (16,34), (8,68). И на втором ходу Петя выигрывает, набирая> =77 камней.

Второе значение S находится так:

14 (первый ход 2*7) +2*s (второй ход) =76, то s=31. При S=1 – Петя побеждаем вторым ходом. Продемонстрируем это на дереве, где получились все значения> =77, что и требуется по условию задачи.

Решим данную задачу cпособом программирования на языке Python.

 
def f(x,y,p):
    if x + y >= 77 and p==4: # Петя побеждает на втором ходу
        return True
    if x +y < 77 and p==4: # Петя проигрывает на втором ходу, при значении меньше 77
        return False
    else:
        if x + y >= 77: #  проигрыш при достижении больше 77, кроме 2-ого хода Пети
            return False
    if p%2 == 1:
        return f (x+1,y, p+1) or f (x*2,y, p+1) or
        f (x,y+1, p+1) or f (x,y*2, p+1)
    else:
        return f (x+1,y, p+1) and f (x*2,y, p+1) and
        f (x,y+1, p+1)  and f (x,y*2, p+1) # Петя побеждает при четном p
for i in range (1, 100+1):
    if f(7,i,1):
        print(i)
 

Ответ: 31 34.

Пример 19—21

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть

первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно

выиграть первым ходом.

Решение:

Используем преемственность предыдущей задачи. Т.к. в предыдущей задаче получили значение, равное 31, то логично проверить значение на один ход меньше, т.е. 31—1=30. На основании дерева, что ниже, мы видим, что в его нижней части получаются все значения> =77 путем хода *2, поэтому S=30 нам подходит.

Решим данную задачу cпособом программирования на языке Python.

 
def f(x,y,p):
    if x + y >= 77 and (p==5 or p ==3): # Выигрыш Ивана на 1-ом или втором ходу
        return True
    if x +y < 77 and p==5:
        return False
    else:
        if x + y >= 77:
            return False
    if p%2 == 0:
        return f (x+1,y, p+1) or f (x*2,y, p+1) or
       f (x,y+1, p+1) or f (x,y*2, p+1)
    else:
        return f (x+1,y, p+1) and f (x*2,y, p+1) 
        and f (x,y+1, p+1) and f (x,y*2, p+1) # Победа Вани на нечетной позиции p
for i in range (1, 100+1):
    if f(7,i,1):
        print(i)
        break
 

Ответ: 30

Задачи для самостоятельного решения

Задача 19.2

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в пять раз. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 50 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится более 100. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 101 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 100.

Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

1. а) При каких значениях числа S Петя может выиграть первым ходом? Укажите все такие значения и выигрывающий ход Пети.

б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

2. Укажите два значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для указанных значений S опишите выигрышную стратегию Пети.

3. Укажите такое значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Глава 10. Языки программирования

Задача №22. Анализ программы на языке программирования

Для решения задач данного типа достаточно знать, что данные программы «заворачиваются» в цикл и прописывается условие. Давайте посмотрим на примере.

 
Пример 22.1
 

Ниже на четырёх языках программирования записана программа, которая вводит натуральное число x, выполняет преобразования, а затем выводит одно число. Укажите наименьшее возможное значение x, при вводе которого программа выведет число 40.

 
x = int(input())
a = 1
while x > 0:
  a *= x % 7
  x = x // 7
print(a)
 

Решение:

a *= x % 7 обозначает, что у нас в переменной а накапливается произведение цифр в семеричной системе счисления. Оно должно быть равно 40. Можно ли получить произведением двух цифр в семеричной системе счисления число 40? Не получится, т.к. максимальное число, которое мы можем взять в семеричной системе – это шесть, и тогда 6*6=36. Поэтому нам понадобится 3 числа, т.е. будет три разряда, x*y*z=40. Если на первое место поставим число 1, то двумя другими числами число 40 получить не получится. Поэтому поставим на первое место число 2. 2*x*y=40, тогда x=4, y=5, но не наоборот, т.к. нам нужно наименьшее число по условию задачи. Получили число 2*4*5=40, т.е. 245 нужно перевести из семеричной системы счисления в десятичную. 245₇=2*7²+4*7+5*7⁰ = 98+28+5=131.

Решим задачу cпособом программирования на языке Python.

 
for i in range (1,1000): # всю программу помещаем в цикл
    x = i
    a = 1
    while(x > 0):
        a *=x % 7
        x = x //7
    if a == 40: # из условия задачи
        print(i)
 

Ответ: 131.

Пример 22.2

Ниже на четырёх языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 4, а потом 5.

 
x = int(input())
Q = 9
L = 0
while x >= Q:
    L = L + 1
    x = x – Q
M = x
if M < L:
    M = L
    L = x
print(L)
print(M)
 

Решение:

Сначала решим аналитически. Условие if M <L обозначает, что цифры 5 и 4 поменяли местами. Выражение x = x – Q обозначает, сколько раз отнимали из числа 9 число 5. Сколько это раз? 4=x – 5*9, тогда x=49. Решим также эту задачу cпособом программирования на языке Python.

 
for i in range (0,100): # «заворачиваем» всю программу в цикл
    x = i
    Q = 9
    L = 0
    while x >= Q:
        L = L + 1
        x = x – Q
    M = x
    if M < L:
        M = L
        L = x
    if L ==4 and M==5: # прописываем условие задачи
      print(i)
Ответ: 49.
 

Пример 22.3

Ниже на четырех языках программирования записан алгоритм. Получив на вход натуральное десятичное число x <109, этот алгоритм печатает два числа A и B. Сколько чисел x существует таких, что после их обработки программой будут выведены два числа, сначала 43, затем 23.

 
x = int(input())
A, B = 0, 1
while x  > 0:
  if x % 2 == 0:
    A = A + (x % 10)
  else:
    B = B + (x % 10)
  x = x // 10
print(A)
print(B)
 

Решение:

Решение способом программирования на языке Python будет выглядеть следующим образом:

 
count =0 # вводим счетчик для накопления условия. Если А==43 и B=23
for i in range(100):
    x = i
    A, B = 0, 1
    while x  > 0:
         if x % 2 == 0:
             A = A + (x % 10)
         else:
             B = B + (x % 10)
             x = x // 10
    if A==43 and B == 23:
        count+=1
print(count)
 

Если запустить эту программу, то она не выдаст никакой результат. Как вы думаете почему? Ответ: программа не может выйти из цикла while x> 0, т.к. x в цикле всегда только положительное число. Поэтому переменная count не поменяется и будет равна 0.

Давайте решим эту задачу аналитически.

После анализа программы понимаем, что если if x % 2 == 0, то значение А – сумма четных разрядов числа х, В – сумма нечетных разрядов числа х. Из условия А = 43, В = 23. Что невозможно, так как суммой четных чисел невозможно накопить нечетное значение, т.к. нельзя число 43 представить суммой двух четных чисел.

Ответ: 0.

Задачи для самостоятельного решения

Задача 22.4

Ниже приведён алгоритм. Укажите наименьшее из таких чисел x, большее, чем 100, при вводе которого алгоритм напечатает 21.

Задача 22.5

Найдите минимальное число, при вводе которого приведенный алгоритм напечатает на экране число 60.

Задача №23. Исполнитель чисел

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

• словесное описание последовательности действий на естественном языке;

• графическое изображение в виде блок-схемы;

• запись при помощи псевдокода (алгоритмического языка);

• запись на языке программирования.

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

Пример 23.1

Исполнитель преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2.

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10?

Решение:

 
def count (a, b):
    """
    a – откуда мы идём , b – куда мы хотим прийти
    """
    if a == b:  # начальное положение и конечное совпали
        return 1
    if a > b:  # если начальное значение превысило конечное
        return 0
    return count(a + 1, b) + count(a * 2, b) # вызов команд из условия +1 и *2
print(count(1, 10)*count(10, 20)) # пути из одного в 10 и из 10 в 20.
 

Решим аналитически, путем построения дерева.

На рисунке, что выше, изображены команды из числа 2 в число 10. Вправо изображены команды *2, вниз +1. Всего таких команд можно насчитать 7, т.е. подчеркнутых цифр 10 равно семь. Но у нас выходит, что из единицы мы можем попасть в две двойки, путем команд 1*2=2 и 1+1=2, поэтому 7 команд повторится, а именно 7*2=14. Из 10 в 20 мы можем попасть двумя командами 10*2=20 и 10+1+1+1+1+1+1+1+1+1+1=20, поэтому 14*2=28.

Ответ: 28.

Пример 23.2

Исполнитель преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Удвоить

2. Удвоить и прибавить

Первая команда умножает число на экране на 2, вторая – умножает его на 2, а затем прибавляет 1.

Программа для исполнителя – это последовательность команд. Например, программа 121 при исходном числе 3 последовательно получит числа 6, 13 и 26. Результатом программы будет число 26.

Сколько различных результатов можно получить из исходного числа 1 после выполнения программы, содержащей ровно 11 команд?

Решение:

Аналитически довольно-таки долго просчитывать данную задачу, поэтому быстрее написать программу.

 
k = 0
def f(x, p):
    global k # глобальная переменная, которую интерпретатор видит во всей программе
    if p == 11: # если количество команд ровно 10-ти, то увеличиваем счетчик
        k += 1
    if p > 10: # больше 10-ти команд нас не устраивает, поэтому возвращаем ложь
        return 0
    return f(x * 2, p + 1) or f(x * 2 + 1, p + 1) # команды из условия задачи
f(1, 0) # вызов функции
print(k)
 

Ответ: 2048.

Пример 23.3

Исполнитель Треугольник преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 3

Сколько существует программ, для которых при исходном числе 3 результатом является число 20, и при этом траектория вычислений содержит число 15 и не содержит число 5?

Решение:

Код решения расположен ниже.

 
def count(a, b):
    if a == b:  # начальное положение и конечное совпали
        return 1
    if a > b:  # если начальное значение превысило конечное
        return 0
    if a == 5:  # если достигли числа 10, то эта команда не считается
        return 0
    return count(a + 1, b) + count(a +3, b) # вызов команд из условия +1 и +3
print(count(3, 15)*count(15, 20)) # пути из одного в 10 и из 10 в 20.
 

Ответ: 128.

Задачи для самостоятельного решения

Задача 23.4

Исполнитель преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд.

Задача 23.5

Сколько существует программ, для которых при исходном числе 1 результатом является число 30?

Исполнитель преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 30, при этом траектория вычислений не проходит через 10?

Задача 23.6

Исполнитель Муравей обрабатывает натуральные числа и имеет две команды:

1. Прибавить 3

2. Умножить на 3

Команда 1 увеличивает число на 3, команда 2 – втрое.

Сколько нечетных чисел, меньших 100, может быть получено в результате работы исполнителя, если на вход Муравью будет подано число 10?

Задача №24. Строки

Задания данного типа считаются повышенной сложности и выполняются с помощью языка программирования. Для этого необходимо знать, как работать со строками и списками. Опишу некоторые функции, полезные для этого задания. S.count (T) – возвращает число вхождений строки T внутри строки S. Строка – это тип данных, предназначенный для работы с текстом. Чтобы создать строку в Python, нужно использовать одинарные или двойные кавычки. Для многострочных строк можно использовать тройные кавычки (тоже одинарные или двойные). Пример S = «2, 3» – строка. s = input () – считываем строку с клавиатуры и помещаем ее в переменную s.

Метод split в Python разбивает строку на части, используя специальный разделитель, и возвращает эти части в виде списка. Например:

s = input () # s == «1 2 3»

a = s. split () # a == [«1», «2», «3»] – разделяет на подстроки

Строковый метод join () возвращает строку, объединяя все элементы итерации, разделенные разделителем строк.

Синтаксис: str.join (iterable)

Параметры: str – строка-разделитель, iterable – итерируемый (перебираемый) объект с элементами в виде строк.

Возвращаемое значение: новая строка.

Бывает, что необходимо считать с файла 2 или более чисел с одной строки и перевести в целый тип. Для этого используется функция: map (function, iterable, …).

Параметры: function – пользовательская функция, вызывается для каждого элемента.

iterable – последовательность или объект, поддерживающий итерирование.

Возвращаемое значение: map object – объект итератора (тип данных, который создан слева от метода, смотрим далее в пример). В данном случае поможет такая конструкция: s, n = map (int, f.readline ().split ()) – объектом итератора будут два числа целочисленного типа, считанные из файла s в виде строки и разделенные методом split отдельно на числа.

Пример 24.1

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

Решение:

Простроим математическую модель на примере. Например, дана строчка: XYZZY. Подряд идущие символы – это XYZ. Как нам это посчитать? Будем сравнивать посимвольно последующий символ с предыдущим, если они не равны, то увеличиваем счетчик на плюс один.

 
f=open('D:/24.txt') # открываем файл
s=f.readline() # считываем все одну строку
count =1 # текущее значение идущих разных символов подряд
count_final =0 # конечное значение идущих разных символов подряд
for i in range(1,len(s)): # циклом проходим построчно до конца строки
    if s[i]!=s[i-1]: # если последующий элемент не равен предыдущему.
        count +=1
        count_final = max(count_final,count) # для поиска максимально разных символов, если встретится несколько разных строк
    else:
        count=0 # обнуления счетчика для того, чтобы если встретится большая последовательность подряд идущих, то считаться будет заново
print(count_final)
 

Ответ: на данную задачу, если в файле будет находиться строка XYZZY – три.

Пример 24.2

Текстовый файл содержит строки различной длины. Общий объём файла не превышает 1 Мбайт. Строки содержат только заглавные буквы латинского алфавита (ABC… Z). Определите количество строк, в которых буква A встречается чаще, чем буква E. Решите задачу на примере следующих данных из файла:

AAAEE

AEAE

EEAAA

Решение:

 
f = open ('24.txt')
count = 0
for s in f:# считываем файл построчно
    if s.count('A') > s.count('E'):# если число букв А в новой строке больше, чем Е, то увеличиваем счетчик на +1
        count +=1
print(count)
Ответ: 3.
 

Пример 24.3

Текстовый файл содержит строки различной длины. Общий объём файла не превышает 1 Мбайт. Строки содержат только заглавные буквы латинского алфавита (ABC… Z). В строках, содержащих менее 25 букв A, нужно определить и вывести максимальное расстояние между одинаковыми буквами в одной строке.

Пример. Исходный файл:

GIGA

GABLAB NOTEBOOK

AGAAA

В этом примере во всех строках меньше 25 букв A. Самое большое расстояние между одинаковыми буквами – в третьей строке между буквами O, расположенными в строке на 2-й и 7-й позициях. В ответе для данного примера нужно вывести число 5.

Решение:

Давайте рассмотрим следующий пример. Идея задачи следующая: в каждой строке индексируем буквы (как на рисунке выше), и, например, буква b с индексом 1 находится на расстоянии 8 от буквы b с индексом 9, т.е. у нас будет индекс макс 9—1=8. В данной задаче используем функцию ord – она возвращает число символа Unicode. Например, ord (’h’) вернет104. Chr – функция наоборот возвращает символ Unicode.

 
f = open('d:24.txt')
count = 0
m = 0
for s in f:
    if s.count('A') < 25:  # условие из задачи
        mx = [-1] * 100  # максимальные индексы
        mn = [-1] * 100  # минимальные индексы
        for i in range(len(s)):
            if i > mx[ord(s[i])]:
                mx[ord(s[i])] = i  # нахождение макс. индекса
            if i < mn[ord(s[i])] or mn[ord(s[i])] == -1:  # -1 чтобы не спутать с максимумом.
                mn[ord(s[i])] = i  # нахождение минимального индекса
        for i in range(65, 90 + 1):  # проходимся по индексам 26 букв английского алфавита
            if mx[i] – mn[i] > m and mx[i] != -1 and mn[i] !=-1:  # условие поиска максимального расстояния между буквам исходной строки
                m = mx[i] – mn[i]
print(m)
Ответ: для примера, что в условии – 5.
 

Задачи для самостоятельного решения

Задача 24.4

В текстовом файле k7b-3.txt (файл находится по ссылке https://yadi.sk/d/IsXMjy1AvAUemA) находится цепочка из символов латинского алфавита A, B, C, D, E, F. Найдите максимальную длину цепочки вида BAFEBAFEBAFE…

Задача 24.5

Текстовый файл 24-s1.txt (файл находится по ссылке https://yadi.sk/d/_NTkfWVnKC0fig) состоит не более чем из 10⁶ заглавных латинских букв (A..Z). Текст разбит на строки различной длины. Определите количество строк, в которых буква J встречается чаще, чем буква E.