Создание дерева решений для алгоритма сортировки слиянием

Question

В моей домашней работе мне нужно создать дерево решений для n = 3 для произвольного ввода S = {a, b, c}.

Вот мое рекурсивное дерево вызовов. S = {a, b, c} превращается в S = {a}, а S = {b, c} и S = ​​{b, c} превращается в S = {b} и S = ​​{c}. В базовом случае у меня есть S = {a}, S = {b} и S = ​​{c}.

Когда я объединяю S = {b} с S = {c}, у меня есть только 1 решение, проверьте, если b

Все, что возвращается предыдущим слиянием b и c, объединяется с S = {a}.

При слиянии S = ​​{a} и S = ​​{b, c} у меня есть несколько решений. Сначала я проверяю, является ли Это подводит меня к моему затруднению. Как мне объединить всю мою работу в одно дерево решений? Я могу без проблем создать дерево решений для итерационных алгоритмов, но, поскольку этот алгоритм рекурсивный, я запутался.

Любая помощь приветствуется. Спасибо.

Answer 1

Вы должны будете следовать патчу, начиная с самого глубокого уровня рекурсии. В этом случае вершина дерева выглядит так: «if (b <= c)». Тогда если true, как вы уже упоминали, это "if (a <= b") S = {a, b, c} else "if (a <= c") S = {b, a, c} "" else S = {b, c, a} ", то шаблон аналогичен для случая, когда« if (b <= c) »ложно. </p>

Я не уверен в этом. В случае n = 4, у вас есть 24 возможных перестановок, для n = 5, 120 перестановок, довольно большое дерево.