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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
SergProgC++
Эксперт GPSS
314 / 316 / 59
Регистрация: 02.07.2010
Сообщений: 1,360
#1

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

15.10.2010, 20:28. Просмотров 1278. Ответов 15
Метки нет (Все метки)

Приветствую всех форумчан!!!!
Дана задача:
Найти возможные способы для удара ферзем максимального количества вражеских фигур за N проходов исходя из определенного задаваемого положения вражеских фигур, не изменяющих своего положения. Определить кратчайшие.
Подскажите кто может с чего начинать алгоритм выполнения и может ссылочки какие есть с готовыми кодами?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.10.2010, 20:28     Удары ферзем по фигурам!!!
Посмотрите здесь:

FreeKick: бьём штрафные удары
Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем C++
Можно ли как то поставить удары левой рукой так же как и правой?
Привязать код к фигурам C#
Шахматы, ход ферзем C++
Удары током и дребезжащий звук в наушниках
Обход ферзем всех полей доски за 15 ходов (начиная в С3, заканчивая в F6) Prolog
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
KuKu
1554 / 1032 / 75
Регистрация: 17.04.2009
Сообщений: 2,971
15.10.2010, 21:41     Удары ферзем по фигурам!!! #2
Напомнило "задачу комивояжора", посмотри может поможет.
Andrew_Lvov
Эксперт С++
259 / 189 / 5
Регистрация: 19.08.2010
Сообщений: 758
Записей в блоге: 1
15.10.2010, 21:51     Удары ферзем по фигурам!!! #3
Рекурсия, где в каждом вызове проверяются все возможные ходы (в т.ч. взятия) ферзём.
При каждом взятии увеличивается счётчик.
Оптимизация: при проверке хода если оставшихся ходов меньше, чем разница с лучшим результатом - пропускаем проверку.
Можно так же запоминать ситуации, что бы не просчитывать по несколько раз, ведь к некоему положению фигур часто можно прийти несколькими способами.
SergProgC++
Эксперт GPSS
314 / 316 / 59
Регистрация: 02.07.2010
Сообщений: 1,360
19.10.2010, 20:03  [ТС]     Удары ферзем по фигурам!!! #4
А хотябы фрагменты кода какие нибудь можете написать? чтобы приблизительно стало ясно
KuKu
1554 / 1032 / 75
Регистрация: 17.04.2009
Сообщений: 2,971
19.10.2010, 20:19     Удары ферзем по фигурам!!! #5
Цитата Сообщение от SergProgC++ Посмотреть сообщение
А хотябы фрагменты кода какие нибудь можете написать? чтобы приблизительно стало ясно
Какие фрагменты кода? Вы алгоритм хоть бы выбрали, он вродь как не совсем тривиальный.
SergProgC++
Эксперт GPSS
314 / 316 / 59
Регистрация: 02.07.2010
Сообщений: 1,360
21.10.2010, 19:54  [ТС]     Удары ферзем по фигурам!!! #6
Цитата Сообщение от KuKu Посмотреть сообщение
Какие фрагменты кода? Вы алгоритм хоть бы выбрали, он вродь как не совсем тривиальный.
подскажи какой алгоритм тут надо использовать
KuKu
1554 / 1032 / 75
Регистрация: 17.04.2009
Сообщений: 2,971
21.10.2010, 21:01     Удары ферзем по фигурам!!! #7
вродь сказал посмотри "задачу комвояжора" - схожая задача, для решения которой есть несколько алгоритмов, или как Andrew_Lvov сказал перебором.
SergProgC++
Эксперт GPSS
314 / 316 / 59
Регистрация: 02.07.2010
Сообщений: 1,360
25.10.2010, 22:29  [ТС]     Удары ферзем по фигурам!!! #8
было бы не плохо еслиб код кто выложил или часть кода с чего начать можно
valeriikozlov
Эксперт C++
4667 / 2493 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.10.2010, 22:51     Удары ферзем по фигурам!!! #9
Предварительно (я не полностью уверен, но вроде бы правильно будет), алгоритм будет заключаться в следующем:
- если есть на линии удара вражеская фигура (или несколько фигур на разных линиях), то нужно бить любую из них.
- если нет на линии (линиях) удара никаких фигур, то кратчайшим путем (за два хода) бьем любую из находящихся на поле, и смотрим на пункт первый.
KuKu
1554 / 1032 / 75
Регистрация: 17.04.2009
Сообщений: 2,971
25.10.2010, 23:14     Удары ферзем по фигурам!!! #10
Любую бить нельзя. Синий - ферзь, красные - кого рубят, на рисунке. К примеру только один вариант рубки в 4 хода, если атакавать сразу верх. Если по диагонали вначале, тот надо больше ходов.
Миниатюры
Удары ферзем по фигурам!!!  
valeriikozlov
Эксперт C++
4667 / 2493 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.10.2010, 23:24     Удары ферзем по фигурам!!! #11
KuKu, согласен. А как картинку вставить в ответе?
KuKu
1554 / 1032 / 75
Регистрация: 17.04.2009
Сообщений: 2,971
25.10.2010, 23:24     Удары ферзем по фигурам!!! #12
в расширенном режиме, нажать скрепку.
valeriikozlov
Эксперт C++
4667 / 2493 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.10.2010, 23:43     Удары ферзем по фигурам!!! #13
в расширенном режиме, нажать скрепку.
В расширенный режим что бы перейти, нужно нажать значек А/А?
KuKu
1554 / 1032 / 75
Регистрация: 17.04.2009
Сообщений: 2,971
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     Удары ферзем по фигурам!!!
Еще ссылки по теме:

MS Powerpoint Как создать счетчик кликов по движущимся фигурам
Python Сделать игру-кликалку по появляющимся в рандомном месте фигурам
C++ Builder Как задать номера фигурам?
C++ Ферзем попасть с одного заданного поля на другое

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru