Необходимо использовать 2 указателя, один из которых будет двигаться "быстрее", другой "медленнее", в конечном итоге, если есть зацикливание, в определенный момент оба указателя будут находиться в одном и том же узле. http://en.wikipedia.org/wiki/Cycle_detection
Картинка-пример, с черепахой и зайцем.
_____________
Mysql, Postgresql, Redis, Memcached, Unit Testing, CI, Kohana, Yii, Phalcon, Zend Framework, Joomla, Open Cart, Ymaps, VK Api
Полная Версия: Меня порвали как специалиста
Или можно булевое значение хранить. Или на бит у нас тоже памяти нет?
Как бы выразился тех дир. - "Представим, что у узлов склероз".
Вариант с черепахой и зайцем является самым эффективным алгоритмом по выявлению зацикливаний на сегодняшний день.
_____________
Mysql, Postgresql, Redis, Memcached, Unit Testing, CI, Kohana, Yii, Phalcon, Zend Framework, Joomla, Open Cart, Ymaps, VK Api
Вариант с черепахой и зайцем является самым эффективным алгоритмом по выявлению зацикливаний на сегодняшний день.
_____________
Mysql, Postgresql, Redis, Memcached, Unit Testing, CI, Kohana, Yii, Phalcon, Zend Framework, Joomla, Open Cart, Ymaps, VK Api
T1grOK
Хм. Надо покурить.
Ты бы сразу сказал)
Хм. Надо покурить.
Ты бы сразу сказал)
| Цитата (T1grOK @ 25.04.2015 - 18:57) |
| Необходимо использовать 2 указателя, один из которых будет двигаться "быстрее", другой "медленнее", в конечном итоге, если есть зацикливание, в определенный момент оба указателя будут находиться в одном и том же узле. http://en.wikipedia.org/wiki/Cycle_detection Картинка-пример, с черепахой и зайцем. |
Я бы пошел другим путем!
Предполагаю что у крайнего правого эл-та указатель на следующий элемент равен нулю. Если оказывается что элемента у которого указатель на следующий элемент не равен нулю, то запускается функция определения цикла которая сохраняет состояние текущего элемента и продолжает двигаться вперед при каждой смене состояния сравнивая текущее состояние с сохраненным. Если оно совпадает - граф замкнутый.
_____________
Трус не играет в хокей
Zzepish
Имел бы ты хотя бы 1 год практики в разработке сайтов, так бы не говорил.
_____________
Обучаю веб-программированию качественно и не дорого: http://school-php.com
Фрилансер, принимаю заказы: PHP, JS, AS (видео-чаты). Писать в ЛС (Личные сообщения на phpforum).
Имел бы ты хотя бы 1 год практики в разработке сайтов, так бы не говорил.
_____________
Обучаю веб-программированию качественно и не дорого: http://school-php.com
Фрилансер, принимаю заказы: PHP, JS, AS (видео-чаты). Писать в ЛС (Личные сообщения на phpforum).
inpost
а я не конкретно про сайты говорю
а я не конкретно про сайты говорю
Zzepish
и чем ты собираешься заниматься на PHP, если сам язык основан на разработку сайтов?
_____________
Обучаю веб-программированию качественно и не дорого: http://school-php.com
Фрилансер, принимаю заказы: PHP, JS, AS (видео-чаты). Писать в ЛС (Личные сообщения на phpforum).
и чем ты собираешься заниматься на PHP, если сам язык основан на разработку сайтов?
_____________
Обучаю веб-программированию качественно и не дорого: http://school-php.com
Фрилансер, принимаю заказы: PHP, JS, AS (видео-чаты). Писать в ЛС (Личные сообщения на phpforum).
T1grOK
кстати- ты не уточнил: граф тупо тот, который дали, или любой? т.е. сколько угодно ветвлений и т.д.
кстати- ты не уточнил: граф тупо тот, который дали, или любой? т.е. сколько угодно ветвлений и т.д.
inpost
да я уже решал кое-какие задачки не связанные с сайтостроением.
А вообще- я сейчас перелажу на java. Кроме того- такие задачки хорошо развивают мозги
да я уже решал кое-какие задачки не связанные с сайтостроением.
А вообще- я сейчас перелажу на java. Кроме того- такие задачки хорошо развивают мозги
Zzepish
На PHP? И где-то используется? Мы сейчас обсуждаем вакансию ПХП.
_____________
Обучаю веб-программированию качественно и не дорого: http://school-php.com
Фрилансер, принимаю заказы: PHP, JS, AS (видео-чаты). Писать в ЛС (Личные сообщения на phpforum).
На PHP? И где-то используется? Мы сейчас обсуждаем вакансию ПХП.
_____________
Обучаю веб-программированию качественно и не дорого: http://school-php.com
Фрилансер, принимаю заказы: PHP, JS, AS (видео-чаты). Писать в ЛС (Личные сообщения на phpforum).
inpost
там как пойдет фантазия. пхп не только для веба можно юзать.
Как говорил Гесер из дозоров: вы не имеете права спашивать- зачем я забиваю гвозди микроскопом!
там как пойдет фантазия. пхп не только для веба можно юзать.
Как говорил Гесер из дозоров: вы не имеете права спашивать- зачем я забиваю гвозди микроскопом!
Zzepish
Ты утверждаешь, что та фирма, на которую устраивался ТС делают не веб-сайты на PHP ? Давай не будем фантазировать, я уверен на 99% что там требуется делать стандартные вещи на ПХП, которыми занимается даже юниор на более непрофессиональном уровне.
_____________
Обучаю веб-программированию качественно и не дорого: http://school-php.com
Фрилансер, принимаю заказы: PHP, JS, AS (видео-чаты). Писать в ЛС (Личные сообщения на phpforum).
Ты утверждаешь, что та фирма, на которую устраивался ТС делают не веб-сайты на PHP ? Давай не будем фантазировать, я уверен на 99% что там требуется делать стандартные вещи на ПХП, которыми занимается даже юниор на более непрофессиональном уровне.
_____________
Обучаю веб-программированию качественно и не дорого: http://school-php.com
Фрилансер, принимаю заказы: PHP, JS, AS (видео-чаты). Писать в ЛС (Личные сообщения на phpforum).
T1grOK, вопрос был только про синглтон или другие паттерны тоже спрашивали?
_____________
Люди, имеющие низкий уровень квалификации, делают ошибочные выводы, принимают неудачные решения и при этом неспособны осознавать свои ошибки в силу низкого уровня своей квалификации
_____________
Люди, имеющие низкий уровень квалификации, делают ошибочные выводы, принимают неудачные решения и при этом неспособны осознавать свои ошибки в силу низкого уровня своей квалификации
Синглтон и DI.
Основной упор был на дополнительные задачи. Которые в данной теме рассматривались.
_____________
Mysql, Postgresql, Redis, Memcached, Unit Testing, CI, Kohana, Yii, Phalcon, Zend Framework, Joomla, Open Cart, Ymaps, VK Api
Основной упор был на дополнительные задачи. Которые в данной теме рассматривались.
_____________
Mysql, Postgresql, Redis, Memcached, Unit Testing, CI, Kohana, Yii, Phalcon, Zend Framework, Joomla, Open Cart, Ymaps, VK Api
Здесь расположена полная версия этой страницы.