Автор Тема: [Все] Полный путь в графе  (Прочитано 9093 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Yashied [?]

  • AutoIt MVP
  • Глобальный модератор
  • *
  • Сообщений: 5349
  • Репутация: 2691
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.x.x
Есть следующий граф (дерево):


Из каждого узла может выходить максимум две ветки. Т.е. максимальное количество узлов (N) на каждом следующем уровне (i) удваивается по сравнению с предыдущим:

Ni = 2 ^ (i - 1)
Задается такой граф в виде последовательности строк, определяющих каждый уровень дерева, например:

Уровень 1: A
Уровень 2: B, C
Уровень 3: D, E, F, G
Уровень 4: H, I, J, K, L, M, N, O

и т.д.

A, B, C, ... - это просто названия узлов (могут быть произвольными).

Для полного описания графа используется массив:

$aGraph[15] = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']

Длина массива всегда равна максимально возможному количеству узлов в графе, в данном случае:

1 + 2 + 4 + 8 = 15
Если какие-нибудь узлы отсутствуют, то используются пустые строки, например:

Код: AutoIt [Выделить]
$aGraph[15] = ['A', 'B', 'C', 'D', 'E', 'F', 'G', '', 'H', '', '', 'I', 'J', 'K', '']



Самый верхний узел A (1-ый уровень) всегда должен присутствовать.

Задание

Написать алгоритм (функцию) для нахождения полного пути от вершины A до требуемого узла в таком дереве. Например, полный путь до узла J в предыдущем графе будет выглядеть так:


В качестве исходных данных есть только сам граф ($aGraph) и название узла в нем, например "J", путь до которого необходимо определить. Результат должен представлять из себя строку вида (для данного примера):

A-C-F-J
Примечание

Исходный граф может иметь произвольное количество уровней, начиная с 1, и произвольное количество отсутствующих вершин, но всегда имеет описанную выше древовидную структуру.
« Последнее редактирование: Март 08, 2012, 19:43:55 от Yashied »


Думай, прежде чем говорить.

Русское сообщество AutoIt

[Все] Полный путь в графе
« Отправлен: Март 08, 2012, 19:35:26 »

Оффлайн C2H5OH [?]

  • Знаю я тут одно место с офигенными циркулями...
  • AutoIt Гуру
  • *****
  • Сообщений: 1473
  • Репутация: 330
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.12.0
Re: [Все] Полный путь в графе
« Ответ #1, Отправлен: Март 08, 2012, 20:15:40 »
Код тут выкладывать или в личку?
Рано или поздно все станет понятно, все станет на свои места и выстроится в единую красивую схему, как кружева. Станет понятно, зачем все было нужно, потому что все будет правильно.

Оффлайн Yashied [?]

  • AutoIt MVP
  • Глобальный модератор
  • *
  • Сообщений: 5349

  • Автор темы
  • Репутация: 2691
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.x.x
Re: [Все] Полный путь в графе
« Ответ #2, Отправлен: Март 08, 2012, 20:18:34 »
Код тут выкладывать или в личку?

Тут.

Оффлайн C2H5OH [?]

  • Знаю я тут одно место с офигенными циркулями...
  • AutoIt Гуру
  • *****
  • Сообщений: 1473
  • Репутация: 330
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.12.0
Re: [Все] Полный путь в графе
« Ответ #3, Отправлен: Март 08, 2012, 20:20:19 »
Хотя, вообще-то рекурсию очень уважаю...

(нажмите для показа/скрытия)

Русское сообщество AutoIt

Re: [Все] Полный путь в графе
« Ответ #3 Отправлен: Март 08, 2012, 20:20:19 »

Оффлайн Kaster [?]

  • Бритва, Бритва Оккама
  • Глобальный модератор
  • *
  • Сообщений: 4016
  • Репутация: 622
  • Пол: Мужской
  • Мой Аватар, он лучший самый
    • Награды
  • Версия AutoIt: 3.3.14.0
Re: [Все] Полный путь в графе
« Ответ #4, Отправлен: Март 08, 2012, 22:49:38 »
вот для этой задачи ассоциативные массивы не помешали бы. ну по крайней мере для того решения, которое я вижу

Оффлайн Yashied [?]

  • AutoIt MVP
  • Глобальный модератор
  • *
  • Сообщений: 5349

  • Автор темы
  • Репутация: 2691
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.x.x
Re: [Все] Полный путь в графе
« Ответ #5, Отправлен: Март 09, 2012, 05:20:36 »
Ладно, раз больше никого нет, то вот мой вариант. Немного сложнее, но зато с рекурсией.

Код: AutoIt [Выделить]
;~         A
;~       /   \
;~     B       C
;~   /   \       \
;~ D       E       F
;~       /       /   \
;~     G       H       I
;~           /   \
;~         J       K

Dim $aGraph[31] = ['A', 'B', 'C', 'D', 'E', '', 'F', '', '', 'G', '', '', '', 'H', 'I', '', '', '', '', '', '', '', '', '', '', '', '', 'J', 'K', '', '']

Func _Path(ByRef $aGraph, $sItem, $iIndex = 0, $sPath = '')
    If Not $aGraph[$iIndex] Then
        Return ''
    EndIf
    $sPath = StringRegExpReplace($sPath & '-' & $aGraph[$iIndex], '\A-+', '')
    If $aGraph[$iIndex] = $sItem Then
        Return $sPath
    EndIf
    $iIndex = 2 ^ Ceiling(Log($iIndex + 2) / Log(2)) + 2 * ($iIndex - 2 ^ (Ceiling(Log($iIndex + 2) / Log(2)) - 1) + 1) - 1
    If $iIndex < UBound($aGraph) - 1 Then
        For $i = 0 To 1
            Local $Path = _Path($aGraph, $sItem, $iIndex + $i, $sPath)
            If $Path Then
                Return $Path
            EndIf
        Next
    EndIf
    Return ''
EndFunc   ;==>_Path

ConsoleWrite(_Path($aGraph, 'K') & @CR)


Оффлайн C2H5OH [?]

  • Знаю я тут одно место с офигенными циркулями...
  • AutoIt Гуру
  • *****
  • Сообщений: 1473
  • Репутация: 330
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.12.0
Re: [Все] Полный путь в графе
« Ответ #6, Отправлен: Март 09, 2012, 08:40:40 »
Не понимаю...
Код: AutoIt [Выделить]
$iIndex = 2 ^ Ceiling(Log($iIndex + 2) / Log(2)) + 2 * ($iIndex - 2 ^ (Ceiling(Log($iIndex + 2) / Log(2)) - 1) + 1) - 1

:o

Почему не взять просто
Код: AutoIt [Выделить]
$iIndex = 2 * $iIndex + 1

???

Оффлайн Yashied [?]

  • AutoIt MVP
  • Глобальный модератор
  • *
  • Сообщений: 5349

  • Автор темы
  • Репутация: 2691
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.x.x
Re: [Все] Полный путь в графе
« Ответ #7, Отправлен: Март 09, 2012, 13:41:40 »
Почему не взять просто
Код: AutoIt [Выделить]
$iIndex = 2 * $iIndex + 1

???

:)

Русское сообщество AutoIt

Re: [Все] Полный путь в графе
« Ответ #7 Отправлен: Март 09, 2012, 13:41:40 »

 

Похожие темы

  Тема / Автор Ответов Последний ответ
11 Ответов
6562 Просмотров
Последний ответ Май 04, 2010, 20:59:47
от avmir
7 Ответов
4744 Просмотров
Последний ответ Январь 08, 2011, 20:50:03
от Sky-WaLkeR
2 Ответов
5474 Просмотров
Последний ответ Март 30, 2011, 12:13:09
от joiner
2 Ответов
2615 Просмотров
Последний ответ Март 26, 2012, 15:56:05
от Dimmak
3 Ответов
5129 Просмотров
Последний ответ Июль 24, 2015, 10:31:40
от Rioran
14 Ответов
5069 Просмотров
Последний ответ Сентябрь 18, 2014, 22:59:04
от glax24
6 Ответов
2054 Просмотров
Последний ответ Август 25, 2015, 04:16:38
от winix
0 Ответов
495 Просмотров
Последний ответ Октябрь 31, 2015, 03:07:39
от Δαηy Δαηy
0 Ответов
547 Просмотров
Последний ответ Ноябрь 07, 2015, 01:10:10
от Alofa
2 Ответов
318 Просмотров
Последний ответ Декабрь 10, 2016, 15:17:50
от FlankeR