Решение задач по информатике с помощью ИИ по фото

Ниже представлена реализация алгоритма Флойда — Уоршелла на языке Python, адаптированная под данную задачу: вычисляется матрица кратчайших путей между всеми $N = 20$ вершинами и рассчитывается математическое ожидание сокращения пути при оптимальной стратегии применения волшебного кувшина.

import numpy as np

# Количество вершин (районов)
N = 20
INF = float("inf")

# Инициализация матрицы смежности
# Вершины нумеруются от 0 до 19
dist = [[INF] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0.0

# Список рёбер: (u, v, вес в км)
edges = [
    # Левый кластер
    (0, 1, 5),  # Верхний левый - крайний левый
    (0, 2, 16),  # Верхний левый - внутренний верхний
    (0, 7, 7),  # Верхний левый - узел (7)
    (0, 8, 7),  # Верхний левый - узел (8)
    (1, 2, 1),
    (2, 3, 3),
    (2, 7, 20),
    (3, 4, 20),
    (3, 7, 4),
    (4, 5, 3),
    (5, 6, 11),
    (6, 7, 20),
    (7, 10, 13),  # Узел 7 к нижнему узлу
    (1, 10, 18),  # Крайний левый к нижнему
    (5, 10, 12),  # Нижний левый внутренний к нижнему
    # Центральная часть
    (0, 9, 8),  # Верхний левый к верхнему центру
    (8, 9, 6),
    (8, 12, 12),
    (8, 13, 7),
    (9, 12, 15),
    (9, 11, 10),
    (9, 19, 12),  # Верхний центр к правому краю через верх
    (10, 13, 9),  # Нижний к узлу 13
    (10, 15, 17),  # Нижний к узлу 15
    (10, 19, 18),  # Нижний к нижнему правому углу
    # Правый кластер
    (11, 12, 2),
    (12, 13, 20),
    (12, 14, 6),
    (12, 18, 12),
    (13, 14, 2),
    (14, 15, 6),
    (14, 16, 6),
    (16, 17, 14),
    (17, 18, 18),
    (18, 19, 9),
]

# Заполнение неориентированного графа
for u, v, w in edges:
    dist[u][v] = min(dist[u][v], float(w))
    dist[v][u] = min(dist[v][u], float(w))

# 1. Алгоритм Флойда — Уоршелла (O(N^3))
for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

# 2. Вычисление E[d(X, t)] — ожидаемого расстояния от случайной вершины до t
# При телепортации Оля оказывается в любой из N вершин с вероятностью 1/N
expected_dist_to = [0.0] * N
for t in range(N):
    expected_dist_to[t] = sum(dist[x][t] for x in range(N)) / N

# 3. Расчёт среднего сокращения пути по всем парам s != t
total_reduction = 0.0
pairs_count = N * (N - 1)

for s in range(N):
    for t in range(N):
        if s == t:
            continue
        # Выигрыш от телепортации: если ожидаемый путь меньше прямого
        gain = max(0.0, dist[s][t] - expected_dist_to[t])
        total_reduction += gain

mean_reduction = total_reduction / pairs_count

print(f"Суммарное сокращение: {total_reduction:.6f} км")
print(f"Среднее сокращение: {mean_reduction:.6f} км")

Принцип работы алгоритма:

1. Тройной цикл Флойда — Уоршелла последовательно перебирает каждую вершину $k$ в качестве промежуточной и обновляет расстояние $d(i, j) = \min(d(i, j), d(i, k) + d(k, j))$.
2. Массив expected_dist_to[t] заранее накапливает среднее значение пути до цели $t$, что снижает сложность последующего расчёта с $O(N^3)$ до $O(N^2)$.
3. Для каждой пары $(s, t)$ проверяется целесообразность телепортации: если прямое расстояние $d(s, t)$ больше $\mathbb{E}[d(X, t)]$, кувшин применяется сразу на старте, сокращая маршрут на $d(s, t) - \mathbb{E}[d(X, t)]$.

Число $2020_{10} = 11111100100_2$, в его двоичной записи содержится $7$ единиц.

Дано:

• Десятичное число: $A_{10} = 2020$
• Основание целевой системы счисления: $q = 2$

Найти:

• Двоичное представление числа: $A_2$ — ?
• Количество единиц в двоичной записи: $N_1$ — ?

Решение:

1. Алгоритм перевода делением на основание. Для перевода целого числа из десятичной системы счисления в двоичную выполняется последовательное деление исходного числа и получаемых целых частных на $2$ с фиксацией остатков до тех пор, пока частное не станет равным нулю. Результат записывается из остатков от деления в обратном порядке (снизу вверх).

2. Вычисления. Выполняем последовательное деление:

Записываем остатки в обратном порядке:

3. Подсчёт количества единиц. Считаем количество цифр $1$ в полученной двоичной записи числа $11111100100_2$:

Ответ: $2020_{10} = 11111100100_2$; количество единиц: $7$.