[Москва] ищется php-гуру

AnToXa

prodigy-одаренный ребенок
неужто всё XOR`ишь? :O
не, при некоторых предположениях, которые почти всегда верны на современных архитектурах, можно впихнуть в структуру флаг "мы тут уже были" и его просто проверять и всех дел :)

предположения следующие:
1. указатели размером больше байта
2. структуры лежат выравненными на размер указателя.

тогда у указателя младший бит будет всегда == 0, вот его можно и заюзать.
 

fixxxer

К.О.
Партнер клуба
как же это - с Java работаешь, а паттерна Delegation не знаешь?

P.S. PHP, Java, C#, C, ASM - нет никакой принципиальной разницы. можно писать ОО-код на голом Си.

AnToXa: подобную мысль я как-то сразу отбросил. Слишком уж грязный хак =)
 
Автор оригинала: fixxxer
как же это - с Java работаешь, а паттерна Delegation не знаешь?

P.S. PHP, Java, C#, C, ASM - нет никакой принципиальной разницы. можно писать ОО-код на голом Си.
Такого патерна не знаю, либо его нет вообще, либо он называется иначе (полагаю стратегия), либо дайте ссылку на него.

p.s. Писать ОО код на функциональном языке типа C... забавная шутка...
 

fixxxer

К.О.
Партнер клуба
>забавная шутка
Все ясно, бисер метать влом. В гугл иди.
 

algo

To the stars!
Ого.. Алга оказывается php-гура ;)
... Эта...
А вы языком не ошиблись ?
 

valyala

Новичок
дано: односвязный список произвольной длинны. о структурах в этом
списке известно только то, что каждая из них содержит указатель либо на
другую структуру, либо в null.

задача: установить, цикличный это список или нет. алгоритм должен быть
максимально оптимизирован по потреблению памяти, процессорное время - не
учитывать.
Гы) Если перефразировать задачу на Си, то получится следующее.
Дано:
Код:
typedef struct List List;

int is_cyclic(List *list);
Известно, что struct List содержит где-то внутри себя указатель на следующий элемент:
Код:
struct List {
/* foo struct members */
struct List *next;
/* bar struct members */
};
. Про foo и bar члены структуры ничего не известно. Необходимо реализовать функцию is_cyclic(), чтобы она возвращала 1, если список list является циклическим. Иначе функция должна вернуть 0.

Если неизвестно смещение указателя на следующий элемент списка в структуре List (т.е. значение offsetof(List, next) ), то задача неразрешима.

Ну а если структура List определена или хотя бы известно смещение next, то это задача для детсада:
Код:
int is_cyclic(List *list) {
    List *first = list;

    if (list == NULL) return 0;
    for (list = list->next; list != NULL; list = list->next) {
        if (first == list) {
            /* обнаружен цикл */
            return 1;
        }
    }
    /* напоролись на NULL, т.е. цикла нет */
    return 0;
}
 

Andreika

"PHP for nubies" reader
valyala
это задача не на с++.. это алгоритм.. просто на цэ понятно что есть такое указатель и что есть такое занимаемая память

все гениальное просто.. но вы не учитываете, что зацикливаться оно должно не обязательно с началом списка
1->2->3->4->2->3->4->2 ...

а вообще - на тройку ее на порядок сложнее решить, чем на 5ку.. а оптимизации по используемому времени вообще чет не придумывается :(

AnToXa
mk:mad:MSITStore:C:\php_manual_ru.chm::/ru/language.operators.logical.html
:)
 

Wicked

Новичок
Andreika
какая там может быть оптимизация лучше, чем О(n) ? :) Имхо даже в самом худшем случае требуется около 3-х проходов по списку.
 

valyala

Новичок
я вот тут подумал - а ведь цикл не обязательно должен выглядеть так:
1 -> 2 -> .... n -> 1

Он может выглядеть и так:
1 -> 2 -> ... -> m -> ... -> n -> m

Тогда алгоритм is_cyclic() немного усложняется и не вкладывается в поставленные ограничения - кроме памяти, необходимой для указателей list и first, в стеке используется дополнительная память для переменных depth и i... Так что алгоритм только на троечку ;)
Код:
int is_cyclic(List *list) {
    List *first = list;
    int depth = 1; /* глубина поиска цикла */

    if (list == NULL) return 0;
    for (;;) {
        for (int i = 0; i < depth; i++) {
            list = list->next;
            if (list == NULL) {
                /* напоролись на NULL -> конец списка, т.е. цикла нет */
                return 0;
            }

            if (list == first) {
                /* обнаружен цикл */
                return 1;
            }
        }

        /* увеличиваем глубину поиска одновременно с
          * продвижением в глубину списка */
        depth++;
        first = first->next;
        list = first;
    }
    /* цикл for (;;) завершится в любом случае выходом из функции */
}
 

Wicked

Новичок
valyala:
1) про зацикливание Андрейка написал 2-мя поставми выше.
2) тут PHP-клаб.
3) не думаю, что работодатель будет в восторге, если Вы раскроете решение прямо в этой ветке. Хотя Вы почти это самое и сделали.
 

Wicked

Новичок
тем не менее, основную идею он выхватил. но реализовал криво.
 

Фанат

oncle terrible
Команда форума
Вставлю я свои 5 копеек.
Я думаю, что такая интересная беседа - явление настолько здесь, к сожалению, редкое, что работодатель, надеюсь, простит участников.

Тем более, что, на мой взгляд, задания - это, скорее, ценз для соискателей, чем гарантия принятия на работу.
Достаточно будет того, чтобы соискатель задание хотя бы понял ;-)

Засим удаляюсь.
 

StUV

Rotaredom
и-нет завален решениями этой задачки
(хх-класс средней школы, уроки информатики ;))
 

AnToXa

prodigy-одаренный ребенок
Автор оригинала: valyala
я вот тут подумал - а ведь цикл не обязательно должен выглядеть так:
1 -> 2 -> .... n -> 1

Он может выглядеть и так:
1 -> 2 -> ... -> m -> ... -> n -> m

Тогда алгоритм is_cyclic() немного усложняется и не вкладывается в поставленные ограничения - кроме памяти, необходимой для указателей list и first, в стеке используется дополнительная память для переменных depth и i... Так что алгоритм только на троечку ;)
Код:
int is_cyclic(List *list) { [порезано] }
это решение имеет сложность O(n^2) если вы заметили.
 

valyala

Новичок
у него гавно а не решение
это решение имеет сложность O(n^2) если вы заметили.
ввиду перечисленных выше замечаний привожу решение со сложностью O(n), написанное на ПХП:
PHP:
bool is_cyclic($list)
{
    if ($first == null) return false;

    $depth = 1;
    for (;;) {
        $first = $list;
        for ($i = 0; $i < $depth; $i++) {
            $list = $list->next;
            if ($list == null) return false;
            if ($list == $first) return true;
        }
        $depth += $depth;
    }
}
 
Сверху