Блог FX’а

11 Responses to “Небольшая задачка”

1. 1. Kamashev Max Says:
   September 15th, 2007 at 00:59

   Использовать DOM функции, там с деревом работать просто :)

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

   Или нужен алгоритм с минимумом строк кода?

2. 2. FX Poster Says:
   September 15th, 2007 at 01:01

   Нет. Нужен максимально оптимальный алгоритм. Хоть на псевдокоде. Сложность алгоритма, который получился у меня - O(n), n - кол-во узлов.

3. 3. Andrew Kornilov Says:
   September 15th, 2007 at 01:16

   вот на питоне. только разъехалось форматирование :)
   работает с нелинейной нумерацией parent_id (то бишь, они могут быть 1,3,10 и всё)

   #!/usr/bin/python
   in_f = open('./inf','r+')
   goods = {}
   in_arr = in_f.readlines()
   max_ppid = 0
   for in_str in in_arr:
       (pid,ppid,name) = in_str.split('|')
       if (goods.has_key(ppid)):
           goods[ppid].append([pid,name])
       else:
           goods[ppid] = [[pid,name]]
       if (int(ppid) > max_ppid):
           max_ppid = int(ppid)
   for index in range(int(max_ppid+1)):
       if (not goods.has_key(str(index))):
           continue
       for index2 in range(len(goods[str(index)])):
           print '\\t' * int(index),'%s %s' % (goods[str(index)][index2][0],goods[str(index)][index2][1])

4. 4. Kallisto Says:
   September 15th, 2007 at 01:22

   net sets только в текстовике походу..

5. 5. Andrew Kornilov Says:
   September 15th, 2007 at 01:24

   Ясень пень, что не оптимально, нет проверок на все ошибки и т.п. Но общий смысле же понятен :)

6. 6. FX Poster Says:
   September 15th, 2007 at 01:28

   Ахуенный код просто. Только неправильно работающий немного ;)

7. 7. Andrew Kornilov Says:
   September 15th, 2007 at 01:33

   По диагонали прочитал задание. Там еще надо учитывать кое-что. Ладно, допишем :)

8. 8. Артём Курапов Says:
   September 15th, 2007 at 18:48

   Делал нечто подобное для генерации дерева, правда все данные хранились в базе. В основе там была функция рекурсивная, работала по принципу “начать сверху, найти детей и сделать то же самое для детей”.

   Есть задача поинтересней - отрисовка дерева только до тех веток, где название/содержание ветки (частично) совпадает с поисковым словом

9. 9. FX Poster Says:
   September 16th, 2007 at 00:04

   Тут суть в том - как быстро построить это самое дерево. Конкретных реализаций я пока что так и не увидел. :(

10. 10. lyu Says:
    November 16th, 2007 at 01:41

    Честно говоря малость удивлёт отсутствием решений. Вой мой вариант.

    class FileTree
    {
           protected $tree = array();
    
           public function __construct($filename)
           {
           $f = file($filename);
           foreach ($f as $s) $this->AddNode(explode('|', trim($s)));
           }
    
           public function ShowTree($parent_id = 0, $level = 0)
           {
           foreach ($this->tree[$parent_id] as $node)
           {
                   echo str_repeat("\t", $level), $node['name'], "\n";
                   if (!empty($this->tree[$node['id']])) $this->ShowTree($node['id'], $level+1);
           }
           }
    
           protected function AddNode($nodeStruct)
           {
                   list($node_id, $parent_id, $node_name) = $nodeStruct;
                   $this->tree[$parent_id][] = array('id' => $node_id, 'name' => $node_name);
           }
    }
    
    $tree = new FileTree('file.txt');
    $tree->ShowTree();

11. 11. FX Poster Says:
    November 16th, 2007 at 02:56

    Просто вот мое решение. :)

Leave a Reply

Name (required)

Mail (will not be published) (required)

Website

Subscribe to comments