1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

Кто может сделать быстрее задачу о "Путешествии Коня"?

Тема в разделе "WASM.A&O", создана пользователем cpp_and_wasm, 21 авг 2006.

  1. cpp_and_wasm

    cpp_and_wasm Владимир

    Публикаций:
    0
    Регистрация:
    27 июл 2006
    Сообщения:
    128
    Задача похожа на ту, что про 8 ферзей.
    Условия: доска 8*8, начальное положение коня безразлично, конь не должен дважды попадать на одну и ту же ячейку доски.
    Всего ходов у вас должно получится 64.
     
  2. censored

    censored New Member

    Публикаций:
    0
    Регистрация:
    5 июл 2005
    Сообщения:
    1.615
    Адрес:
    деревня "Анонимные Прокси"
    быстрее чего? (кого)
     
  3. spa

    spa Active Member

    Публикаций:
    0
    Регистрация:
    9 мар 2005
    Сообщения:
    2.240
    censored
    хороший вопрос
     
  4. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.535
    censored
    Наверное быстрее всех?
     
  5. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Хорошо бы сначала ферзей до ума довести, а потом уже за следующую задачу браться.
     
  6. Quantum

    Quantum Паладин дзена

    Публикаций:
    0
    Регистрация:
    6 янв 2003
    Сообщения:
    3.143
    Адрес:
    Ukraine
    Это классика. Врядли алгоритм можно как-то улучшить.
     
  7. cpp_and_wasm

    cpp_and_wasm Владимир

    Публикаций:
    0
    Регистрация:
    27 июл 2006
    Сообщения:
    128
    Я ещё забыл спросить: у кого-нибудь есть готовая программа, выполняющая задачу о Путешествии коня? У меня есть готовая программа, но она написана на С++, хотя хотелось бы транслировать её в МАСМ (что я сейчас и делаю) для увеличения производительности на моём P3 710 MHz. Я тестил ту, что на С++ - вроде работает правильно. Сам алгоритм не оптимизирован, но 500 000 ходов/сек делает при релиз-компиляции на M!cr0$0ft Visual C++ 6.0 с указанием оптимизации на скорость
     
  8. cpp_and_wasm

    cpp_and_wasm Владимир

    Публикаций:
    0
    Регистрация:
    27 июл 2006
    Сообщения:
    128
    Я бы добавил прогу, но не знаю как её постить в форуме!!! Если знаете - подскажите как.
     
  9. cpp_and_wasm

    cpp_and_wasm Владимир

    Публикаций:
    0
    Регистрация:
    27 июл 2006
    Сообщения:
    128
    Попробуйте сделать алгоритм быстрее того, что у меня. Я ещё доработаю программу и потом выложу её. Дня 2 уйдёт на это...
     
  10. cpp_and_wasm

    cpp_and_wasm Владимир

    Публикаций:
    0
    Регистрация:
    27 июл 2006
    Сообщения:
    128
    Я алгоритм сам придумывал. А есть классический алгоритм этой головоломки и если есть, то где найти его?
     
  11. Quantum

    Quantum Паладин дзена

    Публикаций:
    0
    Регистрация:
    6 янв 2003
    Сообщения:
    3.143
    Адрес:
    Ukraine
    cpp_and_wasm
    Помню, на олимпиаде как раз попалась эта задача. Потом нашёл в сети кучу ресурсов с готовыми решениями. Совсем недавно опять наткнулся на эту самую головоломку, но уже в какой-то книге.

    Погуглить.
     
  12. cpp_and_wasm

    cpp_and_wasm Владимир

    Публикаций:
    0
    Регистрация:
    27 июл 2006
    Сообщения:
    128
    ДЕРЖИТЕ ПРОЕКТ!!! ЗАЦЕНИТЕ, НО СИЛЬНО НЕ РУГАЙТЕ!!! У меня компиляция прошла нормально. Жаль вот, что не на ассемблере писал :dntknw: , но скоро будет! ;)
     
  13. Arhara

    Arhara New Member

    Публикаций:
    0
    Регистрация:
    27 апр 2006
    Сообщения:
    10
    Адрес:
    Russia
    "BishopTravel.zip" - задача точно про коня ? :-)
     
  14. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    1.872
    У меня на доске 8х8 "ходит" со скоростью ~50 млн. ходов/сек и останавливаться и не думает :)
     
  15. cpp_and_wasm

    cpp_and_wasm Владимир

    Публикаций:
    0
    Регистрация:
    27 июл 2006
    Сообщения:
    128
    НУ, извините, если неправильно обозвал... :))))))
     
  16. cpp_and_wasm

    cpp_and_wasm Владимир

    Публикаций:
    0
    Регистрация:
    27 июл 2006
    Сообщения:
    128
    хе-хе!!! Если я правильно подсчитал, то на доске 8*8 может быть 64! комбинаций, т.е. 1,2688693218588416410343338933516e+89 ходов!!! :dntknw:
     
  17. Arhara

    Arhara New Member

    Публикаций:
    0
    Регистрация:
    27 апр 2006
    Сообщения:
    10
    Адрес:
    Russia
    Если нужно просто обойти всю доску как можно быстрее, то есть одна эвристика. При каждом ходе выбирать поле с которого меньше всего возможностей сходить на ещё неиспользованное поле. Когда-то давно воевал с этой задачей. Конь упорно не хотел идти в угол (это был единственный вариант) и переберал массу лишних вариантов.

    ====

    В зависимости от поля конь имеет возможность переместиться на следующее количество полей

    2 возможности - 4 поля
    3 - 8
    4 - 20
    6 - 16
    8 - 16

    Учитывая что уже конь использовал одну возможность как вход в текущее поле, то имеем.

    1^4+2^8+3^20+5^16+8^16 < 8^17 ~ 2*10^15

    Так как в реальности многие возможности уже будут невозможны, реальное число вариантов гораздо меньше.
     
  18. Mescalito

    Mescalito New Member

    Публикаций:
    0
    Регистрация:
    31 мар 2005
    Сообщения:
    78
    Адрес:
    Харьков
    Когда-то в школе мы от нефиг делать на уроках играли в игру: кто больше сделает ходов конём по доске. Играли, пока не обнаружилось, что если выйти из угла и идти вдоль стенок (ближайшие две клетки к ней), то две внешние полосы заполняются тривиально, а в центре остаётся ещё один неправильный квадрат (4 на 4) такого вида (расположение выреза мы, вроде как вольны выбирать сами, но наличие его обязательно, т. к. нормальное хождение по кругу с прохождением углов возможно только на досках 3n-типа):
    1000
    1000
    0000
    0000
    заполнение которого чуть посложнее, но тоже возможно.
    Дык вот, к чему я это всё: есть довольно простая и понятная траектория по которой можно гонять коня без всякого перебора. Задача сводится к поиску способа как посадить на неё коня из произвольной точки.
    Имхо выйдет быстрее перебора
     
  19. Arhara

    Arhara New Member

    Публикаций:
    0
    Регистрация:
    27 апр 2006
    Сообщения:
    10
    Адрес:
    Russia
    А для произвольной доски ?
     
  20. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Проблема нахождения пути для квадратной доски(возможно и в общем случае тоже, не знаю) решается в линейное, то есть O(n) время. Поэтому ищите во-первых все пути, во-вторых на произвольной доске, иначе совсем неинтересно :)