На шахматной доске N*N (N<30)
Из какой-нибудь клетки сделать K<N*N ходов, ни разу не наступив туда, где уже были и вернуться в начальную ( в неё можно наступить :-) )
Если будет решение - будут баллы, а может и 1000...
Просто не хочется их ухать разом...
Примечание:
Нужно компьютерное решение,
желательно за полином n^(2K).
Т.е. за время K перемножения матриц смежности.
Такова сложность искомого алгоритма....
Примечание:
nwn, Спасибо, но перебор тут неуместен.... Слишком долго.
Примечание:
nwn, понимаете, то что Вы предлагаете - это обход доски всей!
Мне же надо было для заданного n и k найти простой цикл длины k.
Т.е. обойти конём K клеток, так чтобы не повторялись...
n=3 k=4
Простого цикла длины 4 на доске 3x3 нет
n=3 k=8
6 1 4
3 0 7
8 5 2
n=4 k=5
Простого цикла длины 5 на доске 5x5 нет
n=4 k=4
0 0 0 2
0 3 0 0
0 0 1 0
4 0 0 0
n=5 k=4
0 0 0 2 0
0 0 0 0 0
0 0 1 0 3
0 0 0 0 0
0 0 0 4 0
В общем случае задача NP полная...
Но существует алгоритм полиномиальный по K
Вопрос потерял свою актуальность, т.к. зачёта уже нет...
RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.
Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.
Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.