Pers.narod.ru. Алгоритмы. Строим дерево игры (задача С3 ЕГЭ по информатике) |
В этой заметке описана и приведена программа для построения полных деревьев игр, в которых игроки поочерёдно делают ходы, сводящиеся к перемещению фишки на игровом поле, добавлению/удалению камней в одну из двух куч и тому подобным легко формализуемым действиям.
Пример такой задачи показан ниже. С небольшими вариациями она включается в варианты итогового ЕГЭ по информатике 2006-2010 гг. (номер задачи C3).
Два игрока играют в следующую игру. На координатной плоскости стоит фишка. В начале игры фишка находится в точке с координатами (-2,-1). Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3,y), (x,y+4), (x+2,y+2). Игра заканчивается, как только расстояние от фишки до начала координат превысит число 9. Выигрывает игрок, который сделал последний ход. Кто выигрывает при безошибочной игре - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
В качестве решения учащийся должен представить неполное дерево игры, то есть, описать игровые ситуации, возникающие после возможных ходов первого и второго игроков. Наша программа не будет заниматься выбором выигрышной стратегии, она просто покажет полное дерево игры в удобном для восприятия и анализа виде. Кроме того, программа может служить примером компактного рекурсивного решения подобных задач (о рекурсии см. главу 18 учебника по Паскалю, а о реализации переборных стратегий на Паскале - эту статью).
Так как дерево может оказаться довольно длинным, вместо вывода на консоль результаты будем выводить в текстовый файл c3.txt. Для вывода на экран просто замените имя файла в операторе assign(f,'c3.txt'); на con.
Все исходные данные игры опишем в виде констант:
const MAXLEVEL=100; {Максимальное число ходов}
MAXSTEPS=3; {Число вариантов хода}
x0=-2; {Начальная позиция}
y0=-1; {игры}
hod:array [1..MAXSTEPS,1..2] of integer = ( {варианты ходов}
(3,0), (0,4), (2,2) {в виде смещений координат фишки по осям x и y}
);
Сама игра будет писаться в двумерный массив, по 1 ходу на строку:
var game:array [1..MAXLEVEL,1..2] of integer;
Перебором ходов будет заниматься метод step, которому мы передадим начальную позицию игры и номер хода l (он же будет служить номером строки массива game, в которую пишется этот ход):
step(x0,y0,1);
Метод step сохранит в массиве game очередной ход, вызовом метода endofgame проверит, не достигнут ли конец игры (если да, последовательность ходов игры напечатается методом print), а затем переберёт в цикле все возможные ходы, рекурсивно вызвав себя для каждого из них с изменёнными значениями параметров. Получится вот что:
procedure step (x,y,l:integer);
{x,y - координаты точки, l - уровень просмотра}
var i:integer;
begin
game[l,1]:=x;
game[l,2]:=y;
if endofgame(l) then print(l)
else for i:=1 to MAXSTEPS do step (x+hod[i,1],y+hod[i,2],l+1);
end;
Метод endofgame использует для проверки завершения игры условие задачи - достижение очередным ходом расстояния от начала координат, большего 9. Подсчёт расстояния сделает функция dist:
function dist(x,y:integer):real; begin dist:=sqrt(sqr(x)+sqr(y)); end; function endofgame (l:integer):boolean; begin endofgame:=dist(game[l,1],game[l,2])>9; end;
Метод print распечатает на отдельной строке очередную игру, а в конце выведет победителя (игрока, сделавшего последний ход). Так как ходы делались по очереди, для выявления победителя достаточно проверить чётность или нечётность значения l:
procedure print(l:integer);
var i:integer;
begin
writeln (f);
for i:=1 to l do write (f,'(',game[i,1]:2,',',game[i,2]:2,') ');
if l mod 2 = 0 then write (f,'1 win')
else write (f,'2 win');
end;
Осталось соединить всё воедино и получить работающую программу:
uses crt;
const MAXLEVEL=100;
MAXSTEPS=3;
x0=-2;
y0=-1;
hod:array [1..MAXSTEPS,1..2] of integer = (
(3,0), (0,4), (2,2)
);
var game:array [1..MAXLEVEL,1..2] of integer;
f:text; fname:string;
function dist(x,y:integer):real;
begin
dist:=sqrt(sqr(x)+sqr(y));
end;
function endofgame (l:integer):boolean;
begin
endofgame:=dist(game[l,1],game[l,2])>9;
end;
procedure print(l:integer);
var i:integer;
begin
writeln (f);
for i:=1 to l do write (f,'(',game[i,1]:2,',',game[i,2]:2,') ');
if l mod 2 = 0 then write (f,'1 win')
else write (f,'2 win');
end;
procedure step (x,y,l:integer);
{x,y - координаты точки, l - уровень просмотра}
var i:integer;
begin
game[l,1]:=x;
game[l,2]:=y;
if endofgame(l) then print(l)
else for i:=1 to MAXSTEPS do step (x+hod[i,1],y+hod[i,2],l+1);
end;
begin
clrscr;
assign(f,'c3.txt');{con}
rewrite(f);
step(x0,y0,1);
close (f);
end.
Вот листинг файла c3.txt, который она создала:
(-2,-1) ( 1,-1) ( 4,-1) ( 7,-1) (10,-1) 2 win (-2,-1) ( 1,-1) ( 4,-1) ( 7,-1) ( 7, 3) (10, 3) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 7,-1) ( 7, 3) ( 7, 7) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 7,-1) ( 7, 3) ( 9, 5) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 7,-1) ( 9, 1) 2 win (-2,-1) ( 1,-1) ( 4,-1) ( 4, 3) ( 7, 3) (10, 3) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 4, 3) ( 7, 3) ( 7, 7) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 4, 3) ( 7, 3) ( 9, 5) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 4, 3) ( 4, 7) ( 7, 7) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 4, 3) ( 4, 7) ( 4,11) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 4, 3) ( 4, 7) ( 6, 9) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 4, 3) ( 6, 5) ( 9, 5) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 4, 3) ( 6, 5) ( 6, 9) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 4, 3) ( 6, 5) ( 8, 7) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 6, 1) ( 9, 1) 2 win (-2,-1) ( 1,-1) ( 4,-1) ( 6, 1) ( 6, 5) ( 9, 5) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 6, 1) ( 6, 5) ( 6, 9) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 6, 1) ( 6, 5) ( 8, 7) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 6, 1) ( 8, 3) (11, 3) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 6, 1) ( 8, 3) ( 8, 7) 1 win (-2,-1) ( 1,-1) ( 4,-1) ( 6, 1) ( 8, 3) (10, 5) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 4, 3) ( 7, 3) (10, 3) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 4, 3) ( 7, 3) ( 7, 7) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 4, 3) ( 7, 3) ( 9, 5) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 4, 3) ( 4, 7) ( 7, 7) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 4, 3) ( 4, 7) ( 4,11) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 4, 3) ( 4, 7) ( 6, 9) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 4, 3) ( 6, 5) ( 9, 5) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 4, 3) ( 6, 5) ( 6, 9) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 4, 3) ( 6, 5) ( 8, 7) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 1, 7) ( 4, 7) ( 7, 7) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 1, 7) ( 4, 7) ( 4,11) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 1, 7) ( 4, 7) ( 6, 9) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 1, 7) ( 1,11) 2 win (-2,-1) ( 1,-1) ( 1, 3) ( 1, 7) ( 3, 9) 2 win (-2,-1) ( 1,-1) ( 1, 3) ( 3, 5) ( 6, 5) ( 9, 5) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 3, 5) ( 6, 5) ( 6, 9) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 3, 5) ( 6, 5) ( 8, 7) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 3, 5) ( 3, 9) 2 win (-2,-1) ( 1,-1) ( 1, 3) ( 3, 5) ( 5, 7) ( 8, 7) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 3, 5) ( 5, 7) ( 5,11) 1 win (-2,-1) ( 1,-1) ( 1, 3) ( 3, 5) ( 5, 7) ( 7, 9) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 6, 1) ( 9, 1) 2 win (-2,-1) ( 1,-1) ( 3, 1) ( 6, 1) ( 6, 5) ( 9, 5) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 6, 1) ( 6, 5) ( 6, 9) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 6, 1) ( 6, 5) ( 8, 7) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 6, 1) ( 8, 3) (11, 3) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 6, 1) ( 8, 3) ( 8, 7) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 6, 1) ( 8, 3) (10, 5) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 3, 5) ( 6, 5) ( 9, 5) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 3, 5) ( 6, 5) ( 6, 9) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 3, 5) ( 6, 5) ( 8, 7) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 3, 5) ( 3, 9) 2 win (-2,-1) ( 1,-1) ( 3, 1) ( 3, 5) ( 5, 7) ( 8, 7) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 3, 5) ( 5, 7) ( 5,11) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 3, 5) ( 5, 7) ( 7, 9) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 5, 3) ( 8, 3) (11, 3) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 5, 3) ( 8, 3) ( 8, 7) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 5, 3) ( 8, 3) (10, 5) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 5, 3) ( 5, 7) ( 8, 7) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 5, 3) ( 5, 7) ( 5,11) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 5, 3) ( 5, 7) ( 7, 9) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 5, 3) ( 7, 5) (10, 5) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 5, 3) ( 7, 5) ( 7, 9) 1 win (-2,-1) ( 1,-1) ( 3, 1) ( 5, 3) ( 7, 5) ( 9, 7) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 4, 3) ( 7, 3) (10, 3) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 4, 3) ( 7, 3) ( 7, 7) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 4, 3) ( 7, 3) ( 9, 5) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 4, 3) ( 4, 7) ( 7, 7) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 4, 3) ( 4, 7) ( 4,11) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 4, 3) ( 4, 7) ( 6, 9) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 4, 3) ( 6, 5) ( 9, 5) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 4, 3) ( 6, 5) ( 6, 9) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 4, 3) ( 6, 5) ( 8, 7) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 1, 7) ( 4, 7) ( 7, 7) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 1, 7) ( 4, 7) ( 4,11) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 1, 7) ( 4, 7) ( 6, 9) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 1, 7) ( 1,11) 2 win (-2,-1) (-2, 3) ( 1, 3) ( 1, 7) ( 3, 9) 2 win (-2,-1) (-2, 3) ( 1, 3) ( 3, 5) ( 6, 5) ( 9, 5) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 3, 5) ( 6, 5) ( 6, 9) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 3, 5) ( 6, 5) ( 8, 7) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 3, 5) ( 3, 9) 2 win (-2,-1) (-2, 3) ( 1, 3) ( 3, 5) ( 5, 7) ( 8, 7) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 3, 5) ( 5, 7) ( 5,11) 1 win (-2,-1) (-2, 3) ( 1, 3) ( 3, 5) ( 5, 7) ( 7, 9) 1 win (-2,-1) (-2, 3) (-2, 7) ( 1, 7) ( 4, 7) ( 7, 7) 1 win (-2,-1) (-2, 3) (-2, 7) ( 1, 7) ( 4, 7) ( 4,11) 1 win (-2,-1) (-2, 3) (-2, 7) ( 1, 7) ( 4, 7) ( 6, 9) 1 win (-2,-1) (-2, 3) (-2, 7) ( 1, 7) ( 1,11) 2 win (-2,-1) (-2, 3) (-2, 7) ( 1, 7) ( 3, 9) 2 win (-2,-1) (-2, 3) (-2, 7) (-2,11) 1 win (-2,-1) (-2, 3) (-2, 7) ( 0, 9) ( 3, 9) 2 win (-2,-1) (-2, 3) (-2, 7) ( 0, 9) ( 0,13) 2 win (-2,-1) (-2, 3) (-2, 7) ( 0, 9) ( 2,11) 2 win (-2,-1) (-2, 3) ( 0, 5) ( 3, 5) ( 6, 5) ( 9, 5) 1 win (-2,-1) (-2, 3) ( 0, 5) ( 3, 5) ( 6, 5) ( 6, 9) 1 win (-2,-1) (-2, 3) ( 0, 5) ( 3, 5) ( 6, 5) ( 8, 7) 1 win (-2,-1) (-2, 3) ( 0, 5) ( 3, 5) ( 3, 9) 2 win (-2,-1) (-2, 3) ( 0, 5) ( 3, 5) ( 5, 7) ( 8, 7) 1 win (-2,-1) (-2, 3) ( 0, 5) ( 3, 5) ( 5, 7) ( 5,11) 1 win (-2,-1) (-2, 3) ( 0, 5) ( 3, 5) ( 5, 7) ( 7, 9) 1 win (-2,-1) (-2, 3) ( 0, 5) ( 0, 9) ( 3, 9) 2 win (-2,-1) (-2, 3) ( 0, 5) ( 0, 9) ( 0,13) 2 win (-2,-1) (-2, 3) ( 0, 5) ( 0, 9) ( 2,11) 2 win (-2,-1) (-2, 3) ( 0, 5) ( 2, 7) ( 5, 7) ( 8, 7) 1 win (-2,-1) (-2, 3) ( 0, 5) ( 2, 7) ( 5, 7) ( 5,11) 1 win (-2,-1) (-2, 3) ( 0, 5) ( 2, 7) ( 5, 7) ( 7, 9) 1 win (-2,-1) (-2, 3) ( 0, 5) ( 2, 7) ( 2,11) 2 win (-2,-1) (-2, 3) ( 0, 5) ( 2, 7) ( 4, 9) 2 win (-2,-1) ( 0, 1) ( 3, 1) ( 6, 1) ( 9, 1) 2 win (-2,-1) ( 0, 1) ( 3, 1) ( 6, 1) ( 6, 5) ( 9, 5) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 6, 1) ( 6, 5) ( 6, 9) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 6, 1) ( 6, 5) ( 8, 7) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 6, 1) ( 8, 3) (11, 3) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 6, 1) ( 8, 3) ( 8, 7) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 6, 1) ( 8, 3) (10, 5) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 3, 5) ( 6, 5) ( 9, 5) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 3, 5) ( 6, 5) ( 6, 9) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 3, 5) ( 6, 5) ( 8, 7) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 3, 5) ( 3, 9) 2 win (-2,-1) ( 0, 1) ( 3, 1) ( 3, 5) ( 5, 7) ( 8, 7) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 3, 5) ( 5, 7) ( 5,11) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 3, 5) ( 5, 7) ( 7, 9) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 5, 3) ( 8, 3) (11, 3) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 5, 3) ( 8, 3) ( 8, 7) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 5, 3) ( 8, 3) (10, 5) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 5, 3) ( 5, 7) ( 8, 7) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 5, 3) ( 5, 7) ( 5,11) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 5, 3) ( 5, 7) ( 7, 9) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 5, 3) ( 7, 5) (10, 5) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 5, 3) ( 7, 5) ( 7, 9) 1 win (-2,-1) ( 0, 1) ( 3, 1) ( 5, 3) ( 7, 5) ( 9, 7) 1 win (-2,-1) ( 0, 1) ( 0, 5) ( 3, 5) ( 6, 5) ( 9, 5) 1 win (-2,-1) ( 0, 1) ( 0, 5) ( 3, 5) ( 6, 5) ( 6, 9) 1 win (-2,-1) ( 0, 1) ( 0, 5) ( 3, 5) ( 6, 5) ( 8, 7) 1 win (-2,-1) ( 0, 1) ( 0, 5) ( 3, 5) ( 3, 9) 2 win (-2,-1) ( 0, 1) ( 0, 5) ( 3, 5) ( 5, 7) ( 8, 7) 1 win (-2,-1) ( 0, 1) ( 0, 5) ( 3, 5) ( 5, 7) ( 5,11) 1 win (-2,-1) ( 0, 1) ( 0, 5) ( 3, 5) ( 5, 7) ( 7, 9) 1 win (-2,-1) ( 0, 1) ( 0, 5) ( 0, 9) ( 3, 9) 2 win (-2,-1) ( 0, 1) ( 0, 5) ( 0, 9) ( 0,13) 2 win (-2,-1) ( 0, 1) ( 0, 5) ( 0, 9) ( 2,11) 2 win (-2,-1) ( 0, 1) ( 0, 5) ( 2, 7) ( 5, 7) ( 8, 7) 1 win (-2,-1) ( 0, 1) ( 0, 5) ( 2, 7) ( 5, 7) ( 5,11) 1 win (-2,-1) ( 0, 1) ( 0, 5) ( 2, 7) ( 5, 7) ( 7, 9) 1 win (-2,-1) ( 0, 1) ( 0, 5) ( 2, 7) ( 2,11) 2 win (-2,-1) ( 0, 1) ( 0, 5) ( 2, 7) ( 4, 9) 2 win (-2,-1) ( 0, 1) ( 2, 3) ( 5, 3) ( 8, 3) (11, 3) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 5, 3) ( 8, 3) ( 8, 7) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 5, 3) ( 8, 3) (10, 5) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 5, 3) ( 5, 7) ( 8, 7) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 5, 3) ( 5, 7) ( 5,11) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 5, 3) ( 5, 7) ( 7, 9) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 5, 3) ( 7, 5) (10, 5) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 5, 3) ( 7, 5) ( 7, 9) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 5, 3) ( 7, 5) ( 9, 7) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 2, 7) ( 5, 7) ( 8, 7) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 2, 7) ( 5, 7) ( 5,11) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 2, 7) ( 5, 7) ( 7, 9) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 2, 7) ( 2,11) 2 win (-2,-1) ( 0, 1) ( 2, 3) ( 2, 7) ( 4, 9) 2 win (-2,-1) ( 0, 1) ( 2, 3) ( 4, 5) ( 7, 5) (10, 5) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 4, 5) ( 7, 5) ( 7, 9) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 4, 5) ( 7, 5) ( 9, 7) 1 win (-2,-1) ( 0, 1) ( 2, 3) ( 4, 5) ( 4, 9) 2 win (-2,-1) ( 0, 1) ( 2, 3) ( 4, 5) ( 6, 7) 2 win
Легко заметить, что в этом варианте игры при правильных действиях всегда побеждает первый игрок.
Теперь посмотрим на задачу C3 из рекомендуемых вариантов ЕГЭ 2009 года:
Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку с координатами (x,y+4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
В нашей программе придётся изменить только положение перед первым ходом x0, y0, массив возможных ходов hod и условие завершения игры в функции endofgame (теперь расстояние от начала координат должно быть не менее 13, а не 9).
Изменения выделены красным.
Изменённая таким образом программа легко строит дерево игры этой задачи:
uses crt;
const MAXLEVEL=100;
MAXSTEPS=3;
x0=5;
y0=2;
hod:array [1..MAXSTEPS,1..2] of integer = (
(3,0), (0,3), (0,4)
);
var game:array [1..MAXLEVEL,1..2] of integer;
f:text; fname:string;
function dist(x,y:integer):real;
begin
dist:=sqrt(sqr(x)+sqr(y));
end;
function endofgame (l:integer):boolean;
begin
endofgame:=dist(game[l,1],game[l,2])>13;
end;
procedure print(l:integer);
var i:integer;
begin
writeln (f);
for i:=1 to l do write (f,'(',game[i,1]:2,',',game[i,2]:2,') ');
if l mod 2 = 0 then write (f,'1 win')
else write (f,'2 win');
end;
procedure step (x,y,l:integer);
{x,y - координаты точки, l - уровень просмотра}
var i:integer;
begin
game[l,1]:=x;
game[l,2]:=y;
if endofgame(l) then print(l)
else for i:=1 to MAXSTEPS do step (x+hod[i,1],y+hod[i,2],l+1);
end;
begin
clrscr;
assign(f,'c3.txt');{con}
rewrite(f);
step(x0,y0,1);
close (f);
end.
Наконец, для построения деревьев игры задач 2006-2008 гг. (про "кучки камней") нам придётся лишь немного поменять логику программы. Дело в том, что там было по 4 возможных хода, 2 из которых приводили к увеличению количества камней во сколько-то раз, а другие два - к увеличению его на заданное число.
Поэтому в массиве hod две первых строки будут содержать числа, на которые нужно умножить величины x,y в методе step, а две последних строки - величины, которые нужно прибавить к каждой из куч. Изменится и критерий выхода из игры (см. метод endofgame).
Вот задача 2008 года:
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй - 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 17 камней. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
А вот изменённый листинг программы:
uses crt;
const MAXLEVEL=100;
MAXSTEPS=4;
x0=1;
y0=2;
hod:array [1..MAXSTEPS,1..2] of integer = (
(3,1), (1,3), (2,0), (0,2)
);
var game:array [1..MAXLEVEL,1..2] of integer;
f:text; fname:string;
function endofgame (l:integer):boolean;
begin
endofgame:=game[l,1]+game[l,2]>16;
end;
procedure print(l:integer);
var i:integer;
begin
writeln (f);
for i:=1 to l do write (f,'(',game[i,1]:2,',',game[i,2]:2,') ');
if l mod 2 = 0 then write (f,'1 win')
else write (f,'2 win');
end;
procedure step (x,y,l:integer);
{x,y - координаты точки, l - уровень просмотра}
var i:integer;
begin
game[l,1]:=x;
game[l,2]:=y;
if endofgame(l) then print(l)
else for i:=1 to MAXSTEPS do
if i<3 then step (x*hod[i,1],y*hod[i,2],l+1)
else step (x+hod[i,1],y+hod[i,2],l+1);
end;
begin
clrscr;
assign(f,'c3.txt');{con}
rewrite(f);
step(x0,y0,1);
close (f);
end.
 гостевая; E-mail
|
