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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

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




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: Головоломка
СообщениеДобавлено: 05 окт 2015, 00:22 
Не в сети
Начинающий
Зарегистрирован:
05 окт 2015, 00: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, 10:28 
Не в сети
Начинающий
Зарегистрирован:
05 окт 2015, 00:18
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

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

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

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

MurChik

10

371

08 апр 2023, 11:05

Головоломка

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

Ellya

2

322

27 ноя 2014, 11:28

Головоломка

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

Avgust

21

694

25 авг 2021, 18:40

Головоломка

в форуме Размышления по поводу и без

Nataly-Mak

4

329

30 окт 2019, 09:47

Очередная головоломка

в форуме Геометрия

MurChik

23

343

13 мар 2023, 21:33

Головоломка по геометрии

в форуме Геометрия

dempid

2

269

24 мар 2021, 13:00

Головоломка для школьников

в форуме Геометрия

mugga

9

371

13 ноя 2020, 10:50

Занимательная головоломка

в форуме Объявления участников Форума

Elia

8

309

10 сен 2019, 12:15

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

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

Pegas

2

448

12 апр 2016, 17:38

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

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

Custom

3

419

14 авг 2014, 12:53


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



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

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


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

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

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

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