Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: Головоломка
СообщениеДобавлено: 05 окт 2015, 01:22 
Не в сети
Начинающий
Зарегистрирован:
05 окт 2015, 01:18
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Описание игры-головоломки: дано некоторое поле в клеточку с фишками (N>1). Можно двигать фишки только перескакивая через одну другую (через пустые клетки прыгать нельзя). При этом фишка, через которую перескочили, удаляется. Игра считается пройденной, когда на поле останется 1 фишка.

Мой вопрос:
Пусть поле 16х16. Количество фишек на поле 1<N<255.
Пусть какая-то расстановка фишек считается более удачной, если сейчас можно сделать меньшее количество ходов. Например, если у нас на поле где-то в центре стоят рядом 2 фишки, то возможно 2 хода. Если всё поле заставлено фишками, кроме одной угловой клетки, то возможно тоже 2 хода. Эти две расстановки одинаково "удачные". Если всё поле заставлено фишками, кроме какой-то клетки в центре, то возможно 4 хода. Эта расстановка менее "удачная", чем предыдущие две.

Найти максимальное количество ходов в самой(ых) неудачных расстановках. Сами неудачные расстановки не важны, нужно только число возможных ходов в такой ситуации.

Вот, что пока есть:
Каждый ход может начинаться в одной из 256 клеток и может быть направлен в одном из четырёх направлений. Это даёт нам первое ограничение 256х4=1024 хода.
Возьмём первую и вторую строку. В них ход "вверх" невозможен, т.к. там граница поля. Это даёт ограничение (256-2х16)х4=896 ходов.
Для того, чтобы ход было возможно сделать, где-то должна быть пустая клетка, из которой ход сделать нельзя. Эта клетка может располагаться:
1) в центральном квадрате 12х12
2) в угловых квадратах 2х2
3) в остальных местах
Первый вариант позволяет уменьшить ограничение на ответ ещё на 4, второй на 2, третий на 3. Нам нужно максимальное число ходов, значит 896-2=894.

То есть, пока у меня выходит 1<ОТВЕТ<894. Это явно слишком много.

Даже если у вас нет окончательного ответа, предлагаю дать своё ограничение сверху на ответ, если оно будет обосновано. Это требуется для выделения памяти программе, которая будет пытаться решить головоломку.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Ошибки в первом посте
СообщениеДобавлено: 05 окт 2015, 11:28 
Не в сети
Начинающий
Зарегистрирован:
05 окт 2015, 01:18
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Ошибки в первом посте:
Количество фишек на поле 2<=N<=255.
То есть, пока у меня выходит 0<=ОТВЕТ<=894.

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Головоломка

в форуме Алгебра

Ellya

2

170

27 ноя 2014, 12:28

Задачка -головоломка

в форуме Задачи со школьных и студенческих олимпиад

Natalia Sherbakova

6

894

23 ноя 2012, 13:33

Задача головоломка

в форуме Специальные разделы

Pegas

2

217

12 апр 2016, 18:38

Среднеквадратичное значение. Головоломка

в форуме Интересные задачи участников форума MHP

Custom

3

247

14 авг 2014, 13:53

Задача-головоломка, исключительно для вундеркиндов

в форуме Алгебра

ALEXIN

1

353

09 май 2015, 15:32

Маленькая головоломка для любителей логарифмов

в форуме Алгебра

Anatole

5

134

09 июл 2018, 23:22


Часовой пояс: UTC + 4 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved