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

@SergProgC++ · Регистрация: 02.07.2010

Студворк — интернет-сервис помощи студентам

Приветствую всех форумчан!!!!
Дана задача:
Найти возможные способы для удара ферзем максимального количества вражеских фигур за N проходов исходя из определенного задаваемого положения вражеских фигур, не изменяющих своего положения. Определить кратчайшие.
Подскажите кто может с чего начинать алгоритм выполнения и может ссылочки какие есть с готовыми кодами?

KuKu · 15.10.2010, 21:41

Напомнило "задачу комивояжора", посмотри может поможет.

@Andrew_Lvov · 15.10.2010, 21:51

Рекурсия, где в каждом вызове проверяются все возможные ходы (в т.ч. взятия) ферзём.
При каждом взятии увеличивается счётчик.
Оптимизация: при проверке хода если оставшихся ходов меньше, чем разница с лучшим результатом - пропускаем проверку.
Можно так же запоминать ситуации, что бы не просчитывать по несколько раз, ведь к некоему положению фигур часто можно прийти несколькими способами.

@SergProgC++ · 19.10.2010, 20:03 **[ТС]**

А хотябы фрагменты кода какие нибудь можете написать? чтобы приблизительно стало ясно

KuKu · 19.10.2010, 20:19

Сообщение от SergProgC++

А хотябы фрагменты кода какие нибудь можете написать? чтобы приблизительно стало ясно

Какие фрагменты кода? Вы алгоритм хоть бы выбрали, он вродь как не совсем тривиальный.

@SergProgC++ · 21.10.2010, 19:54 **[ТС]**

Сообщение от KuKu

Какие фрагменты кода? Вы алгоритм хоть бы выбрали, он вродь как не совсем тривиальный.

подскажи какой алгоритм тут надо использовать

KuKu · 21.10.2010, 21:01

вродь сказал посмотри "задачу комвояжора" - схожая задача, для решения которой есть несколько алгоритмов, или как Andrew_Lvov сказал перебором.

@SergProgC++ · 25.10.2010, 22:29 **[ТС]**

было бы не плохо еслиб код кто выложил или часть кода с чего начать можно

valeriikozlov · 25.10.2010, 22:51

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

KuKu · 25.10.2010, 23:14

Любую бить нельзя. Синий - ферзь, красные - кого рубят, на рисунке. К примеру только один вариант рубки в 4 хода, если атакавать сразу верх. Если по диагонали вначале, тот надо больше ходов.

valeriikozlov · 25.10.2010, 23:24

KuKu, согласен. А как картинку вставить в ответе?

KuKu · 25.10.2010, 23:24

в расширенном режиме, нажать скрепку.

valeriikozlov · 25.10.2010, 23:43

в расширенном режиме, нажать скрепку.

В расширенный режим что бы перейти, нужно нажать значек А/А?

KuKu · 25.10.2010, 23:57

вот так

@alexzak · 26.10.2010, 08:31

Сообщение от 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. Поэтому в конце программы нужно проверять пути и отбрасывать неверные.

@SergProgC++ · 02.11.2010, 20:38 **[ТС]**

А пример кода или пошаговый алгоритм ко всему этому есть?

Новые блоги и статьи Все статьи Все блоги /
Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это дополнительная запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .

@SergProgC++ Эксперт GPSS 555 / 414 / 105 Регистрация: 02.07.2010 Сообщений: 1,729

	Удары ферзем по фигурам!!! 15.10.2010, 20:28. Показов 2486. Ответов 15 Метки нет (Все метки) Приветствую всех форумчан!!!! Дана задача: Найти возможные способы для удара ферзем максимального количества вражеских фигур за N проходов исходя из определенного задаваемого положения вражеских фигур, не изменяющих своего положения. Определить кратчайшие. Подскажите кто может с чего начинать алгоритм выполнения и может ссылочки какие есть с готовыми кодами? 0

KuKu 1563 / 1041 / 94 Регистрация: 17.04.2009 Сообщений: 2,995
	15.10.2010, 21:41
	Напомнило "задачу комивояжора", посмотри может поможет. 0

@Andrew_Lvov 261 / 191 / 10 Регистрация: 19.08.2010 Сообщений: 760 Записей в блоге: 1
	15.10.2010, 21:51
	Рекурсия, где в каждом вызове проверяются все возможные ходы (в т.ч. взятия) ферзём. При каждом взятии увеличивается счётчик. Оптимизация: при проверке хода если оставшихся ходов меньше, чем разница с лучшим результатом - пропускаем проверку. Можно так же запоминать ситуации, что бы не просчитывать по несколько раз, ведь к некоему положению фигур часто можно прийти несколькими способами. 0

@SergProgC++ Эксперт GPSS 555 / 414 / 105 Регистрация: 02.07.2010 Сообщений: 1,729
	19.10.2010, 20:03 [ТС]
	А хотябы фрагменты кода какие нибудь можете написать? чтобы приблизительно стало ясно 0

KuKu 1563 / 1041 / 94 Регистрация: 17.04.2009 Сообщений: 2,995
	21.10.2010, 21:01
	вродь сказал посмотри "задачу комвояжора" - схожая задача, для решения которой есть несколько алгоритмов, или как Andrew_Lvov сказал перебором. 0

@SergProgC++ Эксперт GPSS 555 / 414 / 105 Регистрация: 02.07.2010 Сообщений: 1,729
	25.10.2010, 22:29 [ТС]
	было бы не плохо еслиб код кто выложил или часть кода с чего начать можно 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	25.10.2010, 22:51
	Предварительно (я не полностью уверен, но вроде бы правильно будет), алгоритм будет заключаться в следующем: - если есть на линии удара вражеская фигура (или несколько фигур на разных линиях), то нужно бить любую из них. - если нет на линии (линиях) удара никаких фигур, то кратчайшим путем (за два хода) бьем любую из находящихся на поле, и смотрим на пункт первый. 0

KuKu 1563 / 1041 / 94 Регистрация: 17.04.2009 Сообщений: 2,995
	25.10.2010, 23:14
	Любую бить нельзя. Синий - ферзь, красные - кого рубят, на рисунке. К примеру только один вариант рубки в 4 хода, если атакавать сразу верх. Если по диагонали вначале, тот надо больше ходов. Миниатюры 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	25.10.2010, 23:24
	KuKu, согласен. А как картинку вставить в ответе? 0

KuKu 1563 / 1041 / 94 Регистрация: 17.04.2009 Сообщений: 2,995
	25.10.2010, 23:24
	в расширенном режиме, нажать скрепку. 0

KuKu 1563 / 1041 / 94 Регистрация: 17.04.2009 Сообщений: 2,995
	25.10.2010, 23:57
	вот так Миниатюры 0

@SergProgC++ Эксперт GPSS 555 / 414 / 105 Регистрация: 02.07.2010 Сообщений: 1,729
	02.11.2010, 20:38 [ТС]
	А пример кода или пошаговый алгоритм ко всему этому есть? 0