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

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

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

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

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

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

Шахматы, ход ферзем - C++
Здраствуйте! Подскажите пожалуйста как запрограммировать ходы ферзя на шахматной доске? Он должен ходить по координатах Х,У и по диагонале....

Ферзем попасть с одного заданного поля на другое - C++
Всем привет, помогите с заданием в С++. Поле шахматной доски определяется парой натуральных чисел, первое из которых задаёт номер...

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

FreeKick: бьём штрафные удары - Спортивные игры
Нашел футбольную игру . Это она для любителей бить штрафные удары. http://go-o-ol.ru/ Может кто помнит на телефоне была такая игра что...

Удары током и дребезжащий звук в наушниках - Компьютерное железо
Здравствуйте! Возникла следующая проблема. Никогда раньше такого не было. Ноутбук HP Envy dv6-7252er. Есть алюминиевые элементы корпуса....

Привязать код к фигурам - C#
Доброго времени суток. Необходимо создать программу, которая будет сортировать по возрастанию прямоугольники. Понятное дело необходимо...

15
KuKu
1558 / 1036 / 78
Регистрация: 17.04.2009
Сообщений: 2,987
15.10.2010, 21:41 #2
Напомнило "задачу комивояжора", посмотри может поможет.
0
Andrew_Lvov
Эксперт С++
259 / 189 / 5
Регистрация: 19.08.2010
Сообщений: 760
Записей в блоге: 1
15.10.2010, 21:51 #3
Рекурсия, где в каждом вызове проверяются все возможные ходы (в т.ч. взятия) ферзём.
При каждом взятии увеличивается счётчик.
Оптимизация: при проверке хода если оставшихся ходов меньше, чем разница с лучшим результатом - пропускаем проверку.
Можно так же запоминать ситуации, что бы не просчитывать по несколько раз, ведь к некоему положению фигур часто можно прийти несколькими способами.
0
SergProgC++
Эксперт GPSS
315 / 317 / 59
Регистрация: 02.07.2010
Сообщений: 1,361
19.10.2010, 20:03  [ТС] #4
А хотябы фрагменты кода какие нибудь можете написать? чтобы приблизительно стало ясно
0
KuKu
1558 / 1036 / 78
Регистрация: 17.04.2009
Сообщений: 2,987
19.10.2010, 20:19 #5
Цитата Сообщение от SergProgC++ Посмотреть сообщение
А хотябы фрагменты кода какие нибудь можете написать? чтобы приблизительно стало ясно
Какие фрагменты кода? Вы алгоритм хоть бы выбрали, он вродь как не совсем тривиальный.
0
SergProgC++
Эксперт GPSS
315 / 317 / 59
Регистрация: 02.07.2010
Сообщений: 1,361
21.10.2010, 19:54  [ТС] #6
Цитата Сообщение от KuKu Посмотреть сообщение
Какие фрагменты кода? Вы алгоритм хоть бы выбрали, он вродь как не совсем тривиальный.
подскажи какой алгоритм тут надо использовать
0
KuKu
1558 / 1036 / 78
Регистрация: 17.04.2009
Сообщений: 2,987
21.10.2010, 21:01 #7
вродь сказал посмотри "задачу комвояжора" - схожая задача, для решения которой есть несколько алгоритмов, или как Andrew_Lvov сказал перебором.
0
SergProgC++
Эксперт GPSS
315 / 317 / 59
Регистрация: 02.07.2010
Сообщений: 1,361
25.10.2010, 22:29  [ТС] #8
было бы не плохо еслиб код кто выложил или часть кода с чего начать можно
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.10.2010, 22:51 #9
Предварительно (я не полностью уверен, но вроде бы правильно будет), алгоритм будет заключаться в следующем:
- если есть на линии удара вражеская фигура (или несколько фигур на разных линиях), то нужно бить любую из них.
- если нет на линии (линиях) удара никаких фигур, то кратчайшим путем (за два хода) бьем любую из находящихся на поле, и смотрим на пункт первый.
0
KuKu
1558 / 1036 / 78
Регистрация: 17.04.2009
Сообщений: 2,987
25.10.2010, 23:14 #10
Любую бить нельзя. Синий - ферзь, красные - кого рубят, на рисунке. К примеру только один вариант рубки в 4 хода, если атакавать сразу верх. Если по диагонали вначале, тот надо больше ходов.
0
Миниатюры
Удары ферзем по фигурам!!!  
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.10.2010, 23:24 #11
KuKu, согласен. А как картинку вставить в ответе?
0
KuKu
1558 / 1036 / 78
Регистрация: 17.04.2009
Сообщений: 2,987
25.10.2010, 23:24 #12
в расширенном режиме, нажать скрепку.
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.10.2010, 23:43 #13
в расширенном режиме, нажать скрепку.
В расширенный режим что бы перейти, нужно нажать значек А/А?
0
KuKu
1558 / 1036 / 78
Регистрация: 17.04.2009
Сообщений: 2,987
25.10.2010, 23:57 #14
вот так
0
Миниатюры
Удары ферзем по фигурам!!!   Удары ферзем по фигурам!!!  
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. Поэтому в конце программы нужно проверять пути и отбрасывать неверные.
0
26.10.2010, 08:31
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.10.2010, 08:31
Привет! Вот еще темы с ответами:

Как задать номера фигурам? - C++ Builder
Помогите пож-ста разобраться в такой задаче: на Image1 ставятся фигуры-точки, например их 2. как им присвоить номера и сделать так, чтобы...

Как создать счетчик кликов по движущимся фигурам - MS Powerpoint
Приветствую! В PowerPoint мной создана презентация - игра-стрелялка с несколькими движущимися автофигурами - прямоугольниками. При...

Обход ферзем всех полей доски за 15 ходов (начиная в С3, заканчивая в F6) - Prolog
Есть такой код, но решает задачу с поля А1 и за 14 ходов. Как переделать код под задание: ферзь находится на поле С3 шахматной доски....

Сделать игру-кликалку по появляющимся в рандомном месте фигурам - Python
Всем привет , я новичок в питоне делаю игру , принцип игры такой, появляется объект на экране к примеру круг или квадрат и через 1 секунду...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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