ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Путь коня по доске
25 сообщений из 26, страница 1 из 2
  1  все
Путь коня по доске
    #34268491
Alexуооо
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alexуооо
Гость
Можете подсказать решение задачи:

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

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

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

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

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

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

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

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

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

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

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

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

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

к вечеру в голове уже не укладывается :)
...
Рейтинг: 0 / 0
23.01.2007, 16:52
| Ответить | Цитировать | Написать  
Путь коня по доске
    #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, 16:59
| Ответить | Цитировать | Написать  
Путь коня по доске
    #34276112
Фотография Gluk (Kazan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gluk (Kazan)
Участник
поиск в ширину с отсечением

по моему так
...
Рейтинг: 0 / 0
23.01.2007, 17:02
| Ответить | Цитировать | Написать  
Путь коня по доске
    #34276211
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Вполне может быть. Я не особо стремлюсь запомнить названия.
...
Рейтинг: 0 / 0
23.01.2007, 17:30
| Ответить | Цитировать | Написать  
25 сообщений из 26, страница 1 из 2
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Путь коня по доске
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=57&msg=34268905&tid=2029596]:
 0ms
get settings:
 8ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 143ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 57ms
get tp. blocked users:
 1ms
others: 214ms
total:  454ms
созд. / загр.: 454ms
x
x
Закрыть


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