Имя пользователя:
Пароль:  
Помощь | Регистрация | Забыли пароль?  | Правила  

Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » Теория - Деревья, обход матрицы

Ответить
Настройки темы
Теория - Деревья, обход матрицы

Ветеран


Сообщения: 1397
Благодарности: 131


Конфигурация

Профиль | Отправить PM | Цитировать


Какой структурой данных можно организовать хранение дерева?
Глубина дерева не ограничена.
Максимальное число ветвей на каждый узел - 4.

Предположим, задача следующая:
Дана матрица 10x10. Нужно обойти все элементы всеми возможными способами. Упростим задачу, предположив, что каждый узел можно посетить только один раз. Решение должно быть без рекурсии, и решение должно позволять возврат назад.

Как вариант другая задача, обойти матрицу 10x10, состоящую из 1 и 2, так чтобы не была посещена ни одна 1. Элемент можно посетить несколько раз.

Каким образом решаются подобные задачи?

Отправлено: 11:55, 09-07-2008

 

редкий гость


Сообщения: 1696
Благодарности: 44

Профиль | Сайт | Отправить PM | Цитировать


Цитата 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) - пойдём, т.к. там ноль.

Можно доказать, что этот алгоритм всегда обходит все вершины, входящие в компоненту связности. Хотя, вероятно, и не самым оптимальным способом (не за минимальное число шагов).

В общем, читайте нормальный книжки по структурам данных и алгоритмам. Их много. Стандартные алгоритмы почти всегда можно адаптировать под свою задачу.

-------
http://ivank.ru


Отправлено: 03:57, 10-07-2008 | #2



Для отключения данного рекламного блока вам необходимо зарегистрироваться или войти с учетной записью социальной сети.

Если же вы забыли свой пароль на форуме, то воспользуйтесь данной ссылкой для восстановления пароля.



Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » Теория - Деревья, обход матрицы

Участник сейчас на форуме Участник сейчас на форуме Участник вне форума Участник вне форума Автор темы Автор темы Шапка темы Сообщение прикреплено

Похожие темы
Название темы Автор Информация о форуме Ответов Последнее сообщение
C/C++ - [решено] Нахождение обратной матрицы методом Гаусса и рассширенной матрицы D.Y. Программирование и базы данных 64 06-05-2011 22:59
Ноутбук без матрицы systeman Ноутбуки 0 10-11-2009 17:09
C/C++ | Матрицы Kuron Программирование и базы данных 2 21-01-2007 10:09
c++.NET выравнивание матрицы bezumes Программирование и базы данных 4 22-04-2006 01:20
Формирование матрицы Sergey Po Программирование и базы данных 3 28-04-2004 04:47




 
Переход