|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
09.06.2011, 13:23 | #1 |
Пользователь
Регистрация: 08.02.2010
Сообщений: 51
|
6 ферзей на тороидальной доске - конкурс
Модераторам: форум программистов указан в качестве информационного спонсора на странице конкурса.
Здравия желаю! Предлагаю принять участие в 8-м любительском конкурсе по программированию для тех, кто любит выдумывать эффективные алгоритмы и оптимизировать код. Задача про 6 ферзей уже предлагалась во втором конкурсе больше года назад. С тех пор появились некие новые факты, ради подтверждения которых затевается этот конкурс. Итак, задача состоит в следующем: имеется шахматная доска размером n x n (n - целое неотрицательное). Доска свёрнута в тор, то есть левая граница соединяется с правой, а верхняя - с нижней. Сколькими способами можно расположить на этой доске 6 не бьющих друг друга ферзей? Поскольку ответы до n=35 уже известны, конкурс начинается с n=36. Участник, который сообщит ответ для как можно большего значения n побеждает. Конкурс любительский, призов не будет. Причины выбора на конкурс именно этой задачи написаны на странице конкурса. Удачи! |
21.06.2011, 12:48 | #2 |
Пользователь
Регистрация: 08.02.2010
Сообщений: 51
|
Конкурс завершился досрочно, удалось вывести явную формулу для задачи. Гипотеза о виде рекуррентного соотношения оказалось не совсем точной. Порядок его равен 124, а не 142. Эта разница обусловлена ошибочным предположением о существовании множителя z^6+z^3+1 в знаменателе производящей функции.
Победителем конкурса объявляется Андрей Халявин, реализовавший некий алгоритм, работающий со сложностью O(n^5). Более подробно о формуле можно прочитать на странице с итогами. Там же будет предложено скачать PDF вариант формулы, умещающейся на одном листе. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Какое наимньшее число ферзей можно расставить на доске так, чтобы они держали под бонм все свободные поля | alykaa | Помощь студентам | 4 | 01.12.2010 18:48 |
Си/Си++ Слоны на шахматной доске | Маришка_Курносова | Помощь студентам | 1 | 12.09.2010 01:02 |
Конкурс для программистов - 6 ферзей | Zealint | Свободное общение | 13 | 11.05.2010 11:12 |
монетки на шахматной доске! | grimm_jow | Общие вопросы C/C++ | 2 | 31.01.2010 10:27 |
конкурс программистов ! (первый конкурс) | Alar | Свободное общение | 129 | 18.03.2007 00:50 |