Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Путь коня по доске / 25 сообщений из 26, страница 1 из 2
  1  все
19.01.2007, 15:09
    #34268491
Alexуооо
Alexуооо
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
Можете подсказать решение задачи:

Дана шахматная доска размером 8х8 и шахматный конь. Программа должна запросить у пользователя координаты клетки поля и поставить туда коня. Задача программы найти и вывести путь коня, при котором он обойдет все клетки доски, становясь в каждую клетку только один раз.

Без использования классов. Я до них ещё не дошёл :( А в инете нашёл решение только с классами
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.01.2007, 15:41
    #34268613
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
либо ищи в инете спец. алгоритм, либо:
строй ОПУПЕННОГО размера дерево (используя рекурсию) и рассматривай так все ходы.
штука медленная до опупения

аффтопитезь: объект либо именован, либо не существует
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.01.2007, 15:42
    #34268622
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
а нужны все пути? или досточно одного любого?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.01.2007, 16:57
    #34268905
Alexуооо
Alexуооо
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
miksoft: В начале программа спрашивает у пользователя начальные координаты коня, и это координата будет точкой начала пути. Т.е. началом может біть любая клетка доски.
Можно рассмотерть вместо доски 8х8 доску 5х5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.01.2007, 16:58
    #34268911
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
аффтопитезь: объект либо именован, либо не существует
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.01.2007, 17:00
    #34268921
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
я же говорил, что она медленная:

аффтопитезь: объект либо именован, либо не существует
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.01.2007, 17:08
    #34268945
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
вопрос все же созрел: как сделать релиз, а не дебаг???

аффтопитезь: объект либо именован, либо не существует
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.01.2007, 17:09
    #34268950
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
п.с. если знать игровые алгоритмы, писал и отлаживал минут 30...

аффтопитезь: объект либо именован, либо не существует
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.01.2007, 17:19
    #34268975
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
тебе возможно пригодится это (ибо без этого пару часов вбивать)

аффтопитезь: объект либо именован, либо не существует
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.01.2007, 17:21
    #34268980
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
а дабы совсем мало что было бы делать, нажми
(CTRL+ALT)(не отпуская)+ASTAFY

аффтопитезь: объект либо именован, либо не существует
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.01.2007, 17:22
    #34268988
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
странно, кстати, для 0,0 думала 4 секунды, а вот для 7,7 (это тоже, но зеркально) думает уже пару минут...

аффтопитезь: объект либо именован, либо не существует
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.01.2007, 07:49
    #34269613
muk07
muk07
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
У меня это дежурный лекционный пример для backtrack и стека. Пристёгнут (CBuilder 5).
Собственно решение, независимое от среды в Horse.cpp, Horse.h.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.01.2007, 09:04
    #34269622
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
muk07У меня это дежурный лекционный пример для backtrack и стека. Пристёгнут (CBuilder 5).
Собственно решение, независимое от среды в Horse.cpp, Horse.h.

бегло пробежался, у меня похоже в пару раз быстрее будет
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.01.2007, 09:08
    #34271110
Gluk (Kazan)
Gluk (Kazan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
Блин, скоро попу подтереть будут просить
Студенты, читайте Вирта, он ХОРОШИЙ
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2007, 12:56
    #34274877
Den_di
Den_di
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
Gluk (Kazan)Блин, скоро попу подтереть будут просить
Студенты, читайте Вирта, он ХОРОШИЙ

А задача не столь и тривиальная. она почти NP - универсальное решение - найти цикл ср всеми вершинами по одному разу. Моя реализация 2-3 раза быстрее и стабильна. Просто Aklin повезло с выбором ветвлений.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2007, 13:14
    #34274971
Gluk (Kazan)
Gluk (Kazan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
Den_di Gluk (Kazan)Блин, скоро попу подтереть будут просить
Студенты, читайте Вирта, он ХОРОШИЙ

А задача не столь и тривиальная. она почти NP - универсальное решение - найти цикл ср всеми вершинами по одному разу. Моя реализация 2-3 раза быстрее и стабильна. Просто Aklin повезло с выбором ветвлений.

Задача РАЗУМЕЕТСЯ не тривиальна, но ПОДРОБНО описана у Вирта "Алгоритмы и структуры данных"
Кстати где-то на форуме (искать лень) решение softwarer-а на SQL
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2007, 14:45
    #34275437
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
Gluk (Kazan)Кстати где-то на форуме (искать лень) решение softwarer-а на SQL
/topic/321015&pg=3#2968446
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2007, 14:50
    #34275465
Gluk (Kazan)
Gluk (Kazan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
Угу, там естественно полный перебор, а не поиск с возвратом как у Вирта
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2007, 15:27
    #34275680
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
Полного перебора там нет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2007, 16:25
    #34275965
Gluk (Kazan)
Gluk (Kazan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
согласен, но и поиска с возвратом тоже
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2007, 16:43
    #34276052
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
Там если угодно "параллельный поиск с возвратом". То есть рассматривается не одна текущая позиция, а множество, и соответственно применением допустимых ходов получается очередное множество допустимых позиций.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2007, 16:52
    #34276090
Gluk (Kazan)
Gluk (Kazan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
softwarerТам если угодно "параллельный поиск с возвратом". То есть рассматривается не одна текущая позиция, а множество, и соответственно применением допустимых ходов получается очередное множество допустимых позиций.

к вечеру в голове уже не укладывается :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2007, 16:59
    #34276106
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
При инициализации в массив "позиций к рассмотрению" заносится путь (a1).

Далее, на каждом шаге рассматриваются "текущие пути" и делается попытка расширить их допустимыми ходами (то есть соответствующими ходу коня и отсутствующими в предыдущем пути). Скажем, (a1) расширяется до (a1, c2) и (a1, b3). На втором шаге получаем (a1, c2, a3), (a1, c2, b4), (a1, c2, d4), (a1, c2, e3), (a1, c2, e1), (a1, b3, a5), (a1, b3, c5), (a1, b3, d4), (a1, b3, d2), (a1, b3, c1). И так далее.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2007, 17:02
    #34276112
Gluk (Kazan)
Gluk (Kazan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
поиск в ширину с отсечением

по моему так
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.01.2007, 17:30
    #34276211
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Путь коня по доске
Вполне может быть. Я не особо стремлюсь запомнить названия.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Путь коня по доске / 25 сообщений из 26, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 579ms
Закрыть
start [/forum/topic.php?fid=57&tablet=1&tid=2029596]:
 0ms
get settings:
 10ms
get forum list:
 20ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 201ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 76ms
get tp. blocked users:
 1ms
others: 248ms
total:  579ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]