Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Клуб программистов > Свободное общение
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 09.06.2011, 13:23   #1
Zealint
Пользователь
 
Регистрация: 08.02.2010
Сообщений: 51
По умолчанию 6 ферзей на тороидальной доске - конкурс

Модераторам: форум программистов указан в качестве информационного спонсора на странице конкурса.

Здравия желаю!

Предлагаю принять участие в 8-м любительском конкурсе по программированию для тех, кто любит выдумывать эффективные алгоритмы и оптимизировать код.

Задача про 6 ферзей уже предлагалась во втором конкурсе больше года назад. С тех пор появились некие новые факты, ради подтверждения которых затевается этот конкурс.

Итак, задача состоит в следующем: имеется шахматная доска размером n x n (n - целое неотрицательное). Доска свёрнута в тор, то есть левая граница соединяется с правой, а верхняя - с нижней. Сколькими способами можно расположить на этой доске 6 не бьющих друг друга ферзей?

Поскольку ответы до n=35 уже известны, конкурс начинается с n=36. Участник, который сообщит ответ для как можно большего значения n побеждает. Конкурс любительский, призов не будет.

Причины выбора на конкурс именно этой задачи написаны на странице конкурса.

Удачи!
Zealint вне форума Ответить с цитированием
Старый 21.06.2011, 12:48   #2
Zealint
Пользователь
 
Регистрация: 08.02.2010
Сообщений: 51
По умолчанию

Конкурс завершился досрочно, удалось вывести явную формулу для задачи. Гипотеза о виде рекуррентного соотношения оказалось не совсем точной. Порядок его равен 124, а не 142. Эта разница обусловлена ошибочным предположением о существовании множителя z^6+z^3+1 в знаменателе производящей функции.

Победителем конкурса объявляется Андрей Халявин, реализовавший некий алгоритм, работающий со сложностью O(n^5).

Более подробно о формуле можно прочитать на странице с итогами. Там же будет предложено скачать PDF вариант формулы, умещающейся на одном листе.
Zealint вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Какое наимньшее число ферзей можно расставить на доске так, чтобы они держали под бонм все свободные поля 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