matyushkin 29 января 2020

Задача о шести шахматных конях

Сегодня нам предстоит алгоритмическая задача с позиционным обменом двух типов объектов. Наглядно такое движение можно представить через перемещение шахматных коней.

Условие задачи о шести шахматных конях

На шахматной доске 3 × 4 находится шесть фигур: три белых коня в нижнем ряду, и три чёрных коня в верхнем. Предложите алгоритм, при котором чёрные и белые фигуры обменяются положениями, как показано на рисунке, за минимальное количество ходов. Один ход соответствует одному перемещению фигуры в соответствии с шахматными правилами.

Условия задачи: перейти от левого вида шахматной доски к правому

Для описания алгоритма используйте нумерацию полей как на рисунке ниже.

Нумерация полей

Это задача не из лёгких. Идеи и ответы можно обсудить в комментариях. Первого читателя, указавшего в комментариях под постом правильное решение, мы выделим при публикации следующей задачи (см. пример ниже).

Эта задача – девятый эпизод нашего сериала головоломок. После описания задачи идёт ответ на предыдущую головоломку о вирусе в колонии бактерий. Ответ и новая задача будут опубликованы в 14:00 в субботу.

***

Решение задачи о вирусе в колонии бактерий

Ответ: нет, колония обречена.

Решение. Легко проверить, что количество бактерий и вирусов будет меняться со временем по следующему закону:

Время (минуты) Кол-во вирусов Кол-во бактерий
0 1 N
1 2 2(N-1)
2 22 2(2N-2-2) = 22(N-2)
3 23 2(4N-8-4) = 23(N-3)
4 24 24(N-4)
... ... ...
t 2t 2t(N-t)

Отсюда ясно, что при t = N количество бактерий обратится в ноль.

Как ответили читатели Библиотеки программиста? Первым правильный ответ на сайте, что колония бактерий не выживет, дал muradoz. Само решение тоже верное, но шло от конечной точки, и поэтому получилось немного более запутанным:

К моменту T бактерий было бы N*2^T без вирусов. Сколько из этого убили вирусы? За первую минуту была убита 1 бактерия, которая превратилась бы в 2^T. За вторую минуту 2 вируса убили 2 бактерии, которые бы стали к моменту времени Т числом 2^(T-1). То есть вирусы убили от потенциального числа к моменту Т сумму по к от 1 до T следующей штуки: число вирусов в момент к (то есть 2^k) на 2^(T-k). Эта сумма T*2^T. Колония проживет N минут.

РУБРИКИ В СТАТЬЕ

МЕРОПРИЯТИЯ

Комментарии 8

ВАКАНСИИ

iOS developer
от 140000 RUB до 200000 RUB
Front-end Developer
Казань, по итогам собеседования

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ

BUG