Цитата mrcnn:
Какой структурой данных можно организовать хранение дерева?
Глубина дерева не ограничена.
Максимальное число ветвей на каждый узел - 4. »
|
Код:
struct Node {
Node *children[4];
};
ня?
Цитата mrcnn:
|
Дана матрица 10x10. Нужно обойти все элементы всеми возможными способами. Упростим задачу, предположив, что каждый узел можно посетить только один раз. Решение должно быть без рекурсии, и решение должно позволять возврат назад. »
|
Яндекс, друг молодёжи. Матрица - тот же граф, по сути. Вершины - клетки матрицы, рёбра - переходы по горизонтали/вертикали в соседние клетки. Без рекурсии не реализуется, можно обойтись банальным стеком, но по сути - та же рекурсия.
Цитата mrcnn:
|
Как вариант другая задача, обойти матрицу 10x10, состоящую из 1 и 2, так чтобы не была посещена ни одна 1. Элемент можно посетить несколько раз. »
|
Те же яйца, вид сбоку. Вершины - клетки содержащие "2", рёбра - переходы в соседние двойки. Проблему составляет разрешение переходить назад. Вот такая матрица обычным поиском в глубину не обойдётся:
Код:
22222
21212
Для того, чтобы её обойти можно завести ещё одну матрицу - со счётчиком посещений вершины. И при очередном шаге поиска всегда идти в вершину с наименьшим числом посещений. В частности для матрицы приведённой выше, если мы начали путь в точке (2,1), то через 5 ходов матрица со счётчиками будет выглядеть так (соответственно находимся в точке (2,3)):
Код:
11100
10100
после этого, надо перейти в (1,3):
Код:
11200
10100
и в (2,3) на следующем шаге _не_ пойдём, т.к. там счётчик 1, а в (1,4) - пойдём, т.к. там ноль.
Можно доказать, что этот алгоритм всегда обходит все вершины, входящие в компоненту связности. Хотя, вероятно, и не самым оптимальным способом (не за минимальное число шагов).
В общем, читайте нормальный книжки по структурам данных и алгоритмам. Их много. Стандартные алгоритмы почти всегда можно адаптировать под свою задачу.
