2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Вроде бы простая алгоритмическая задача
Сообщение07.07.2014, 21:58 


05/03/12
31
БГУ РФКТ (бывш. РФЭ)
В социальной сети зарегистрировано $n$ человек. Каждый участник может подписываться на сообщения других участников, причем если человек $A$ подписан на $B$, то из этого не следует, что $B$ подписан на $A$. Известно, что среди зарегистрированных пользователей есть знаменитость - человек, на которого подписаны все $n-1$ других пользователей, но сам он не подписан ни на кого. При помощи одного запроса к серверу вы можете определить, подписан ли человек $A$ на сообщения человека $B$. Предложите алгоритм, позволяющий найти знаменитость за не более чем $n$ запросов к серверу.

Что такое почитать, чтобы решать такую и подобные задачи?

 Профиль  
                  
 
 Re: Вроде бы простая алгоритмическая задача
Сообщение07.07.2014, 22:22 
Заслуженный участник


04/05/09
4582
Для начала определите, какую информацию можно извлечь разных вариантов ответов на запрос при отсутствии другой информации.

 Профиль  
                  
 
 Re: Вроде бы простая алгоритмическая задача
Сообщение07.07.2014, 22:33 
Аватара пользователя


31/10/08
1244
MAnt
Задачка простая на внимательность и умение логически мыслить.

 Профиль  
                  
 
 Re: Вроде бы простая алгоритмическая задача
Сообщение07.07.2014, 22:46 


05/03/12
31
БГУ РФКТ (бывш. РФЭ)
venco
если $A$ подписан на $B$, то $A$ не знаменитость.
если $A$ не подписан на $B$, то $B$ не знаменитость.
Понятно, вычеркиваем одного человека. За $n$ запросов вычеркнем $n$ человек. Спасибо :oops:

А какие есть доступные книги по графам?

 Профиль  
                  
 
 Re: Вроде бы простая алгоритмическая задача
Сообщение08.07.2014, 16:13 


26/06/14
83
Доступное - это что-то вроде "Введения в дискретную математику".

 Профиль  
                  
 
 Re: Вроде бы простая алгоритмическая задача
Сообщение08.07.2014, 19:16 
Аватара пользователя


31/10/08
1244
MAnt
Вы решили неправильно. Ещё раз внимательно посмотрите на условие задачи. И посмотрите на то что вы написали. Каким условием вы не воспользовались из условия?

Что касается графов то "Программирование в алгоритмах" Автор: С. Окулов

 Профиль  
                  
 
 Re: Вроде бы простая алгоритмическая задача
Сообщение08.07.2014, 19:38 
Заслуженный участник


04/05/09
4582
А мне кажется, что решение правильное.

 Профиль  
                  
 
 Re: Вроде бы простая алгоритмическая задача
Сообщение08.07.2014, 19:40 
Аватара пользователя


31/10/08
1244
venco
Да точно. Неправильно прочитал. Бывает.

 Профиль  
                  
 
 Re: Вроде бы простая алгоритмическая задача
Сообщение16.01.2015, 05:09 


30/08/10
158
Можно ещё Райгородского почитать, хотя там больше комбинаторики. Книга называется "Комбинаторика и теория вероятности", но таких у него может быть больше одной. Та, про которую я говорю, тонкая (страниц 100), и в ней графам отведено примерно 20 страниц.

 Профиль  
                  
 
 Re: Вроде бы простая алгоритмическая задача
Сообщение16.01.2015, 19:52 
Заслуженный участник


27/04/09
28128

(Оффтоп)

MAnt в сообщении #885097 писал(а):
При помощи одного запроса к серверу вы можете определить, подписан ли человек $A$ на сообщения человека $B$.
Главное, чтобы в реальной системе такого не было — и серверу обычно проще (имею в виду, меньше оверхеда) выдать, например, всех, на кого подписался $A$, а не только одну проверку, и передаваться маленькие повторные запросы-ответы, наверно, немного дольше будут, ну и в самом клиенте тоже может быть чуть проще.

К задаче это, конечно, никаким боком — хотя у неё могла бы быть и другая формулировка, не вызывающая такие ассоциации. :lol:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group