Статья Автор: Лебедев Дмитрий

Разбор заданий с файлами

Задание 24	Файл `fz_24_ds25.txt`

Решим задание с помощью "двух указателей". Пусть задана строкак sss. Определим:

x - указатель на начало слова/числа. Очевидно, что sss[x] in "123456789AB" (тривиальным случаем sss[x] = 0 принебрегаем)
y - указатель на следующий символ после окончания слова/числа. Очевидно, что sss[y] not in "0123456789AB" (теперь 0 нужен и длина слова/числа равна y - x)

Напишем макет программы, который будет искать максимальное (по длине) слово/число. Чтобы не было проблем, добавим к строке "барьер" в виде "паразитного символа" (типа "_")

def f24(ss):
  return ss
fin = open('fz_24_ds25.txt') # открываем файл для удобства 
sss = fin.read() + '_1_' # добавляем барьер
fin.close() # для порядка
print(len(sss), sss[-10:]) #отладочная печать, чтобы файл не открывать и увидеть последние символы
x, ans = 0, "" # инициализация начальных значений и ответа в формате строки (для визуализации)
while x < len(sss)-3: # остановка по началу слова/x и барьеру
  while (sss[x] in '123456789AB') == False : # прогон указателя "начала слова"
    x +=1
  y = x # иниацилизация указателя "конца слова" - более правильная y = x + 1, но так более "чучковатей"
  while sss[y] in '0123456789AB' : # прогон указателя "окончание слова"
    y += 1
  ss = sss[x:y] # получение слова/числа - далее его надо обработать/сократить
  ss = f24(ss) # "здесь будет город заложен ..." (можно пока было и не вставлять, но это "необходимое условие" решения)
  if len(ss) > len(ans) : # проверям результат на "самый, самый ..."
    ans = ss
  x = y #перенос "начала слова" на "окончание слова" для ускорения поиска следующего  
print(len(ans), ans, sep ='\n') # вывод результатов"

Теперь осталось понять - а как определять чётность числа по его записи в P - ной системе счисления.
В общем случае есть признаки делимости вида:

по "последнимй цифрам" - делимость/остатки на делители числа P и их степени (для десятичной системы это на 2, 5, 4, 25 и т.д.)
по "сумме цифр разрядов записи" - делимость/остатки на делители чисел P-1 и P+1 (для десятичной системы это 9, 3, 11)

По условию нам нужна делимость на 2 в 12-ной системе счисления. Мы нашли 20-значное число "A3000001500860000061" и если его сократить на одну цифру, то все будет OK:

- у нас есть ответ в 19 и можно вывести все 20-значные числа и проверить их (так можно и возможно НУЖНО поступить на экзамене)

Для общности напишем подпрограмму, сокращающую слов/число до нужной цифры, добавим алфавит и введем переменные
P - для основания системы счисления и q - числа кратности

def f24(ss, p = 12, q = 2): #p - основание системы счисления; q - цифра для проверки делимость
  s = ss[::-1] # переворот для упрощения кода
  i = 0
  while i < len(s) :
    if int(s[i], p) % q == 0 : 
      s = s[i:]
      return s[::-1]  # возврат результата
    i += 1
  return "" # возврат пустого результата 
alf = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p, q = 35, 2
dl, kl  = 600, 0
alf0, alf1 = alf[:p], alf[1:p]
fin = open('fz_24_ds25.txt') # открываем файл для удобства 
sss = fin.read() + '_1_' # добавляем барьер
fin.close() # для порядка
print(len(sss), sss[-10:]) #отладочная печать, чтобы файл не открывать и увидеть последние символы
x, ans = 0, "" # инициализация начальных значений и ответа в формате строки (для визуализации)
while x < len(sss)-3: # остановка по началу слова/x и барьеру
  while (sss[x] in alf1) == False : # прогон указателя "начала слова"
    x +=1
  y = x # иниацилизация указателя "конца слова" - более правильная y = x + 1, но так более "чучковатей"
  while sss[y] in alf0 : # прогон указателя "окончание слова"
    y += 1
  ss = sss[x:y] # получение слова/числа - далее его надо обработать/сократить
  if len(ss) >=dl : 
    i = sum([int(j) for j in ss])
    kl+=1
    #print(kl, i,ss)
  if len(ss) > len(ans) : # проверям результат на "самый, самый ..."
    s = ss #f24(ss, p, q) # перенесли "внутрь" для ускорения (короткие строки можно не проверять")
    if len(s) > len(ans):# сравнение с лучшим вариантом
      ans = s # фиксация нового варианта
  x = y #перенос "начала слова" на "окончание слова" для ускорения поиска следующего  
print(kl,len(ans), ans, sep ='\n') # вывод результатов"

Ответ в задании всего 19 знаков, при максимальной длине числа в 20. Значит было возможно практически любой "силовой" способ решения.
Теперь посмотрим какие "усиления" могут предложить организаторы:

увеличение основания системы P
замена чётности на кратность/не кратность цифре q - являющейся делетелем P:
например кратность 7 в системе счисления с основанием 21
переход к "квадрату основания"
например к кратности 9 в системе счисления с основанием 12
переход от правила "последних" цифр к правилам "признаки делимости" или их комбинации
например, кратности 22 или 26 для 12-ричных чисел

Разберем случай чётности в 13-ричной системе счисления, заодно освоим промежуточную печать итогов
Алгоритм действует на основе правила - "в системе счисления с нечётным основание чётность числа совпадает с чётностью суммы цифр этого числа".
Значит если сумма цифр:

чётна, то число чётно
нечётна, то точно есть нечётная цифра и одну из них надо выкинуть
- можно "первую слева",
- можно "первую справа" (удалив оставшиеся ведущие нули)

def f24a(ss, p = 13): #p - основание системы счисления; q - цифра для проверки делимость
  ks = sum([int(x, p) for x in ss])
  if ks % 2 == 0 : # число чётное 
    return ss
  i = -1 # проход справа налево
  while int(ss[i],p) %2 == 0:
    i -=1
  sr = ss[:i]
  i = 0 # проход слева
  while int(ss[i],p) %2 == 0: # до первой нечётной
    i +=1
  i += 1  
  while (i < len(ss)) and (ss[i] == '0') :
    i +=1
  sl = ss[i:]
  if len(sl) > len(sr) : return sl
  return sr
alf = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p = 19
alf0, alf1 = alf[:p], alf[1:p]

Прикрепленные файлы
fz_24_ds25.txt

Чтобы оставить комментарий нужна авторизация

Печать