⚙️ Алгоритмы  ·  20 вопросов  ·  ~45 мин  ·  ⏱ Таймер 45:00  ·  Сложный  · 

Жадные алгоритмы

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

Отвечено: 0 из 20
⏱ --:--
0%
💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 45 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.
Вопрос 1 из 20
Какие интервалы выберет алгоритм?
Python
intervals = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (7, 8)]
intervals.sort(key=lambda x: x[1])
chosen = []
end = float('-inf')
for start, finish in intervals:
    if start >= end:
        chosen.append((start, finish))
        end = finish
print(chosen)
Вопрос 2 из 20
Какие монеты выберет правило «каждый раз брать крупнейший подходящий номинал»?
4+1+1=6
Python
coins = [1, 3, 4]
amount = 6
used = []
for coin in sorted(coins, reverse=True):
    while amount >= coin:
        amount -= coin
        used.append(coin)
print(used)
Вопрос 3 из 20
В дробном рюкзаке предметы можно делить. Какой локальный выбор оптимален?
\rho_i=\frac{v_i}{w_i}
Вопрос 4 из 20
Какие два символа будут объединены первыми и какой вес получит новый узел?
Python
from heapq import heapify, heappop, heappush
heap = [(5, 'A'), (9, 'B'), (12, 'C'), (13, 'D')]
heapify(heap)
x = heappop(heap)
y = heappop(heap)
print(x[1], y[1], x[0] + y[0])
Вопрос 5 из 20
При построении минимального остова алгоритмом Краскала какой следующий шаг выполняется?
Вопрос 6 из 20
Какой обмен лежит в основе доказательства выбора раннего окончания?
Python
greedy_first = (1, 3)      # заканчивается раньше всех
optimal_first = (0, 5)     # первое событие в некотором оптимуме
rest = [(5, 7), (7, 9)]

# Нужно обосновать замену optimal_first на greedy_first,
# не уменьшая число мероприятий в расписании.
Вопрос 7 из 20
Что нужно доказать помимо свойства жадного выбора?
Вопрос 8 из 20
Почему выбор двух минимальных частот безопасен в коде Хаффмана?
Python
from heapq import heapify, heappop, heappush

frequencies = [2, 3, 7, 9, 18]
heapify(frequencies)
while len(frequencies) > 1:
    x = heappop(frequencies)
    y = heappop(frequencies)
    heappush(frequencies, x + y)

# На каждом шаге объединяются две минимальные частоты.
Вопрос 9 из 20
Какой признак отличает доказанный жадный алгоритм от эвристики?
Вопрос 10 из 20
Какое свойство используется в алгоритме Прима?
Python
from heapq import heappop

used = {0, 2}
frontier = [(3, 2, 1), (5, 0, 3), (8, 2, 4)]

weight, inside, outside = heappop(frontier)
used.add(outside)
# Затем в очередь добавляются рёбра новой вершины.
Вопрос 11 из 20
Какой результат даст жадный 0/1-рюкзак по плотности?
Python
items = [(60, 10), (100, 20), (120, 30)]  # (value, weight)
capacity = 50
items.sort(key=lambda p: p[0] / p[1], reverse=True)
value = 0
for v, w in items:
    if w <= capacity:
        capacity -= w
        value += v
print(value)
Вопрос 12 из 20
Какой набор номиналов и суммы опровергает правило «всегда брать крупнейшую монету» для минимума числа монет?
Вопрос 13 из 20
Почему выбор ближайшей по весу ещё не посещённой вершины не гарантирует минимальный гамильтонов цикл?
Python
# Произвольные стоимости переходов в полном взвешенном графе.
distance = [
    [0,   1,   2, 100],
    [1,   0,   1,   2],
    [2,   1,   0,   1],
    [100, 2,   1,   0],
]

current = 0
unvisited = {1, 2, 3}
route = [current]
while unvisited:
    current = min(unvisited, key=lambda v: distance[current][v])
    unvisited.remove(current)
    route.append(current)
route.append(route[0])
Вопрос 14 из 20
Почему правило «в лабиринте всегда идти в соседнюю клетку, ближайшую по прямой к выходу» может провалиться?
Вопрос 15 из 20
Что произойдёт, если первым выбрать самый короткий интервал \( (3,5) \)?
Python
intervals = [(0, 4), (4, 8), (3, 5)]
Вопрос 16 из 20
Сколько комнат нужно?
Python
meetings = [(0, 10), (5, 7), (6, 8), (9, 12)]
events = []
for s, e in meetings:
    events.append((s, 1))
    events.append((e, -1))
events.sort(key=lambda x: (x[0], x[1]))
current = best = 0
for _, delta in events:
    current += delta
    best = max(best, current)
print(best)
Вопрос 17 из 20
Какой суммарный вес получит лес Краскала?
Python
edges = [(1,0,1),(2,1,2),(3,0,2),(4,2,3),(5,1,3)]
parent = list(range(4))
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x
total = 0
for w,u,v in sorted(edges):
    ru, rv = find(u), find(v)
    if ru != rv:
        parent[rv] = ru
        total += w
print(total)
Вопрос 18 из 20
Какой алгоритм нужен, чтобы минимизировать среднее время ожидания независимых заданий на одном процессоре, если все доступны сразу?
Вопрос 19 из 20
Какую стоимость кода Хаффмана создаёт первый этап?
Python
frequencies = [2, 3, 7, 9]
# объединяем 2 и 3 -> 5; затем 5 и 7 -> 12; затем 9 и 12 -> 21
cost = 5 + 12 + 21
print(cost)
Вопрос 20 из 20
Какой инструмент делает выбор следующего минимального элемента эффективным в Хаффмане и Приме?
O((V+E)\log V)

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу