Tosterer
@Tosterer
Новичок

Каков алгоритм решения задачи о жуках, которые не любят находиться близко друг от друга?

Здравствуйте. Прошу помочь с решением учебной задачи, т.к. не очень понимаю суть задачи и поэтому не знаю с чего начать.
Задача следующая:
Жуки не любят находиться рядом друг с другом и каждый прячется под отдельным камнем и старается выбирать камни, максимально удаленные от соседей. Так же жуки любят находится максимально далеко от края. Как только жук сел за камень, он более не перемещается. Всего в линии лежат X камней. И туда последовательно бежит прятаться Y жуков. Найти сколько свободных камней будет слева и справа от последнего жука. X может быть до 4 млрд.

Примеры:
X=8, Y=1 – ответ 3,4
X=8, Y=2 – ответ 1,2
X=8, Y=3 – ответ 1,1
  • Вопрос задан
  • 193 просмотра
Решения вопроса 1
lastuniverse
@lastuniverse
Всегда вокруг да около IT тем
Тут все просто, каждый очередной жук будет искать точку равноудаленную от края и других жуков.
тоесть первый засядет ровно по середине, два последующих засядут с двух сторон от первого, посередине между первым и краями и так далее.
По сути это задача на нахождение значений фрактала.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Вообще, в таком виде задача может не иметь однозначного решения.
Первый же пример X=8, Y=1 даёт два решения - (3,4) и (4,3).
Ответ написан
@Beshere
Инженер-программист
Тут конечно есть аж три подхода:

1. Смоделировать ситуацию рассаживания жуков, хотя замечание о 4 млрд намекает, что от нас ждут не этого. А если завтра их будет 4 триллиона?

2. Можно заметить, что расстояние например левого жука (при рассадке слева направо) от края отрезка длиной X в зависимости от числа жуков представляет собой ряд: L(1) = X/2, L(2) = X/4, L(3) = X/4, L(4) = X/8, L(5) = X/8, L(6) = X/8, L(7) = X/8... и т.д. Осталось сообразить, что же это за формула тут прячется. Степень двойки? Треугольник Паскаля? Теплеет. Ах зачем программисту высшее образование? Не, не нужно!

3. Про фракталы верно, это в терминах вычислений значит рекурсия. Алгоритм может выйти изящным, но скопытится от полчища жуков быстрее, чем вариант 1.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы