Логические задачи и головоломки
23 Январь 2017, 00:21:07 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
Новости:
 
   Начало   Правила Помощь Поиск Войти Регистрация Чат  
Страниц: [1]   Вниз
  Печать  
Автор Тема: Добрый день. Помогите решить... Вечеринка.  (Прочитано 291 раз)
0 Пользователей и 1 Гость смотрят эту тему.
maska11
Новичок
*
Offline Offline

Сообщений: 27


Просмотр профиля
« : 30 Сентябрь 2016, 21:43:19 »

Деревня имеет форму квадрата со стороной 2 км. В ней n домов, в каждом живёт один человек. В 12.00   А. заскучал и решил устроить вечеринку в 19.00.  Сразу же начал обходить своих соседей с приглашением. Как только житель деревни узнавал о вечеринке, шёл приглашать остальных. Если все жители деревни ходят со скоростью 3 км/час решите, могли ли независимо от n и расположения домов,  распространить информацию так, чтобы все жители деревни собрались в 19.00 у А. дома на вечеринке.
Записан
Artem of 93
Ветеран
*****
Offline Offline

Сообщений: 836



Просмотр профиля
« Ответ #1 : 30 Сентябрь 2016, 23:04:35 »

Честно говоря, условия опять расплывчатые:

1) Что значит, что "А начал обходить соседей"? Кто его соседи? Дома справа и слева от него или вся деревня?
2) Что значит, что житель деревни "шёл приглашать остальных"? Тоже соседей или всю деревню?
3) Что значит, что деревня имеет форму квадрата? Жителям можно ходить только по сторонам квадрата или по диагоналям тоже?
Записан

Постоянный читатель "Смекалки" с 2013 года. Появляюсь в комментариях под этим же ником. Моя задача на сайте.
maska11
Новичок
*
Offline Offline

Сообщений: 27


Просмотр профиля
« Ответ #2 : 30 Сентябрь 2016, 23:28:46 »

Перевод практически дословный. Как я понимаю,  дома расположены по сторонам квадрата и внутри него произвольным образом, числом n. О направлении движения А вообще ничего не сказано, как и о том, сказал ли он только одному человеку или нескольким. О соседях сказано, что "как только человек получил информацию, шёл распространять её между остальными". Ходить можно как по сторонам, так и по диагонали.
Записан
Artem of 93
Ветеран
*****
Offline Offline

Сообщений: 836



Просмотр профиля
« Ответ #3 : 30 Сентябрь 2016, 23:47:32 »

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

Допустим, А пошёл к соседу справа, затем вернулся домой. Его сосед пошёл к своему соседу справа, после чего пошёл на вечеринку к А. И так далее. Либо они все вместе будут ходить по кругу. По сути, это ведь равносильно тому, что А сам будет обходить всю деревню. Периметр деревни равен 8 км, а так как скорость жителя равна 3 км/ч, понадобится 2 часа 40 минут, чтобы обойти всю деревню. Также возможен вариант, что А задаст цепную реакцию в обе стороны (сначала предупредит соседа справа, затем - соседа слева). Таким образом, к 19:00 вся деревня гарантированно соберётся на вечернику.

Правда, тогда сложно сказать, в чём смысл задачи.
Записан

Постоянный читатель "Смекалки" с 2013 года. Появляюсь в комментариях под этим же ником. Моя задача на сайте.
StrannikPiter
Ветеран
*****
Offline Offline

Сообщений: 887



Просмотр профиля
« Ответ #4 : 30 Сентябрь 2016, 23:57:22 »

Тут как раз условия нормальные. Дома располагаются произвольно (по периметру это слишком просто), от дома к дому можно идти по прямой, как я понимаю. Чем больше домов, тем больше народу нужно оповещать, зато и среднее расстояние между домами меньше. Кроме того, число "оповещальщиков" растет в геометрической прогрессии. Интуитивно понятно, что 7 часов должно хватить и скорее всего с большим запасом. Но как строго доказать, пока не придумал.
Записан
StrannikPiter
Ветеран
*****
Offline Offline

Сообщений: 887



Просмотр профиля
« Ответ #5 : 01 Октябрь 2016, 00:06:46 »

А по поводу, кого считать соседями, то оповестить по условию нужно всех, но рациональней идти в первую очередь к ближайшим, чтобы не ходить много туда-сюда. И разумеется каждого достаточно оповестить один раз, не обязательно лично, можно и через цепочку других.
То есть как бы предполагается, что А. должен сразу выработать общую стратегию, кто к кому идет и в каком порядке оповещает, и передавать эту стратегию по цепочке, чтобы минимизировать время.
Записан
Artem of 93
Ветеран
*****
Offline Offline

Сообщений: 836



Просмотр профиля
« Ответ #6 : 01 Октябрь 2016, 00:10:43 »

Тут как раз условия нормальные.

Не согласен, что они нормальные. Условия задачи должны быть прописаны однозначно, должны быть обозначены все нюансы.
Записан

Постоянный читатель "Смекалки" с 2013 года. Появляюсь в комментариях под этим же ником. Моя задача на сайте.
Головолом
Постоялец
***
Offline Offline

Сообщений: 140


Просмотр профиля Email
« Ответ #7 : 03 Октябрь 2016, 14:36:23 »

...решите, могли ли независимо от n и расположения домов,  распространить информацию так, чтобы все жители деревни собрались в 19.00 у А. дома на вечеринке.
Я решил, что могли  Отдых
Записан
StrannikPiter
Ветеран
*****
Offline Offline

Сообщений: 887



Просмотр профиля
« Ответ #8 : 03 Октябрь 2016, 17:34:28 »

Потребуется не больше 4 часов.
Можно предложить следующий алгоритм оповещения. А. выбирает дом, расположенный наиболее близко к одному из краев деревни (назовем его стартовый край) и идет туда. Теперь о вечеринке знают уже двое. Они делят деревню на две полосы, шириной в 1 км, которые узкой стороной начинаются на стартовом краю. Каждый выбирает неоповещенный дом на соей полосе, ближайший к стартовому краю. Каждый из них, дойдя до своего дома делит снова свою полосу на две, уже шириной 500 м.
Если идти всегда параллельно краям деревни (не срезать путь), то на то, чтобы прочесать всю деревню, от стартового края до финишного, А. потребуется максимум пройти 6 км, даже если он всегда будет выбирать из 2-х вариантов наиболее длинный.

6 км найдено так. Весь путь будет складываться из продольных и поперечных участков. Сумма всех продольных будет максимально равна 2 км от стартового края до финишного. Максимальная сумма поперечных участков будет представлять собой ряд вида
(1 + 1/2 + 1/4 + 1/8 + ... + 1/2m)*2 км. Этот ряд сходится при любых m, и его предельное значение будет равно 4 км.

Остается найти путь от дома А. до первого дома возле стартового края и от финишного края до дома А. Срезать тоже не будем, получим сумму продольных участков 2 км и 2 поперечных участка, каждый по 2 км. То есть еще 6 км.

Итого максимальный путь будет 12 км, на него потребуется 4 часа. Причем очевидно, что данный алгоритм не будет оптимальным. Во-первых можно срезать путь. Во-вторых можно делить на полосы не равной ширины (где плотность домов выше, там полоса уже). В-третьих наверняка выгодней не идти сразу на край, а зайти к ближайшему соседу, так как чем раньше увеличится число оповещальщиков, тем быстрее закончится весь процесс. Но это сложно решить в общем виде.
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  

Powered by SMF 1.1.13 | SMF © 2006-2009, Simple Machines LLC
Simple Audio Video Embedder
| Sitemap