06:05 

придумал тут задачку..

Рукопожатия.

Работа такая работа. Много народу, с каждым надо поздороваться. Программист Андрей пришел в ужас, высчитав требуемое общее количество рукопожатий, чтобы все были довольны и начали уже кодить этот ваш софтвер. Поэтому он решил несколько оптимизировать процесс.
Итак, поздоровавшись, два человека берут на себя обязательство, что, поздоровавшись с кем-либо впоследствии, они будут здоровается и за себя, и за этого человека. То есть каждый человек здоровается и за себя, и за всех, с кем он фактически или через посредников здоровался до сих пор.
Два человека могут фактически пожать руки только один раз (через других можно здороваться сколько угодно).
Человек в один момент времени может здороваться только с одним человеком.
Какое наименьшее количество фактических рукопожатий среди всех людей можно сделать, с учетом того, что максимальное количество фактических рукопожатий некоторого человека минимально возможное для данного числа человек? Иными словами, если каждому человеку потребуется как можно меньше жать руки, насколько оптимизируется процесс таким способом?

PS
Задачка вроде нетривиальная, сходу ничего придумать не смог. Вряд ли тут есть формула, надо придумывать какой-нибудь алгоритм. Лишь бы не оказалась NP-полной -_- Тут ключевое условие в минимизации максимума пожатий человека, без этого условия ответ был бы что-нибудь типа 2*N-3 пожатий (N - количество народу), а может и того меньше. А еще у меня есть ощущение, что я что-то упускаю в формулировке задачи, да и задача какая-то оптимизационная, может существуют типовые методы оптимизации и не надо тут ничего программировать.. И да, это связанный неориентированный граф с последовательно пронумерованным набором ребер. Перебор - факториал от максимального количества ребер.
Здорово, что с формулировкой можно поиграться, задать время затрачиваемое на одно пожатие или зафиксировать максимальный минимум, выше которого заходить нельзя, но я пожалуй не буду на этом заморачиваться)

URL
   

brain dump

главная