Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 09.06.2011, 19:22   #1
Вася Маклауд
 
Регистрация: 03.04.2011
Сообщений: 6
По умолчанию какая фигура раньше доберется до заданной точки на шахматной доске

Имеется шахматная доска горизонтальные полосы нумеруются числами начиная с 1 вериткальные латинскими буквами начиная с а.Определить какая из пяти фигур король,ферзь,ладья,слон или конь доберутся из заданной начальной точки в заданную конечную за наименьшее количество ходов.Вывести название фигуры,которая раньше всех доберется и кол-во ходов.
Вася Маклауд вне форума Ответить с цитированием
Старый 10.06.2011, 10:29   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,229
По умолчанию

любопытная задачка..

язык программирования какой?
Наработки есть?
Если несколько фигур могут добраться за одинаковое число ходов - то в ответе что должно быть? (все варианты? Один любой? Один вариант - первый подходящий по порядку перечисления фигур?)
Serge_Bliznykov вне форума Ответить с цитированием
Старый 10.06.2011, 13:34   #3
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,577
По умолчанию

такой задачи я не видел. Спасибо вашему преподавателю )
по задаче...
ферзь и ладья добирается до любой клетки поля максимум за 2 хода.
слон тоже за 2 хода( если цвет начальной и конечной клеток совпадают)
Значит можно использовать полный перебор для коня глубиной 2.

Если же надо вывести 1 любое решение - то полный перебор не нужен. Сначала проверяем достигает ли конь нужную клетку за 1 ход. Если достигает то решение - "конь, 1 ход", иначе решение "ферзь, Х ход(ов)", X<=2. Х = 1 если ферзь достигает нужную точку за 1 ход(проверить диагонали и горизонтали, я думаю, не сложно), иначе - Х = 2.
rrrFer вне форума Ответить с цитированием
Старый 10.06.2011, 13:39   #4
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,577
По умолчанию

забыл про короля. Короля нужно учитывать только если нужно вывести все решения.
число ходов, за которое король достигнет точку я бы искал так:

Код:
D = max ( | StartX - FinishX | , | StartY - FinishY | )
не проверял. Тут "| |" - это модуль
rrrFer вне форума Ответить с цитированием
Старый 10.06.2011, 13:43   #5
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,229
По умолчанию

rrrFer, кстати, коллега, я мыслил полностью так же!

Поэтому и задал вопросы TC - какой вариант нужно/можно выводить...
Если один любой, тогда задача сильно упрощается (чистая арифметика), если же все - надо будет для коня перебирать все варианты и искать самый короткий...
Serge_Bliznykov вне форума Ответить с цитированием
Старый 10.06.2011, 15:34   #6
Вася Маклауд
 
Регистрация: 03.04.2011
Сообщений: 6
По умолчанию

Serge_Bliznykov и rrrFer,отвечаю на ваши вопросы)
1.Язык паскаль!
2.если одинаковое количество ходов то выводить старшую по цене(король,ферзь,ладья,слон,конь).
3.препод нашла задачу эту и там как оказлось объявляются клетки в которые нельзя фигуре попадать)
4.Я как понял вы предлагаете решать графами,но вот с ними я пока незнаком(так что если моно расписать примерно)
5,пытался действовать методом перебора(т.е ставил циклы и проверял ходы если фигура попадала в ту клетку в которую якобы нельзя тогда смарел другой ход)но к особо радужным результатам это не привело,к тому же мой препод эт бабушка без пед.образования так что ее объяснения мне не подвластны. Ибо она объясняет одно я прихожу домой и нахожу другое решение.
Вася Маклауд вне форума Ответить с цитированием
Старый 10.06.2011, 15:36   #7
Вася Маклауд
 
Регистрация: 03.04.2011
Сообщений: 6
По умолчанию

клетки в которые нельзя попадать даются в условии,также в условии даются координаты начальной и конечной точки.Все фигуры выходят из точки начала независимо как они расположены при игре.если ни одна из фигур не доберется до конечной точки вывести "Ходов нет".
Вася Маклауд вне форума Ответить с цитированием
Старый 10.06.2011, 15:45   #8
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,577
По умолчанию

Вася Маклауд
у нас тоже нет пед.образования(думаю ни у кого?)
Не понятно что значит "клетка в которую нельзя фигуре попадать". Судя по дальнейшему описанию это уже пройденная клетка(я правильно понял?)
Графы тут никто не предлагал.
Ладью и слона вообще выкиньте из рассмотрения если:
Цитата:
выводить старшую по цене(король,ферзь,ладья,слон,конь).
ЗЫ: на паскале не пишу, помочь не смогу(ИМХО, тут никто и не хочет помогать пока вы сами не приложите усилий{мы не увидим вашего кода}?)
rrrFer вне форума Ответить с цитированием
Старый 10.06.2011, 15:50   #9
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,577
По умолчанию

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

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

Последний раз редактировалось rrrFer; 10.06.2011 в 15:55.
rrrFer вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
расставить 8 ладей на шахматной доске marry Помощь студентам 2 19.11.2010 22:08
Си/Си++ Слоны на шахматной доске Маришка_Курносова Помощь студентам 1 12.09.2010 01:02
монетки на шахматной доске! grimm_jow Общие вопросы C/C++ 2 31.01.2010 10:27
Поиск пути на шахматной доске ходом ферзя A!eI{S@nDrA Помощь студентам 2 16.06.2009 09:51