Печать страницы - Поиск, почти как по дереву =((

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 29 Октябрь, 2009, 09:47:11

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

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

Java

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 от 29 Октябрь, 2009, 04:54:17

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

Название: Поиск, почти как по дереву =((
Отправлено: phpdude от 29 Октябрь, 2009, 04:56:02

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

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

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 29 Октябрь, 2009, 04:58:32

phpdude

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

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

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

Мне бы с поиском что-то придумать, задача интересная.

Спустя 56 секунд добавил

Я просто не знаю как такой тип поиска называется, это же не дерево, это какой-то граф выходит с кучей перемешанных связей.

Название: Поиск, почти как по дереву =((
Отправлено: CTAPbIu_MABP от 29 Октябрь, 2009, 07:03:53

почему код не подкрашен? ктото с классами снрова мудрил?

Спустя 1 минуту 35 секунд добавил

krasun, почитай про класс LinkedList он по идеи должен быть и в c# может немного иначе называется

Название: Поиск, почти как по дереву =((
Отправлено: phpdude от 29 Октябрь, 2009, 07:06:12

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

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

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 29 Октябрь, 2009, 07:13:15

Тоже думаю так сделать, пока что не могу придумать какой-то алгоритм

Спустя 4 минуты добавил

CTAPbIu_MABP, а у меня разве связной список? У меня получается один из узлов может иметь множество ссылок на другие узлы

Спустя 1 минуту 29 секунд добавил

но идею понял, поищу что нибудь в этом направлении, на крайний случай, все в кучу и перебор

Название: Поиск, почти как по дереву =((
Отправлено: CTAPbIu_MABP от 29 Октябрь, 2009, 07:23:18

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

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 29 Октябрь, 2009, 09:43:49

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

Название: Поиск, почти как по дереву =((
Отправлено: Mr.Pihto от 02 Ноябрь, 2009, 08:45:28

Код: Java

а код вроде C )

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 02 Ноябрь, 2009, 08:53:21

Mr.Pihto

Код: Java
а код вроде C )

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

Название: Поиск, почти как по дереву =((
Отправлено: Mr.Pihto от 02 Ноябрь, 2009, 09:47:41

ну я имел ввиду С#.. хотя С# и Java близки

Спустя 15 секунд добавил

по синтаксису

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 05 Ноябрь, 2009, 10:00:59

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

Знаком ли Вася с Федором.

Спустя 25 секунд добавил

Единственное, что сейчас я нахожу не кратчайший путь правда

Спустя 34 секунды добавил

Загвоздка была, в том что это не дерево и здесь могут быть циклические связи.

Название: Поиск, почти как по дереву =((
Отправлено: adw0rd от 06 Ноябрь, 2009, 12:10:10

Давай алгоритмы в студию)

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 06 Ноябрь, 2009, 12:51:42

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

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 06 Ноябрь, 2009, 07:26:54

Поиск сделал, но до сих пор не могу решить одну проблему. Из-за которой я могу запустить поиск только один раз.

В общем, вот пример связей:

Надо сказать знаком ли A. с F. и если знаком, то вывести путь.

Вот вывод программы

Сам код http://rapidshare.com/files/303023515/Friendship.rar.html

P.S: Но есть одна проблема, поиск можно запустить один раз, нужно как-то очищать журнал поиска, но это так, пока еще решаю

Спустя 40 секунд добавил

http://dkrasun.wordpress.com/2009/11/05/%D0%B4%D0%B7-c-%D0%BF%D0%BE%D1%80%D0%BE%D1%87%D0%BD%D1%8B%D0%B5-%D1%81%D0%B2%D1%8F%D0%B7%D0%B8-%D1%87%D0%B0%D1%81%D1%82%D1%8C-2/ здесь пытаюсь описать

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 06 Ноябрь, 2009, 07:59:56

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

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 06 Ноябрь, 2009, 08:33:03

Может кто встречал хорошие статьи, фиг с ним уже, пусть даже книги, где хорошо описываются рекурсии и куча всяких алгоритмов основанных на рекурсии

Название: Поиск, почти как по дереву =((
Отправлено: mario от 06 Ноябрь, 2009, 08:42:41

Дональд Э. Кнут. Искусство программирования. Том 4. Комбинаторные алгоритмы.
книга дорогая (а особенно дорогая если брать все тома) но(!) они того стоят, у знакомого были... приходил в гости листал ) очень понравилось, себе все ни как не куплю, по одному тому я не люблю брать, а что бы все сразу взять не получалось то денег нет, то всех томов нет )))))

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 06 Ноябрь, 2009, 08:45:43

про Кнут, я тоже знаю, и имею точно такое же мнение "либо денег нет, либо томов" =(((

хорошо пока есть что сейчас читать, кстати хорошая книга http://www.ozon.ru/context/detail/id/2427699/

Название: Поиск, почти как по дереву =((
Отправлено: mario от 06 Ноябрь, 2009, 08:48:28

krasun

про Кнут, я тоже знаю, и имею точно такое же мнение "либо денег нет, либо томов" =(((

хорошо пока есть что сейчас читать, кстати хорошая книга http://www.ozon.ru/context/detail/id/2427699/

смотрю тоже любитель почитать? )

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 06 Ноябрь, 2009, 08:55:10

Последнее время все больше и больше.

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

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

Спустя 16 секунд добавил

А ты как?

Название: Поиск, почти как по дереву =((
Отправлено: adw0rd от 06 Ноябрь, 2009, 09:46:05

Я тоже сразу несколько книг читаю, по другому не могу :/

Название: Поиск, почти как по дереву =((
Отправлено: phpdude от 06 Ноябрь, 2009, 10:10:11

а я с ребенком играю, не до книг))

Название: Поиск, почти как по дереву =((
Отправлено: mario от 06 Ноябрь, 2009, 10:20:15

krasun

Последнее время все больше и больше.

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

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

Спустя 16 секунд добавил
А ты как?

раньше примерно так и читал, только вместо худ.литеры была литра по какому нибудь хобби(может быть и не литра)
а если программирую, то читаю в основном теорию программирования, если не программирую а чем нибудь другим занимаюсь читаю теорию по тому чес занимаюсь... если не читаю у меня начинается паранойя, что я балбес и нихуя не шарю )))) хотя и так нехуя не шарю, скажем так, предела же совершенства нет, не так ли? ;)

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 06 Ноябрь, 2009, 10:32:48

Да, предела совершенства нет. Но когда чувствуешь что переходишь на новый уровень, ощущаешь счастье и радуешься, что нам еще надо кроме как любви к своему делу и быть профи в этом деле.

Название: Поиск, почти как по дереву =((
Отправлено: phpdude от 06 Ноябрь, 2009, 10:35:06

krasun

Да, предела совершенства нет. Но когда чувствуешь что переходишь на новый уровень, ощущаешь счастье и радуешься, что нам еще надо кроме как любви к своему делу и быть профи в этом деле.

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

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 06 Ноябрь, 2009, 10:41:38

phpdude

... госво, котрое дает развиваться в человеке только алкоголизму ...

блин я ушел в себя на пару минут

Спустя 26 секунд добавил

но ты же не сдашься?

Название: Поиск, почти как по дереву =((
Отправлено: adw0rd от 06 Ноябрь, 2009, 11:20:06

phpdude, ебаный рот, ты снова стал ныть, когда же ты блять возмужаешь?

Название: Поиск, почти как по дереву =((
Отправлено: md5 от 06 Ноябрь, 2009, 11:20:47

phpdude, да ты тёлка! :)))

Название: Поиск, почти как по дереву =((
Отправлено: phpdude от 06 Ноябрь, 2009, 12:09:14

adw0rd

phpdude, ебаный рот, ты снова стал ныть, когда же ты блять возмужаешь?

хуй знает :) ладн, удаляюсь :)

md5

phpdude, да ты тёлка! :)))

ага, возьми меня ))

Название: Поиск, почти как по дереву =((
Отправлено: welder от 06 Ноябрь, 2009, 02:17:21

бля а я завидую алкашам им по хуй на всё и жрать не хотят и работать не нана один хуй выпить есть чо, а про то что по синьке везёт я ваще молчу :)

Название: Поиск, почти как по дереву =((
Отправлено: phpdude от 06 Ноябрь, 2009, 02:44:22

welder

бля а я завидую алкашам им по хуй на всё и жрать не хотят и работать не нана один хуй выпить есть чо, а про то что по синьке везёт я ваще молчу :)

а кому щас легко? "да им несложно" ))

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 06 Ноябрь, 2009, 04:29:34

phpdude

welder

бля а я завидую алкашам им по хуй на всё и жрать не хотят и работать не нана один хуй выпить есть чо, а про то что по синьке везёт я ваще молчу :)

а кому щас легко? "да им несложно" ))

Им хуже всех.

Название: Поиск, почти как по дереву =((
Отправлено: mario от 07 Ноябрь, 2009, 12:05:20

krasun

Да, предела совершенства нет. Но когда чувствуешь что переходишь на новый уровень, ощущаешь счастье и радуешься, что нам еще надо кроме как любви к своему делу и быть профи в этом деле.

за это +1 ) без него я даже на кнопку запуска не нажму )

phpdude

krasun

Да, предела совершенства нет. Но когда чувствуешь что переходишь на новый уровень, ощущаешь счастье и радуешься, что нам еще надо кроме как любви к своему делу и быть профи в этом деле.

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

эй нехуй раскисать, хуй всему голова!, а в переезде есть тоже плюсы ;)
это было к тому что нехуй минусы искать, ищи везде плюсы! )

Название: Поиск, почти как по дереву =((
Отправлено: adw0rd от 06 Ноябрь, 2009, 11:45:54

эй, нехуй раскисать, хуй всему голова!

Это было обращение?

Название: Поиск, почти как по дереву =((
Отправлено: mario от 07 Ноябрь, 2009, 12:04:44

adw0rd

эй, нехуй раскисать, хуй всему голова!
Это было обращение?

:DDDDDD
блин, я просто очень люблю запятые ;)
я сам прочитал правильно, под стол ушел )

Название: Поиск, почти как по дереву =((
Отправлено: grigoriyi от 17 Январь, 2010, 10:42:43

welder

бля а я завидую алкашам им по хуй на всё и жрать не хотят и работать не нана один хуй выпить есть чо, а про то что по синьке везёт я ваще молчу :)

я вот люблю залитым програмить и что?

Название: Поиск, почти как по дереву =((
Отправлено: CTAPbIu_MABP от 17 Январь, 2010, 10:46:57

grigoriyi, покажи код :D

Название: Поиск, почти как по дереву =((
Отправлено: krasun от 18 Январь, 2010, 12:53:13

CTAPbIu_MABP

grigoriyi, покажи код :D

да, да, интересно

Название: Поиск, почти как по дереву =((
Отправлено: Mr.Pihto от 18 Январь, 2010, 12:58:22

я думаю что он и не залитым ниче не пишет

Название: Поиск, почти как по дереву =((
Отправлено: artoodetoo от 18 Январь, 2010, 08:37:34

как вам раздел "Синяя Пыха"? :)

Название: Поиск, почти как по дереву =((
Отправлено: AlexB от 18 Январь, 2010, 12:31:15

krasun

CTAPbIu_MABP

grigoriyi, покажи код :D

да, да, интересно

Да чего тут интересного, открывай почти любой топик на пыхе и любуйся ...

Название: Поиск, почти как по дереву =((
Отправлено: CTAPbIu_MABP от 18 Январь, 2010, 12:33:54

AlexB, оптимист бля

Название: Поиск, почти как по дереву =((
Отправлено: Nyaah_old от 09 Февраль, 2010, 08:26:27

Такая структура данных называется граф. Советую по алгоритмам почитать ослов (Карман сотоварищи "Алгоритмы - посроение и анализ")

Ключевые слова для поиска: алгоритмы на графах, поиск в ширину (это если искать друзей друзей) и поиск в глубину/поиск кратчайших путей (если ищешь, связаны как-нибуть пользователи через одного/двух/трёх/мильён друзей)

Название: Поиск, почти как по дереву =((
Отправлено: CTAPbIu_MABP от 09 Февраль, 2010, 10:08:06

Nyaah, анимешник со знанием матана.... интересно...

Название: Поиск, почти как по дереву =((
Отправлено: Sinkler от 09 Февраль, 2010, 11:18:23

математика... целых четыре за одни семестр... ммм... =)

Название: Поиск, почти как по дереву =((
Отправлено: Nyaah от 10 Февраль, 2010, 06:20:31

Матан то тут причём, этож чистая алгоритмика, причем не сильно сложная

зы зарегался не на то мыло и пароль докучи забыл, а вы говорите матан-матан =)

Название: Поиск, почти как по дереву =((
Отправлено: phpdude от 10 Февраль, 2010, 06:56:30

Naaayh, красавец.

Название: Поиск, почти как по дереву =((
Отправлено: AlexB от 10 Февраль, 2010, 04:03:52

Формально математический анализ — «часть математики, в котором математические объекты изучаются методом пределов (методом бесконечно малых)». Но, поскольку сферическое быдло в вакууме в душе не чает чем диффуры отличаются от теории графов, то матаном обзывается вообще вся высшая математика, а то и просто любые записи со «страшными» формулами. Поэтому далее по тексту под матаном имеется ввиду не одноименный раздел математики, а любое из нижеперечисленного ... http://lurkmore.ru/%D0%9C%D0%B0%D1%82%D0%B0%D0%BD

Название: Поиск, почти как по дереву =((
Отправлено: CTAPbIu_MABP от 10 Февраль, 2010, 04:06:56

AlexB, спасибо обосрал

Название: Поиск, почти как по дереву =((
Отправлено: phpdude от 10 Февраль, 2010, 04:19:52

AlexB, кстати ведь ты прав)

Название: Поиск, почти как по дереву =((
Отправлено: Sinkler от 10 Февраль, 2010, 11:35:29

а вы не знали?

PHP форум на ПЫХА.РУ

Языки программирования => C/C++ и C# => Тема начата: krasun от 29 Октябрь, 2009, 09:47:11