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

Перебор и возврат с откатом

Возврат с откатом — это не просто рекурсия с циклом. Каждая ветвь должна получить чистое родительское состояние, а любое отсечение обязано исключать только заведомо бесполезные продолжения. В тесте есть перестановки, сочетания, подмножества, ферзи, копирование путей и оценки пространства поиска.

Отвечено: 0 из 20

⏱ --:--

💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 45 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.

Вопрос 1 из 20

Сколько листьев посетит полный перебор двоичных строк длины 5?

2^5=32

count = 0
def gen(pos, n):
    global count
    if pos == n:
        count += 1
        return
    gen(pos + 1, n)
    gen(pos + 1, n)
gen(0, 5)
print(count)

10 64 32 25

Вопрос 2 из 20

Сколько перестановок будет напечатано?

def perm(path, remaining):
    if not remaining:
        print(path)
        return
    for i in range(len(remaining)):
        perm(path + [remaining[i]], remaining[:i] + remaining[i+1:])

perm([], [1, 2, 3])

3 8 9 6

Вопрос 3 из 20

Какова грубая сложность полного перебора всех подмножеств n элементов, если проверка каждого занимает O(n)?

O(n\,2^n)

O(2ⁿ) O(n) O(n²) O(n·2ⁿ)

Вопрос 4 из 20

Сколько узлов дерева, включая неполные префиксы, создаст функция?

calls = 0
def build(pos):
    global calls
    calls += 1
    if pos == 3:
        return
    for _ in range(2):
        build(pos + 1)
build(0)
print(calls)

16 15 14 8

Вопрос 5 из 20

Какой порядок выбора переменных часто уменьшает дерево поиска в задачах ограничений?

Всегда начинать с последней по имени Сначала переменная с наименьшим числом допустимых значений Случайно менять уже присвоенные значения Сначала переменная с наибольшим числом допустимых значений

Вопрос 6 из 20

Почему функция печатает неверные пути?

path = []
def gen(n):
    if len(path) == n:
        print(path)
        return
    for x in [0, 1]:
        path.append(x)
        gen(n)
        # пропущено действие

Нужно печатать только длину Нужно заменить цикл на while Нужно очищать path перед append Нужно path.pop() после рекурсивного вызова

Вопрос 7 из 20

Какой список останется после завершения вызова?

path = []
def gen(pos):
    if pos == 2:
        return
    for x in [1, 2]:
        path.append(x)
        gen(pos + 1)
        path.pop()
gen(0)
print(path)

[] [2,2] [1,1,2,2] [1,2]

Вопрос 8 из 20

Что должно быть истинно после отката из рекурсивного вызова?

Все ограничения удаляются навсегда Состояние совпадает с тем, которое было до выбора текущей ветви Состояние содержит все решения предыдущих ветвей Глубина увеличивается

Вопрос 9 из 20

Какой дефект связан с добавлением path напрямую?

answers = []
path = []
def save():
    answers.append(path)

path.append(1); save(); path.pop()
path.append(2); save(); path.pop()
print(answers)

[[1],[2]] [[2],[2]] [[],[]] [1,2]

Вопрос 10 из 20

Когда копирование состояния вместо отката может быть разумным?

Когда копирование одной ветви дороже полного перебора её продолжений Когда все ветви должны совместно изменять один и тот же объект Когда состояние велико, но на каждом уровне меняется только один элемент Когда состояние небольшое и простота кода важнее дополнительной памяти

Вопрос 11 из 20

Какое отсечение безопасно в задаче набора положительных чисел до суммы target?

def search(i, total):
    if total > target:
        return
    ...

Остановить поиск после первого совпадения, даже если требуется найти все решения или лучшее Отсечь total<target, потому что дальнейшие положительные слагаемые только увеличат разрыв Отсечь нечётную текущую сумму при чётном target, не учитывая значения оставшихся чисел Отсечь total>target, потому что добавление положительных чисел уже не уменьшит сумму

Вопрос 12 из 20

Почему это отсечение может быть неверным при отрицательных числах?

def search(current_sum, target):
    if current_sum > target:
        return
    # здесь продолжается перебор оставшихся чисел
    ...

Отсечение только ускоряет, не меняя результат current_sum всегда равна target Отрицательные числа нельзя перебирать Поздний отрицательный элемент может уменьшить сумму обратно до target

Вопрос 13 из 20

В задаче минимизации найдено решение стоимости best. Когда ветвь можно безопасно отсечь?

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

Вопрос 14 из 20

Сколько размещений ферзей проверит база после отсечения по занятым столбцам для n=4?

def count_placements(row, used_columns, n):
    if row == n:
        return 1
    total = 0
    for column in range(n):
        if column not in used_columns:
            used_columns.add(column)
            total += count_placements(row + 1, used_columns, n)
            used_columns.remove(column)
    return total

print(count_placements(0, set(), 4))
# Диагонали пока не проверяются.

4 16 24 256

Вопрос 15 из 20

Как выбор следующего кандидата по эвристике влияет на корректность, если никакие ветви не удаляются?

Меняет порядок поиска, но не множество рассмотренных решений Гарантирует оптимальность первого найденного решения без дополнительного доказательства Может потерять решения, даже если каждый допустимый кандидат всё равно будет перебран Изменяет само условие допустимости решения, хотя проверки и отсечения остались прежними

Вопрос 16 из 20

Какие сочетания длины 2 будут сгенерированы?

a = [1, 2, 3, 4]
out = []
def choose(start, path):
    if len(path) == 2:
        out.append(path.copy())
        return
    for i in range(start, len(a)):
        path.append(a[i])
        choose(i + 1, path)
        path.pop()
choose(0, [])
print(out)

[[1,1],[2,2],[3,3],[4,4]] Только [[1,2],[3,4]] [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] [[1,2],[2,1],[1,3],[3,1]]

Вопрос 17 из 20

Сколько уникальных перестановок у [1,1,2]?

# одинаковые единицы не различаются

6 2 3 9

Вопрос 18 из 20

Как избежать дублей при генерации перестановок массива с повторами?

Сначала получить все перестановки, а затем удалить лишь соседние совпадения без полного сравнения Менять порядок кандидатов случайно и считать равные значения различными по исходным позициям Отсортировать вход и запрещать повторяющееся значение на всех уровнях, независимо от префикса На каждом уровне не выбирать одно и то же значение повторно из разных равных позиций

Вопрос 19 из 20

Сколько подмножеств будет добавлено?

a = [1, 2, 3]
out = []
def subsets(i, path):
    if i == len(a):
        out.append(path.copy())
        return
    subsets(i + 1, path)
    path.append(a[i])
    subsets(i + 1, path)
    path.pop()
subsets(0, [])
print(len(out))

6 8 7 9

Вопрос 20 из 20

Чем размещения отличаются от сочетаний?

P(n,k)=\frac{n!}{(n-k)!},\quad C(n,k)=\frac{n!}{k!(n-k)!}

В сочетаниях порядок важен, а в размещениях учитывается только состав Различие только в способе генерации; число вариантов всегда одинаково Сочетания различают {1, 2} и {2, 1}, если исходные элементы уникальны В размещениях важен порядок выбранных элементов, в сочетаниях — нет

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

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

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

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