ФорумПрограммированиеБольше языковC/C++ и C# → Поиск, почти как по дереву =((

Поиск, почти как по дереву =((

  • krasun

    Сообщения: 1370 Репутация: N Группа: Джедаи

    Spritz 29 октября 2009 г. 11:47, спустя 3 минуты 22 секунды

    Делаю класс - друг. Друг может подружится с другими друзьями. Дружба взаимная, если я дружу Васю с Петей, то и Петя дружит с Васей. Так у каждого друга, получается, что-то вроде списка друзей.  

    Задача сделать поиск друга напрямую и косвенно. Напрямую, я сделал, это легко и понятно, нужно просто ответить дружит ли Вася напрямую с Петей. А вот косвенно, это значит через кого-то. Тут я не много уже задумался. Может подкинете идеи или кто-то уже решал подобное.

    namespace Friendship
    {
       class Friend
       {  
           /* Имя */
           private String Name;

           /* Список друзей */
           private ArrayList Relations;

           /*
            *
            * Устанавливает начальное значение имени
            * и выделяет память под Relations.
            *
            * */
           public Friend(String name)
           {
               this.SetName(name);
               this.Relations = new ArrayList();
           }

           /*
            *
            * Метод создает взаимную связь между
            * текущим и указанным другом.
            *
            * */
           public void ConnectTo(Friend f)
           {
               this.Relations.Add(f);
               f.Relations.Add(this);
           }

           /*
            *
            * Метод разрывает связь между текущим и
            * указанным другом.
            *
            * */
           public void DisconnectWith(Friend f)
           {
               this.Relations.Remove(f);
               f.Relations.Remove(this);
           }

           /*
            *
            * Метод поиска друга на прямую. Отвечает на вопрос: "Знаком
            * ли текущий друг с указанным на прямую?"
            *
            * */
           public bool IsDirectConnectWith(Friend f)
           {
               return this.Relations.Contains(f);
           }

           /*
            *
            * Метод поиска косвенных связей.
            * Сообщает связан ли текущий друг с указанным,
            * любыми другими связями.
            *
            * */
           public bool IsAccrossConnectWith(Friend f)
           {
               // если связан на прямую, то дальше
               // искать нет смысла
               if (this.IsDirectConnectWith(f))
               {
                   return true;
               }
           }

           /*
            *  
            * Метод, который устанавливает имя.
            *
            * */
           public void SetName(String name)
           {
               this.Name = name;
           }

           /*
            *
            * Метод возвращает имя.
            *
            * */
           public String GetName()
           {
               return this.Name;
           }

       }
    }


    Подсветку сделал через java
  • krasun

    Сообщения: 1370 Репутация: N Группа: Джедаи

    Spritz 29 октября 2009 г. 6:54, спустя 19 часов 7 минут 6 секунд

    Может есть где литература?
  • phpdude

    Сообщения: 26624 Репутация: N Группа: в ухо

    Spritz 29 октября 2009 г. 6:56, спустя 1 минуту 45 секунд

    /*
    *
    * Метод, который устанавливает имя.
    *
    * */
    public void SetName(String name)
    {
    this.Name = name;
    }


    почитай про сеттеры и геттеры в .нет, ты написал в стиле пхп.
    Сапожник без сапог
  • krasun

    Сообщения: 1370 Репутация: N Группа: Джедаи

    Spritz 29 октября 2009 г. 6:58, спустя 2 минуты 30 секунд


    /*
    *
    * Метод, который устанавливает имя.
    *
    * */
    public void SetName(String name)
    {
    this.Name = name;
    }


    почитай про сеттеры и геттеры в .нет, ты написал в стиле пхп.


    phpdude, я знаю, что такое геттеры и сеттеры в .NET, сейчас мне просто удобно явно указывать.

    Мне бы с поиском что-то придумать, задача интересная.
    Спустя 56 сек.
    Я просто не знаю как такой тип поиска называется, это же не дерево, это какой-то граф выходит с кучей перемешанных связей.
  • Trej Gun

    Сообщения: 5299 Репутация: N Группа: в ухо

    Spritz 29 октября 2009 г. 9:03, спустя 2 часа 5 минут 21 секунду

    почему код не подкрашен? ктото с классами снрова мудрил?
    Спустя 95 сек.
    krasun, почитай про класс LinkedList он по идеи должен быть и в c# может немного иначе называется
  • phpdude

    Сообщения: 26624 Репутация: N Группа: в ухо

    Spritz 29 октября 2009 г. 9:06, спустя 2 минуты 19 секунд

    почему то мне кажется тут никакой арифметики, а тупой перебор … ))

    либо всех кто в куче знаком складывать в общую кучу и в ней потом уже искать :)
    Сапожник без сапог
  • krasun

    Сообщения: 1370 Репутация: N Группа: Джедаи

    Spritz 29 октября 2009 г. 9:13, спустя 7 минут 3 секунды

    Тоже думаю так сделать, пока что не могу придумать какой-то алгоритм
    Спустя 240 сек.
    CTAPbIu_MABP, а у меня разве связной список? У меня получается один из узлов может иметь множество ссылок на другие узлы
    Спустя 89 сек.
    но идею понял, поищу что нибудь в этом направлении, на крайний случай, все в кучу и перебор
  • Trej Gun

    Сообщения: 5299 Репутация: N Группа: в ухо

    Spritz 29 октября 2009 г. 9:23, спустя 10 минут 3 секунды

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

    Сообщения: 1370 Репутация: N Группа: Джедаи

    Spritz 29 октября 2009 г. 11:43, спустя 2 часа 20 минут 31 секунду

    CTAPbIu_MABP, мне без базы. Я именно хочу понять алгоритм. Я такое видел в соц. сетях: Вы дружите с Антоном через Петра, а Петр через Ивана. И так полный путь.
    Я рисовал сначал граф, но в их теории я не силен. Решение примерно прикинул. Ходить по этим узлам, запоминать какой прошел, и так далее… Еще посмотрю связанные списки, как ты и сказал, спасибо.
  • Mr.Pihto

    Сообщения: 1386 Репутация: N Группа: Адекваты

    Spritz 2 ноября 2009 г. 9:45, спустя 3 дня 23 часа 1 минуту

    Код: Java

    а код вроде C )
  • krasun

    Сообщения: 1370 Репутация: N Группа: Джедаи

    Spritz 2 ноября 2009 г. 9:53, спустя 7 минут 53 секунды


    Код: Java

    а код вроде C )

    не, не C, это C#. Просто C#, не подсвечивался.
  • Mr.Pihto

    Сообщения: 1386 Репутация: N Группа: Адекваты

    Spritz 2 ноября 2009 г. 10:47, спустя 54 минуты 20 секунд

    ну я имел ввиду С#.. хотя С# и Java близки
    Спустя 15 сек.
    по синтаксису
  • krasun

    Сообщения: 1370 Репутация: N Группа: Джедаи

    Spritz 5 ноября 2009 г. 11:00, спустя 3 дня 13 минут

    АХУЕТЬ, я решил это. Теперь, я смогу ответить на вопрос.



    Знаком ли Вася с Федором.  
    Спустя 25 сек.
    Единственное, что сейчас я нахожу не кратчайший путь правда
    Спустя 34 сек.
    Загвоздка была, в том что это не дерево и здесь могут быть циклические связи.
  • adw0rd

    Сообщения: 22905 Репутация: N Группа: в ухо

    Spritz 5 ноября 2009 г. 13:10, спустя 2 часа 9 минут 11 секунд

    Давай алгоритмы в студию)
    adw/0
  • krasun

    Сообщения: 1370 Репутация: N Группа: Джедаи

    Spritz 5 ноября 2009 г. 13:51, спустя 41 минуту 32 секунды

    Обязательно, только чуть позже, нужно код привести в порядок, доделать пару методов и описать ))

Пожалуйста, авторизуйтесь, чтобы написать комментарий!