⚙️ Алгоритмы · 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 25 32

Вопрос 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 6 9 8

Вопрос 3 из 20

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

O(n\,2^n)

O(n) O(n²) O(n·2ⁿ) O(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)

8 16 15 14

Вопрос 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)
        # пропущено действие

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

Вопрос 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)

[1,2] [2,2] [1,1,2,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
    # здесь продолжается перебор оставшихся чисел
    ...

Поздний отрицательный элемент может уменьшить сумму обратно до target Отсечение только ускоряет, не меняя результат current_sum всегда равна 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 24 16 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,2],[2,1],[1,3],[3,1]] [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] Только [[1,2],[3,4]] [[1,1],[2,2],[3,3],[4,4]]

Вопрос 17 из 20

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

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

9 6 3 2

Вопрос 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 9 7 8

Вопрос 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-страницу