Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 09.06.2011, 14:14
Новичок

Отправить личное сообщение для Zealint Посмотреть профиль Найти все сообщения от Zealint
 
Регистрация: 15.04.2010
Сообщений: 12

Конкурс для программистов - 6 ферзей на торе
Предлагаю принять участие в 8-м любительском конкурсе по программированию. Задача состоит в следующем: имеется шахматная доска размером n x n, свёрнутая в тор. Сколькими способами можно расположить на ней 6 не бьющих друг друга ферзей?

Задача выбрана не случайно, она представляется очень интересной в связи с тем, что существует гипотеза о виде рекуррентного соотношения относительно n, порядок которого равен 142. Чтобы проверить это соотношение на правильность нужно уметь считать ответ на досках такого размера. Подробнее о задаче на странице конкурса.
  #2  
Старый 21.06.2011, 13:48
Новичок

Отправить личное сообщение для Zealint Посмотреть профиль Найти все сообщения от Zealint
 
Регистрация: 15.04.2010
Сообщений: 12

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

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

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


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

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Конкурс для программистов - максимальный поток, баян и блуждания на прямой Zealint Новости 1 14.03.2011 21:00
Конкурс для программистов - 3^n, димеры и статистика циклов Zealint Новости 1 09.12.2010 09:06
Конкурс для программистов - предгамильтоновы циклы Zealint Новости 5 31.10.2010 17:48
Конкурс для программистов - 6 ферзей Zealint Новости 1 10.05.2010 20:29
Головоломка про ферзей гость Задачи 5 09.04.2008 02:51