Рассмотрим задачу задания С3 (игровая стратегия):
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче или добавляет 3 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в одной из кучек становится не менее 24. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Для решения задачи рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейки записаны пары чисел, разделенные запятой. Эти числа соответствуют количеству камней на каждом этапе игры, в первой и второй кучках соответственно.
|
1- ход |
2 — ход |
3 — ход |
Пояснения |
||
|
Стартовая позиция |
!-й игрок(все варианты хода) |
2-й игрок(выигрышный ход) |
!-й игрок(все варианты хода) |
2й игрок(один из вариантов) |
|
|
3, 2 |
3, 5 |
6, 5 |
18, 5 |
54,5 |
Второй игрок выигрывает на втором ходу, после любого ответа первого игрока — например, утроив число камней в самой большой кучке |
|
9, 5 |
27,5 |
||||
|
6, 5 |
6, 45 |
||||
|
6, 8 |
6, 24 |
||||
|
6, 2 |
6, 5 |
Те же варианты ходов |
|||
|
3, 6 |
6, 6 |
18, 6 |
54,6 |
Второй игрок выигрывает на втором ходу, после любого ответа первого игрока, например, утроив число камней в самой большой куче. |
|
|
9,6 |
27,6 |
||||
|
9, 2 |
27, 2 |
Второй игрок выигрывает ответным ходом. |
|||
Данная задача имеет четко выраженный алгоритм решения, поэтому можно написать программу, которая будет выдавать результаты решения данной задачи.
Составим алгоритм программы данной задачи в общем виде:
Программа на Pascalк данной задаче (работаем в среде Free Pascal):
program c3_12;
uses crt; {используем библиотеку CRT}
label bye,bye1,bye2; {метки}
var f:text; {текстовый файл f}
a,b,c,d,e,n1,k1,s5,s6,s7,s8,p1,p2,i,i3,j,sp1,sp2,sp3,sp4:integer; st:string;
am2:array[1..2 ,1..16] of integer; {двумерный массив - на 2-ом ходу}
am3:array[1..4,1..64] of integer; {двумерный массив - на 3-ходу}
procedure sum(n,k,i1,i2,i3,j1,j2,j3,d1:integer;var s1,s2,s3,s4,p:integer);{процедура определения выигрыш.позиции на 2-ходу}
begin
s1:=i2+j1;
if s1>= d1 then begin writeln(f,' Выиграл ',n,' игрок на ',k,' ходу: ',i2,',',j1); p:=p+1;end;
s2:=i1+j2;
if s2>= d1 then begin writeln(f,' Выиграл ',n,' игрок на ',k,' ходу: ',i1,',',j2); p:=p+1;end;
s3:=i3+j1;
if s3>= d1 then begin writeln(f,' Выиграл ',n,' игрок на ',k,' ходу: ',i3,',',j1); p:=p+1;end;
s4:=i1+j3;
if s4>= d1 then begin writeln(f,' Выиграл ',n,' игрок на ',k,' ходу: ',i1,',',j3); p:=p+1;end;
end;
procedure pr2(a1,a2,a3,b1,b2,b3:integer); {формирование всех возможных чисел на 2 ходу}
begin
writeln(f,' (',a1,',',b1,')',a2,',',b1);
writeln(f,' ',a1,',',b2);
writeln(f,' ',a3,',',b1);
writeln(f,' ',a1,',',b3);
end;
begin {начало основной программы}
clrscr; {очистка экрана}
assign(f,'d:\e3.txt');
{$I-} {это директива компилятору, а не комментарий}
rewrite(f); {откроем файл для записи}
{$I+}
if IOResult <> 0 then {проверяем наличия файла на диске}
begin
writeln('Не найден файл');
goto bye;
end;
write(f,'Ст.поз.');
write(f,' 1 ход:1 игрок');
write(f,' 2 ход:2 игрок');
write(f,' 3 ход:1 игрок');
writeln(f,' 4 ход:2 игрок');
write('Сколько камней в 1-й кучке? ');
readln(a);
write('Сколько камней в 2-й кучке? ');
readln(b);
write('Во сколько раз увеличится число камней в кучке? ');
readln(c);
write('Сколько добавить камней в кучку? ');
readln(d);
write('Сколько камней должно стать в обеих кучках? ');
readln(e);
writeln(f);
n1:=1;k1:=1; {n1- номер игрока, k1 - номер хода}
write(f,' ',a,',',b); {выводим в файл все возможные числа на 1 ходу - 4 варианта}
writeln(f,' ',a*c,',',b);
writeln(f,' ',a,',',b*c);
writeln(f,' ',a+d,',',b);
writeln(f,' ',a,',',b+d);
sum(n1,k1,a,a*c,a+d,b,b*c,b+d,e,s5,s6,s7,s8,p1); {вызываем прцедуру sum и проверяем возможность выигрышных комбинаций на 1 ходу}
if p1>0 then goto bye2;
n1:=n1+1;k1:=2;p2:=0; {начинается 2 ход, ходит 2 игрок}
pr2(a*c,a*c*c,a*c+d,b,b*c,b+d); {берем 1 вариант с 1-го хода,вызываем процедуру pr2 и получаем 4 возможных варианта}
sum(n1,k1,a*c,a*c*c,a*c+d,b,b*c,b+d,e,s5,s6,s7,s8,p1);{процедурой sum проверяем все 4 варианта на выигрышную комбинацию}
am2[1,1]:=a*c*c;am2[2,1]:=b; {запоминаем все 4 варианта в массиве am2}
am2[1,2]:=a*c;am2[2,2]:=b*c;am2[1,3]:=a*c+d;
am2[2,3]:=b;
am2[1,4]:=a*c;am2[2,4]:=b+d;
if p1>0 then p2:=p2+1; {запоминаем если была выигрышная комбинация}
pr2(a,a*c,a+d,b*c,b*c*c,b*c+d); {берем 2 вариант с 1-го хода,вызываем процедуру pr2 и получаем 4 возможных варианта}
sum(n1,k1,a,a*c,a+d,b*c,b*c*c,b*c+d,e,s5,s6,s7,s8,p1);{процедурой sum проверяем все 4 варианта на выигрышную комбинацию}
am2[1,5]:=a*c;am2[2,5]:=b*c; {запоминаем все 4 варианта в массиве am2}
am2[1,6]:=a;am2[2,6]:=b*c*c;am2[1,7]:=a+d;
am2[2,7]:=b*c;
am2[1,8]:=a;am2[2,8]:=b*c+d;
if p1>0 then p2:=p2+1; {запоминаем если была выигрышная комбинация}
pr2(a+d,(a+d)*c,a+d+d,b,b*c,b+d);
sum(n1,k1,a+d,(a+d)*c,a+d+d,b,b*c,b+d,e,s5,s6,s7,s8,p1);
am2[1,9]:=(a+d)*c;am2[2,9]:=b;
am2[1,10]:=a+d;am2[2,10]:=b*c;am2[1,11]:=a+d+d;
am2[2,11]:=b;
am2[1,12]:=a+d;am2[2,12]:=b+d;
if p1>0 then p2:=p2+1;
pr2(a,a*c,a+d,b+d,(b+d)*c,b+d+d);
sum(n1,k1,a,a*c,a+d,b+d,(b+d)*c,b+d+d,e,s5,s6,s7,s8,p1);
am2[1,13]:=a*c;am2[2,13]:=b+d;
am2[1,14]:=a;am2[2,14]:=(b+d)*c;am2[1,15]:=a+d;
am2[2,15]:=b+d;
am2[1,16]:=a;
am2[2,16]:=b+d+d;
if p2>0 then goto bye2;
n1:=1;k1:=3;p2:=0; {начинается 3-ход, ходит 1 игрок}
i:=1;i3:=1;
while (i<=16) do begin {берем очередной вариант из массива am2, строим 4 варианта и проверяем на выигрыш - все это в цикле}
writeln(f,' (',am2[1,i],',',am2[2,i],')',am2[1,i]*c,',',am2[2,i]);
sp1:=am2[1,i]*c+am2[2,i];
if sp1>=e then begin
writeln(f,' Выиграл ',n1,' игрок на ',k1,' ходу: ',am2[1,i]*c,',',am2[2,i]); p2:=p2+1;end;
am3[1,i3]:=am2[1,i]*c;am3[2,i3]:=am2[2,i]; {из новых вариантов формируем массив am3 - для расчета на 4 шаге}
writeln(f,' ',am2[1,i],',',am2[2,i]*c);
sp2:=am2[1,i]+am2[2,i]*c;
if sp2>=e then begin
writeln(f,' Выиграл ',n1,' игрок на ',k1,' ходу: ',am2[1,i],',',am2[2,i]*c); p2:=p2+1;end;
am3[1,i3+1]:=am2[1,i];am3[2,i3+1]:=am2[2,i]*c;
writeln(f,' ',am2[1,i]+d,',',am2[2,i]);
sp3:=am2[1,i]+d+am2[2,i];
if sp3>=e then begin
writeln(f,' Выиграл ',n1,' игрок на ',k1,' ходу: ',am2[1,i]+d,',',am2[2,i]); p2:=p2+1;end;
am3[1,i3+2]:=am2[1,i]+d;am3[2,i3+2]:=am2[2,i];
writeln(f,' ',am2[1,i],',',am2[2,i]+d);
sp4:=am2[1,i]+am2[2,i]+d;
if sp4>=e then begin
writeln(f,' Выиграл ',n1,' игрок на ',k1,' ходу: ',am2[1,i],',',am2[2,i]+d); p2:=p2+1;end;
am3[1,i3+3]:=am2[1,i];am3[2,i3+3]:=am2[2,i]+d;
i:=i+1;i3:=i3+4;
end;
if p2>0 then goto bye2;
n1:=2;k1:=4;p2:=0;i:=1; {начинается 4 ход, ходит 2 игрок}
while (i<=64) do begin {берем очередной вариант из массива am3 и проверяем на выигрыш - все это в цикле}
writeln(f,' (',am3[1,i],',',am3[2,i],')',am3[1,i]*c,',',am3[2,i]);
sp1:=am3[1,i]*c+am3[2,i];
if sp1>=e then begin
writeln(f,' Выиграл ',n1,' игрок на ',k1,' ходу: ',am3[1,i]*c,',',am3[2,i]); p2:=p2+1;end;
writeln(f,' ',am3[1,i],',',am3[2,i]*c);
sp2:=am3[1,i]+am3[2,i]*c;
if sp2>=e then begin
writeln(f,' Выиграл ',n1,' игрок на ',k1,' ходу: ',am3[1,i],',',am3[2,i]*c); p2:=p2+1;end;
writeln(f,' ',am3[1,i]+d,',',am3[2,i]);
sp3:=am3[1,i]+d+am3[2,i];
if sp3>=e then begin
writeln(f,' Выиграл ',n1,' игрок на ',k1,' ходу: ',am3[1,i]+d,',',am3[2,i]); p2:=p2+1;end;
writeln(f,' ',am3[1,i],',',am3[2,i]+d);
sp4:=am3[1,i]+am3[2,i]+d;
if sp4>=e then begin
writeln(f,' Выиграл ',n1,' игрок на ',k1,' ходу: ',am3[1,i],',',am3[2,i]+d); p2:=p2+1;end;
i:=i+1;
end;
bye2:
close(f); {закрыли текстовый файл}
assign(f,'d:\e3.txt');
reset(f); {открыли файл для чтения}
clrscr;
while not EOF (f) do begin readln(f,st); writeln(st); end; {печать файла на экран}
bye:
writeln;
writeln;
writeln('Для завершения работы нажмите < ENTER >');
readln;
end.
Запускаем данную программу и вводим данные. Но так как верхняя часть файла решений на экране не видна, то обращаемся к текстовому файлу:
С:\FPC\ e3.txt и читаем из файла (не забываем в «Блокноте» изменить шрифт — Terminal):
Литература:
1. Культин Н. Turbo Pascal в задачах и примерах. СПб.: БХВ — Петербург, 2008–256 с.
2. Якушкин П. А., Крылов С. С. ЕГЭ 2012. Информатика: сборник экзаменационных заданий– М.: Эксмо, 2011. — 188 с. — (ЕГЭ. Федеральный банк экзаменационных материалов).
3. Якушкин П. А., Крылов С.С ЕГЭ 2013. Информатика: сборник экзаменационных заданий — М.: Эксмо, 2012. — 185 с. — (ЕГЭ. Федеральный банк экзаменационных материалов).
