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

Разбор Статграда от 2024-12-17. Часть 4( 8, 13, 14, 25)

Задание 8

Джон составляет список всех возможных кодов, составленных из заглавных латинских букв.
Сначала он выписывает в алфавитном порядке все коды, состоящие из
одного символа (A, B, …, Z),
затем – тоже в алфавитном порядке – коды из двух символов (AA, AB, …, AZ, BA, BB, … ZZ),
далее идут трёхсимвольные коды (AAA, AAB, …, ZZZ) и так далее.
Под каким номером окажется в этом списке код FEDABC?

Задание не такое сложное, как может показаться. Для решения достаточно:

Понять, что в алфавите из P элементов k-символьных кодов можно создать P^k
- A, ..., Z = 26¹ вариантов
- AA, ..., ZZ = 26² вариантов
- AAA, ..., Z = 26³ вариантов
- AAAA, ..., ZZZZ = 26⁴ вариантов
- AAAAA, ..., ZZZZZ = 26⁵ вариантов
От AAAAAA до FEDABC можно вычислять как числа в 26-ричной системе счисления, где
0 = 'A', 1 = 'B', 2 = 'C', 3 = 'D', 4 = 'E', 5 = 'F', ...

Таким образом надо подсчитать:

Количество наборов от A до ZZZZZ = 26¹+26²+26³+26⁴+26⁵ = 12356630
Количество наборов от AAAAAA до FEDABC = 1 + 543012₂₆= 1 + int('543012',26) = 61287541

Сложим найденное и получим результат 73644171

Задание 14

Значение арифметического выражения
4·7²⁴ + 6·7¹³ + 5·49⁴ + 2·343² + 10 – x,
где x – натуральное число, записали в системе счисления с основанием 7.
Определите наименьшее значение x, при котором в этой записи шестёрок будет больше, чем нулей.

Задание в новой, интересной постановке. Надо найти х, но простым перебором это может не получиться.
Рассмотрим число A = 4·7²⁴ + 6·7¹³ + 5·49⁴ + 2·343² + 10 и посмотрим на его запись в системе счисления с основанием 7
(сделаем это в табличном редакторе с указанием разрядов, понимая, что 49=7²; 343=7³; 10₁₀ = 13₇)

разряд	24	23	22	21	20	19	18	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
	4	0	0	0	0	0	0	0	0	0	0	6	0	0	0	0	5	0	2	0	0	0	0	1	3

В числе A₇ всего 25 знаков и с 24 до 8 разряда 14 нулей, а это больше половины.
Следовательно из A надо вычесть хотя бы B+1, где B = 502000013₇ Получим

разряд	24	23	22	21	20	19	18	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
A	4	0	0	0	0	0	0	0	0	0	0	6	0	0	0	0	5	0	2	0	0	0	0	1	3
B																	5	0	2	0	0	0	0	1	3
A-B	4	0	0	0	0	0	0	0	0	0	0	6	0	0	0	0	0	0	0	0	0	0	0	0	0
A-B-1	4	0	0	0	0	0	0	0	0	0	0	5	6	6	6	6	6	6	6	6	6	6	6	6	6

В числе (A-B-1)7 всего 10 цифр 0 и 13 цифр 6 - это подходит
X= B+1 = 5·49⁴ + 2·343² + 10 +1 = 29059314
Из ответа видно, что переборное решение не пройдет.

Как можно усложнить вопрос? Найти минимальное X, при котором число цифр 0 и 6 будет одинаковым

Задание 25

Найдите все натуральные числа, принадлежащие интервалу [10⁸; 2·10⁸],
которые соответствуют маске ?*42*81 и имеют ровно три натуральных делителя.

Задание на понимание проблемы с простой реализацией.

Три натуральных делителя имеют числа вида p² (p - простое) и только они.
=> надо перебрать все простые числа от 10⁴ до 14142 (это корень из 210⁸),
и проверить соответствие маске этих чисел
Для проверки на простоту воспользуемся функцией для поиска делителей числа

def sp_del(n):
  A = set()
  d = 0
  while d * d < n :
    d +=1
    if n % d == 0 :
      A.add(d)
      A.add(n // d)
  return A
for n in range(10000, 14142):
  a = sp_del(n) # получение списка делителей
  if len(a) != 2 : continue # проверка на простое
  nn=n*n  # возведение в квадрат
  ss = str(nn)  # строка цифр из квадрата
  if (ss[-2:]) == '81' and ('42' in ss[1:-2]) :
    print(nn, sorted(sp_del(nn))) # вывод результата и его делителей

Задание 13

Узлы с IP-адресами 157.220.185.237 и 157.220.184.230 принадлежат одной сети.
Какое наименьшее количество IP-адресов, в двоичной записи которых
ровно 15 единиц, может содержаться в этой сети?

Решение задания может содержать следующие шаги:

Перевод IP-адресов в двоичный вид

10011101 11011100 10111001 11101101

10011101 11011100 10111000 11100110
Вопрос про "наименьшее количество", значит маску надо взять максимальной длины,
то есть 23/9 (23 единицы и 9 нулей, 23 - максимальная длина совпадающих разрядов)
Первые 23 разряда IP-адреса содержат 14 единиц, значит остальные могут содержать только одну
Разместить 1 единицу на 9 мест можно всего 9 способами

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

Печать