Форум программистов, компьютерный форум CyberForum.ru

Удары ферзем по фигурам!!! - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
SergProgC++
Эксперт GPSS
 Аватар для SergProgC++
314 / 316 / 59
Регистрация: 02.07.2010
Сообщений: 1,316
15.10.2010, 20:28     Удары ферзем по фигурам!!! #1
Приветствую всех форумчан!!!!
Дана задача:
Найти возможные способы для удара ферзем максимального количества вражеских фигур за N проходов исходя из определенного задаваемого положения вражеских фигур, не изменяющих своего положения. Определить кратчайшие.
Подскажите кто может с чего начинать алгоритм выполнения и может ссылочки какие есть с готовыми кодами?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
KuKu
 Аватар для KuKu
1538 / 1016 / 69
Регистрация: 17.04.2009
Сообщений: 2,946
15.10.2010, 21:41     Удары ферзем по фигурам!!! #2
Напомнило "задачу комивояжора", посмотри может поможет.
Andrew_Lvov
Эксперт C++
 Аватар для Andrew_Lvov
259 / 189 / 5
Регистрация: 19.08.2010
Сообщений: 758
Записей в блоге: 1
15.10.2010, 21:51     Удары ферзем по фигурам!!! #3
Рекурсия, где в каждом вызове проверяются все возможные ходы (в т.ч. взятия) ферзём.
При каждом взятии увеличивается счётчик.
Оптимизация: при проверке хода если оставшихся ходов меньше, чем разница с лучшим результатом - пропускаем проверку.
Можно так же запоминать ситуации, что бы не просчитывать по несколько раз, ведь к некоему положению фигур часто можно прийти несколькими способами.
SergProgC++
Эксперт GPSS
 Аватар для SergProgC++
314 / 316 / 59
Регистрация: 02.07.2010
Сообщений: 1,316
19.10.2010, 20:03  [ТС]     Удары ферзем по фигурам!!! #4
А хотябы фрагменты кода какие нибудь можете написать? чтобы приблизительно стало ясно
KuKu
 Аватар для KuKu
1538 / 1016 / 69
Регистрация: 17.04.2009
Сообщений: 2,946
19.10.2010, 20:19     Удары ферзем по фигурам!!! #5
Цитата Сообщение от SergProgC++ Посмотреть сообщение
А хотябы фрагменты кода какие нибудь можете написать? чтобы приблизительно стало ясно
Какие фрагменты кода? Вы алгоритм хоть бы выбрали, он вродь как не совсем тривиальный.
SergProgC++
Эксперт GPSS
 Аватар для SergProgC++
314 / 316 / 59
Регистрация: 02.07.2010
Сообщений: 1,316
21.10.2010, 19:54  [ТС]     Удары ферзем по фигурам!!! #6
Цитата Сообщение от KuKu Посмотреть сообщение
Какие фрагменты кода? Вы алгоритм хоть бы выбрали, он вродь как не совсем тривиальный.
подскажи какой алгоритм тут надо использовать
KuKu
 Аватар для KuKu
1538 / 1016 / 69
Регистрация: 17.04.2009
Сообщений: 2,946
21.10.2010, 21:01     Удары ферзем по фигурам!!! #7
вродь сказал посмотри "задачу комвояжора" - схожая задача, для решения которой есть несколько алгоритмов, или как Andrew_Lvov сказал перебором.
SergProgC++
Эксперт GPSS
 Аватар для SergProgC++
314 / 316 / 59
Регистрация: 02.07.2010
Сообщений: 1,316
25.10.2010, 22:29  [ТС]     Удары ферзем по фигурам!!! #8
было бы не плохо еслиб код кто выложил или часть кода с чего начать можно
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.10.2010, 22:51     Удары ферзем по фигурам!!! #9
Предварительно (я не полностью уверен, но вроде бы правильно будет), алгоритм будет заключаться в следующем:
- если есть на линии удара вражеская фигура (или несколько фигур на разных линиях), то нужно бить любую из них.
- если нет на линии (линиях) удара никаких фигур, то кратчайшим путем (за два хода) бьем любую из находящихся на поле, и смотрим на пункт первый.
KuKu
 Аватар для KuKu
1538 / 1016 / 69
Регистрация: 17.04.2009
Сообщений: 2,946
25.10.2010, 23:14     Удары ферзем по фигурам!!! #10
Любую бить нельзя. Синий - ферзь, красные - кого рубят, на рисунке. К примеру только один вариант рубки в 4 хода, если атакавать сразу верх. Если по диагонали вначале, тот надо больше ходов.
Миниатюры
Удары ферзем по фигурам!!!  
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.10.2010, 23:24     Удары ферзем по фигурам!!! #11
KuKu, согласен. А как картинку вставить в ответе?
KuKu
 Аватар для KuKu
1538 / 1016 / 69
Регистрация: 17.04.2009
Сообщений: 2,946
25.10.2010, 23:24     Удары ферзем по фигурам!!! #12
в расширенном режиме, нажать скрепку.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.10.2010, 23:43     Удары ферзем по фигурам!!! #13
в расширенном режиме, нажать скрепку.
В расширенный режим что бы перейти, нужно нажать значек А/А?
KuKu
 Аватар для KuKu
1538 / 1016 / 69
Регистрация: 17.04.2009
Сообщений: 2,946
25.10.2010, 23:57     Удары ферзем по фигурам!!! #14
вот так
Миниатюры
Удары ферзем по фигурам!!!   Удары ферзем по фигурам!!!  
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
26.10.2010, 08:31     Удары ферзем по фигурам!!! #15
Цитата Сообщение от KuKu Посмотреть сообщение
Любую бить нельзя. Синий - ферзь, красные - кого рубят, на рисунке. К примеру только один вариант рубки в 4 хода, если атакавать сразу верх. Если по диагонали вначале, тот надо больше ходов.
Для начала надо постоить взвешенный граф всех передвижений ферзя от одной фигуры к другой. Вершины графа - это поля на шахматной доске, где находятся фигуры или сам ферзь. Вес ребра в графе будет равен количеству шагов, которое ферзь должен сделать от поля одной вершины к другой. Сделаем это для твоего рисунка. Но сначала определим координаты фигур (в шахматной нотации):

ферзь: c2
фигуры: c5, c8, f3, f5

Вершины в нашем графе будут такие: c2, c5, c8, f3, f5.
Ребра:
c2-c5, вес=1
c2-c8, 1
c2-f3, 2 (нужно два шага)
c2-f5, 1
c5-c8, 1
c5-f3, 2
c5-f5, 1
c8-f3, 2
c8-f5, 1
f3-f5, 1

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

Но есть еще одна тонкость. Иногда таким образом будут находится неверные пути, т.е. ферзь с с2 на с8, перескакивая через с5. Поэтому в конце программы нужно проверять пути и отбрасывать неверные.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.11.2010, 20:38     Удары ферзем по фигурам!!!
Еще ссылки по теме:

Удары током и дребезжащий звук в наушниках
Обход ферзем всех полей доски за 15 ходов (начиная в С3, заканчивая в F6) Prolog

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
SergProgC++
Эксперт GPSS
 Аватар для SergProgC++
314 / 316 / 59
Регистрация: 02.07.2010
Сообщений: 1,316
02.11.2010, 20:38  [ТС]     Удары ферзем по фигурам!!! #16
А пример кода или пошаговый алгоритм ко всему этому есть?
Yandex
Объявления
02.11.2010, 20:38     Удары ферзем по фигурам!!!
Ответ Создать тему
Опции темы

Текущее время: 21:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru