Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Задачи _ Шахматный конь
Автор: Сергей Меркурьев 25.05.2009 21:58
В общем задача заключается в том, чтобы по введённому месту на доске (e1, h3, c6) программа выводила все возможные ходы конём. То есть если мы введём a1, то программа должна вывести следующие значения - b3, c2.
Помогите мне понять как построить алгоритм решения задачи. (как Вы понимаете,что на доске клетка а1 находится в нижнем левом углу. А h8 находится в верхнем правом углу)
Автор: Krjuger 25.05.2009 22:16
Ну как идея.
Смотри что нам дает положение коня,это цифра и буква,первое ограничение,не вылезаем за алфавит,второе по цифрам.Какое дальше ограничение,если буква меняется на 1(с А на Б например),то число может либо увеличиться,либо уменьшитьсяна 2,и проверяеш,если при уменьшении ты вылитаеш за граници дозволенного(напимер был а1,по алфавину влево ты уйти не можеш,следовательно только на Б,либо С,но мы для условности берем пока что Б,значит ты из А1 можеш уйти либо в Б3 либо в Б-1,но б-1 это вылет за доску,поэтому остается Б3,а вообще суть задачи заключается в том,чтобы ограничить грамотно поле и разрешить только 2 варианта либо на 2 по алфавиту в +- и на 1 по числам,либо на 2 по числам и на 1 по алфавиту,дальше проверка границ.
А вообще можно все поле запихнуть в массив,дальше перебрать все движения коня(ну то что я гворил про движение) и потом просто проверять на принадлежность массиву,если принадлежит,то печать,если нет то увы.Код писать не стану,а то обругают еще...)))
Как проверить,ну ты ставиш допустим,чтобы числовая переменная была от 1 до 10 вроде(уж не помню давно не играл) ну и алфавит обьвляеш множеством.
Автор: Сергей Меркурьев 25.05.2009 22:28
То есть доску можно описать следующим образом:
Var a:array[1..8,a..h] of char;
...
...
For i:=8 downto 1 do
For j:=a to h do
a[i,j]:=j+i;
Я не очень разбираюсь в таких выражениях, и я не уверен что может быть вот это [1..8,a..h] и вот это a[i,j]:=j+i;
Но ведь что-то подобное можно сделать?
Автор: volvo 25.05.2009 22:34
[1..8,'a'..'h'] - вполне... Хотя, можно и первый вариант реализовать... В FAQ-е был? Про шахматные задачи читал, чтоб велосипед-то не изобретать?
Автор: Сергей Меркурьев 25.05.2009 23:00
Сейчас взгляну... Но как я понял ход мыслей у меня правильный? 
Автор: Krjuger 25.05.2009 23:08
Ну если ты захотел через массив реализовывать,то первый шаг ты сделал правильно.
Хотя, можно и первый вариант реализовать
Это через аски чтоли?вроде как буквы там подрят расположены.И еще
[1..8,'a'..'h']
Ну если он берет "of char",разве не ['1'..'8','a'..'h'] должно быть?Или я что то путаю.
Автор: Сергей Меркурьев 25.05.2009 23:09
volvo, Что-то я не очень там могу найти это))
Krjuger, всё возможно... Только я с типом char очень мало работал))) Так что могу наделать сотни ошибок.
Автор: Krjuger 25.05.2009 23:14
Ну я больше к volvo обращался,чем к тебе,ведь это его вариант был.
А вот тебе конкретная ссылка на этом же форуме,я хз можно ли их тут размещать.
http://forum.pascal.net.ru/index.php?showtopic=2503
Автор: Сергей Меркурьев 25.05.2009 23:23
Ну то что там записано, это для меня чуть-чуть трудновато... Причём я многово ещё не знаю... Так сказать изучаю азы программирования...
Ну вернёмся к задаче)
Значит таким образом записать шахматное поле можно?
Var a:array['1'..'8','a'..'h'] of char;
...
...
For i:='8' downto '1' do
For j:='a' to 'h' do
a[i,j]:=j+i;
Меня смущает данная надпись - a[i,j]:=j+i;
Автор: Krjuger 25.05.2009 23:41
Ну эта запись ты понимаеш что говорит?ну смотри как пример a[a,1] это самый первый элемент в массиве и ты ему присваиваеш значение этого поля.то есть у тебя получается элемент с координатами а,1 развен а1,кстати тогда у тебя должно быть не of char(char это только 1 элемент а у тебя их 2) a of string[2].
Да кстати поменяй тогда,в описании массива сначала буквы потом цифры иначе будет 1а
Автор: Сергей Меркурьев 25.05.2009 23:43
В таком случае можно осуществить такую запись?
Var a:array[1..8,'a'..'h'] of string;
Автор: Krjuger 25.05.2009 23:46
Можно, но string[2] будет достаточно,зачем тебе выделать лишную память,если у тебя вполне конкретные цели.,а вообще вот так будет лучше.
печать на экран чисто формальна,чтобы ты наглядно понял,что значит та строчка.
...
...
For i:='8' downto '1' do begin
For j:='a' to 'h' do begin
a[i,j]:=j+i;
write(a[i,j]);
end;
writeln;
end;
Автор: volvo 25.05.2009 23:47
{ Хочу - так: }
Var a:array['1'..'8','a'..'h'] of char;
{ или так: }
Var a:array[1 .. 8, 'a' .. 'h'] of char;
{ ну, можно и так: }
Const
a = 'a';
h = 'h';
Var a:array[1 .. 8, a .. h] of char;
Var a:array['1'..'8','a'..'h'] of String[2];, в один Char строку не засунешь...
Автор: Сергей Меркурьев 25.05.2009 23:50
Krjuger, нет нельзя потому что вся доска сделана именно таким видом:
Автор: Krjuger 25.05.2009 23:56
Тема слишком горяча,даже пост отредактировать низя 
.Насчет ответа мне, спс,запомню,хотя роли не играет.Понимаеш,как ты запихнет туда поле,роли не играет,разница будет в том что у тебя получаться перевернутые шахматы(как будто смотриш на ходы противника),а если оно привильно,то на результат это не повлияет,тебе же надо вывести значение поля.
Автор: Сергей Меркурьев 25.05.2009 23:58
Ну да значения! Но что бы данные значения вывести нужно знать как они находятся на поле. Тут всё таки желательно учитывать в каком положении находится доска шахмат.
Автор: Krjuger 26.05.2009 0:03
Покрути монитор и будет тебе счастье,только не выкрути совсем))))))Если бы ты собираться графику подключать и все это визуаально оформлять,то да,а так у тебя в виде результата только числа.
Хотя в общем это пустой треп))))Делай своим вариантом он эстетичнее)
Автор: volvo 26.05.2009 0:04
А теперь - внимание: вопрос на засыпку. Зачем заполнять матрицу идентификатором клетки, если этот же идентификатор в любую секунду можно по индексам получить, может мне кто-нибудь объяснить? Что это мне даст? В матрице надо хранить не обозначение клетки, а признак того, может ли в определенную клетку попасть конь или нет...
Автор: Krjuger 26.05.2009 0:07
А это уже другой вопрос,у нас не спрашивали,надо ли это или нет,а спрашивали,что это делает)))))и что то мне подсказывает,что это человек взял либо из какого нить фака,либо из чьей нить задачи.
Автор: Сергей Меркурьев 26.05.2009 0:07
Ну так после того как мы нашли данную клетку, как нам переобозначить число в букву? (если только не глупым перебором 1-а 2-b)
Автор: volvo 26.05.2009 0:09
А тебе что, сообразительности не хватает, сказать человеку, что это ему не надо? Что ж ты сам-то ждешь КОРРЕКТНЫХ ответов, а даешь какие???+ я все-таки настоятельно рекомендую топикстартеру просмотреть в FAQ-е алгоритмы Варнсдорфа (и тот, что перед ним) еще раз, он содержит бОльшую часть решения... Разберись с ними, если что непонятно - задавай вопросы, а не "просто чтобы спросить..."
Автор: Сергей Меркурьев 26.05.2009 0:10
Ну хорошо. Посмотрю потом поинтересуюсь)
Автор: Krjuger 26.05.2009 0:12
Эм а зачем тебе число в букву преобразовывать,я тебе сказал 2 схемы по котрым может двигаться конь,ты просто проверяеш,есть ли элемент в твем массиве,если есть то тру,если нету то фолс,и потом все тру печатаеш.
volvo, ему даже ссылку скинул на них,но человек ответил,что слишком сложно для него.
Насчет того что нужно это или нет
тебе что, сообразительности не хватает, сказать человеку, что это ему не надо?
Ну для начала,используя его способ тоже можно решить,просто это менее рационально,но уж лучше сделать задачу,хоть как нибудь(ну чтоб правильно работала),а уж потом пытаться оптимизировать.Я думаю через ООП,эту задачу можно решить более красиво,и коротко,но человек врятли пока что в этом разбереться,плюс твой совет предполагает,что у нас массив будет хранить булеву переменную чтоли?Мож для человека это сложно7 ты не задумывался?
Автор: Client 26.05.2009 0:14
for x2:=x1-2 to x1+2 doX1,Y1-первоначальная клетка, X2,Y2-возможный переход (как в системе координат).
for y2:=y1-2 to y1+2 do
if ((abs(x1-x2)=1) and (abs(y1-y2)=2) or
(abs(x1-x2)=2) and (abs(y1-y2)=1)) and
(x1 in [1..8]) and (y1 in [1..8])
then writeln(x2,y2)
Автор: Сергей Меркурьев 26.05.2009 0:18
Хм как бы то ни было странно но задача решается с данным алгоритмом!
Но я всё таки попытаюсь её доделать своим способом. Так как в данном случае программа выводт только но мера ячеек, а не букву и цифру.
Автор: Krjuger 26.05.2009 0:24
Вот тебе человек щас предложил именно то,что я говорил,только вариантом банального перебора.тебе надо лиш немного изменть его процедуру,просто он делает с числами,то каждая буква в аски код переводится числом и вроде функция возвращения числа называется ord(x);,поправьте,если ошибаюсь.
Автор: Сергей Меркурьев 26.05.2009 22:36
В общем либо сегодня либо послезавтра, я это попытаюсь решить до конца)
Автор: Сергей Меркурьев 26.05.2009 23:20
Ха! Всё сделал)) Проверил все 64 теста))) олностью работает)))
program N_5;
var i,j,q,w,ibr,cod:integer;
s:string;
a:array[1..8,1..8] of integer;
Begin
Read (S);
case s[1] of
'a':s[1]:='1';
'b':s[1]:='2';
'c':s[1]:='3';
'd':s[1]:='4';
'e':s[1]:='5';
'f':s[1]:='6';
'g':s[1]:='7';
'h':s[1]:='8';
End;
Val(s,ibr,cod);
q:=ibr div 10;
w:=ibr mod 10;
For i:=q-2 to q+2 do
For j:=w-2 to w+2 do
If ((abs(q-i)=1) and (abs(w-j)=2)) or
((abs(q-i)=2) and (abs(w-j)=1)) and
((q>=1) and (q<=8)) and ((w>=1) and (w<=8)) then
If ((i>0) and (j>0)) and ((i<=8) and (j<=8)) then Begin
case i of
1:Write('a');
2:Write('b');
3:Write('c');
4:Write('d');
5:Write('e');
6:Write('f');
7:Write('g');
8:Write('h');
End;
Writeln (j);
End;
End.
Правда мне тут пришлось переводить цифры в буквы, буквы в цифры)) Но зато я её сделал))
Автор: Krjuger 26.05.2009 23:24
Тебер дебагер вводиш свои переменные и смотриш посторочно что в них записывается на каждой строке,и когда увидеш что число в переменной вышло за рамки дозволенного смотриш почему так произошло.короче с дебагером учись работать.Скорее всего у тебя проблемы с проверкой на принадлежность массиву.
Автор: Сергей Меркурьев 26.05.2009 23:28
Спасибо, но я уже разобрался))