В каждой ситуации возможно 4 хода: увеличить на два число камней в 1 кучке, увеличить на два число камней во 2 кучке, утроить число камней в 1 кучке, утроить число камней во 2 кучке. Составим дерево игры.
Получившиеся после хода количества камней в кучках выписываем в порядке возрастания. Если есть выигрывающий ход, другие ходы не пишем. Нечетные ходы выполнят первый игрок, четные – второй.
1ход 2ход 3ход 4ход
(3,4)-+(4,5)-+(5,6)-+(6,7)—-(6,21)
| | +(5,8)--(5,24)
| | +(6,15)-(6,45)
| | +(5,18)-(5,54)
| +(4,7)--(4,21)
| +(5,12)-(5,36)
| +(4,15)-(4,45)
+(3,6)-+(5,6)-+(6,7)--(6,21)
| | +(5,8)--(5,24)
| | +(6,15)-(6,45)
| | +(5,18)-(5,54)
| +(3,8)--(3,24)
| +(6,9)--(6,27)
| +(3,18)-(3,54)
+(4,9)—-(4,27)
+(3,12)-(3,36)
Анализируя дерево игры, делаем вывод, что при правильной игре выигрывает второй игрок.
При увеличении на 2 количество камней в одной кучке чему надо увеличить на 2 количество камней в другой кучке [(3,4)-(4,5)-(5,6) или (3,4)-(3,6)-(5,6)], и на любой ответ первого игрока утраивать камни в кучке с максимальным числом камней.
Если первый игрок выполнит утроение камней, то проиграет уже на следующем ходу.
Следует отметить, что составление дерева игры – очень трудоемкая операция.
Вычисление значений функций
Под конец занятия, рассмотрим важную в прикладном значении тему – «Вычисление значений функций»
В языках программирования имеется достаточно встроенных функций, чтобы составлять различные арифметические выражения. Для удобства использования, вычисление функций можно обособить. Посмотрим, как оформляются и используются функции пользователя на языках «бейсик» и «паскаль».
В языке бейсик, при объявлении функции, начальные буквы «fn» обязательны, за этими буквами стоит буква, отличающая одну функцию от другой.
В языке паскаль, имена функций полностью определяет программист.
basic
10 def fna(x)=x*x-5*x+6
...
50 print x, fna(x)
pascal
function f(x:real):real begin f:=x*x-5*x+6; end;
var x:real;
Begin x:=3,14; writeln(x:8:2,f(x):12:6); End.
Получение таблицы значений функции, при аргументе, изменяющем значение от a до b с шагом h, может быть представлено линейным алгоритмом.
Повторение одинаковых шагов, которые составят тело, есть алгоритмическая конструкция – цикл.
В языке бейсик, задача может быть решена обычной командой цикла со счетчиком.
Более строгий паскаль не может иметь счетчиком действительное значение. Приходится использовать цикл «пока». Во избежание неточностей, связанных с ошибкой округления, цикл следует выполнять не при x<=b, а при x строго меньшем некоторого числа, которое немного больше b. Иначе, если при округлении шага h последняя цифра увеличивается, возникнет ситуация, когда x=x+h математического подсчета окажется не больше b, а вычисленное компьютером – больше b. Требуемое, согласно математике, f(b) вычисляться не будет.
basic
pascal
for x=a to b+1e-6 step h
print x, fna(x)
next x
x:=a;
while x<b+1e-6 do
begin
writeln(x:8:2,f(x):12:6);
x:=x+h
end;
Например, требуется найти таблицу значений некоторой функции на отрезке [0,2] с шагом 2/3. То есть в точках 0, 2/3, 4/3, 2.
x=0
print x, fnf(x)
x=x+2/3 ‘ x=0.6666666667
print x, fnf(x)
x=x+2/3 ‘ x=1.3333333334
print x, fnf(x)
x=x+2/3 ‘ x=2.0000000001 > 2
Фактически компьютер сосчитает значения только в точках 0, 2/3 и 4/3. После третьего присваивания x=x+h аргумент превысит граничное значение b=2.
Получение таблицы значений функции – простейший циклический алгоритм. В него часто следует включать еще и ветвление – некоторые функции определены не всюду.
basic
pascal
for x=a to b+1e-6 step h
if /x входит в ОДЗ/
then print x, fna(x)
else print x, “не опр.”
endif
next x
x:=a;
while x<b+1e-6 do
begin
if /x входит в ОДЗ/
then writeln(x:8:2,f(x):12:6)
else writeln(x:8:2,’не опр.’);
x:=x+h
end;
Принадлежность аргумента области определения определяется как система неравенств. При этом, для действительных чисел нежелательно использовать нестрогие неравенства. Сравнивайте не с числом, а с небольшим интервалом, содержащим это число. Подобный прием позволяет избежать ошибок округления. Как появляются эти ошибки было показано.
Вообще, «если 5 разделить на 6, а то что получится умножить на 6, то 5 не получится»!
Завершение
По окончании нашего урока, вы должны знать ответы на вопросы:
Как выполнять задания ЕГ, в которых исходные данные формируются по некоторым правилам?
Как выполнять задания ЕГ о работе различных исполнителей?
Как выполнять задания ЕГ про различные игры?
Что такое дерево игры?
Как получить таблицу значений любой функции в любом интервале с любым шагом?
