Методические рекомендации по подготовке к единому государственному экзамену по информатике в Белгородской области (стр. 5 из 10)
Решение (развернутый ответ):
Для решения задачи составим таблицу (дерево развития игры при разных продолжениях).
В колонке 0 показано начальное состояние игры (вершина дерева игры), в колонке 1 показаны 4 возможных состояния игры после 1-го хода 1-го игрока, в колонке 2 показано 16 возможных состояний игры после 1-го хода 2-го игрока, далее дерево игры не ведется, а проводится анализ уже рассчитанных состояний игры.
Если 1-й игрок сделает свой первый ход 2,3,4 —>4,3,4, то 2-й игрок при правильной игре сделает ход 4,3,4 —>4,6,4, что приводит к проигрышу 1-го игрока (т.к. из состояния (4,6,4) 1-й игрок может своим ходом перевести игру в одно из четырех состояний — (8,6,4), (4,12,4), (4,6,8), (6,8,6), и для любого из этих состояний найдется ход 2-го игрока, дающий ему выигрыш, например, по критерию S>25 ).
Если 1-й игрок сделает свой первый ход 2,3,4 —>2,6,4, то 2-й игрок при правильной игре сделает ход 2,6,4 —> 4,6,4, что, как мы только что видели, приводит к выигрышу 2-го игрока.
Если 1-й игрок сделает свой первый ход 2,3,4 —>2,3,8, то его проигрыш очевиден, так как 2-й игрок, как указано в таблице, добьется выигрывающего состояния игры 2,3,16.
Наконец, если 1-й игрок сделает свой первый ход 2,3,4 —> 4,5,6, то он выигрывает игру, т.к. на любой из четырех возможных ответов 2-го игрока (см. табл.) есть выигрывающий ход 1-го игрока.
Таким образом, при правильной игре выигрывает 1-й игрок (при этом его первый ход должен быть 2,3,4 —>4,5,6)
| Начальное состояние | 1-й ход первого игрока | 1-й ход второго игрока | 2-й ход первого игрока |
| 2,3,4 | 4,3,4 | 4,6,4 Приводит к выигрышу второго игрока при любом втором ходе первого игрока | |
| 2,6,4 | 4,6,4 Приводит к выигрышу второго игрока при любом втором ходе первого игрока | ||
| 2,3,8 | 2,3,16 Выигрыш второго игрока | ||
| 4,5,6 | 8,5,6 | 16,5,6 Выигрыш первого игрока | |
| 4,10,6 | 4,20,6 Выигрыш первого игрока | ||
| 4,5,12 | 4,5,24 Выигрыш первого игрока | ||
| 6,7,8 | 6,7,16 Выигрыш первого игрока |
При решений заданий на исполнение алгоритма в среде формального исполнителя, прежде всего — требуется уяснить систему команд исполнителя алгоритма, т.е. как записывается каждая команда, что означают ее параметры (если они есть) и каков должен быть результат ее выполнения.
Пример:
Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:
Вперед n, вызывающая передвижение Черепашки на п шагов в направлении движения.
Направо т, вызывающая изменение направления движения на т градусов по часовой стрелке. 0 
т 180.
(Вместо п и т должны стоять целые числа).
Запись:
Повтори 5 [Команда1 Команда2] означает, что последовательность команд в квадратных скобках повторится 5 раз.
Какое число необходимо записать вместо п в следующем алгоритме:
Повтори 6 [Вперед 40 Направо п], чтобы на экране появился правильный пятиугольник.
Решение:
Сумма внутренних углов правильного пятиугольника вычисляется по формуле (р-2)х180/р, где р =5. Поэтому величина одного внутреннего угла будет равна (5 - 2) х 180/5 = 108°. А угол поворота Черепашки в вершине пятиугольника будет равен углу, смежному с внутренним углом, т.е. 180-108=72°.
Черепашка прочертит на экране 6 отрезков, но последний отрезок полностью совпадет с первым, так как после пятого выполнения цикла Черепашка полностью обернется вокруг своей оси (72x5 = 360°) и окажется в той же точке, что и изначально. Так что на экране появится правильный пятиугольник.
Ответ: 72.
Для решения задач на исполнение алгоритма, записанного в виде блок-схемы или программы на алгоритмическом языке, нужно знать и уметь использовать основные алгоритмические конструкции: следование, ветвление, цикл. Для непосредственного исполнения алгоритма рекомендуется вести таблицу переменных, в которой отображается изменение их значений после каждого шага.
Пример:
Определите значение переменной т после выполнения фрагмента алгоритма:
Примечание: знаком :=обозначена операция присваивания.
1) 1 2) 2 3) 3 4) 33
Решение
Способ 1
Составим таблицу переменных, добавив в нее для удобства результаты вычисления логических выражений.
| N шага | Значение т | Значе- ние п | т =п | т>п |
| 0 | 81 | 48 | ||
| 1 | 81 | 48 | 81 = 48 — нет (выполняем тело цикла) | |
| 2 | 81 | 48 | 81>48 - да | |
| 3 | 33 | 48 | ||
| 4 | 33 | 48 | 33= 48 — нет (выполняем тело цикла) | |
| 5 | 33 | 48 | 33>48-нет | |
| 6 | 33 | 15 | ||
| 7 | 33 | 15 | 33=15 — нет (выполняем тело цикла) | i |
| 8 | 33 | 15 | 33>15 - да | |
| 9 | 18 | 15 | 18=15 — нет (выполняем тело цикла) | |
| 10 | 18 | 15 | 18>15 - да | |
| 11 | 3 | 15 | ||
| 12 | 3 | 15 | 3 = 15 — нет (выполняем тело цикла) | |
| 13 | 3 | 15 | 3 > 15 - нет | |
| 14 | 3 | 12 | ||
| 15 | 3 | 12 | 3 = 12 — нет (выполняем тело цикла) | |
| 16 | 3 | 12 | 3>12 - нет | |
| 17 | 3 | 9 | ||
| 18 | 3 | 9 | 3 = 9 — нет (выполняем тело цикла) | |
| 19 | 3 | 9 | 3 > 9 - нет | |
| 20 | 3 | 6 | ||
| 21 | 3 | 6 | 3 = 6 — нет (выполняем тело цикла) | |
| 22 | 3 | 6 | 3 > 6 - нет | |
| 23 | 3 | 3 | ||
| 24 | 3 | 3 | 3 = 3 — да (выход из цикла и завершение алгоритма) |
Ответ: 3.
Способ 2
Внимательно проанализировав блок-схему, можно сделать вывод, что она реализует известный алгоритм Евклида нахождения наибольшего общего делителя двух чисел, который для 81 и 48 равен трем. (81 = 34, 48 =3x16.)
Ответ: 3.
При выполнении заданий на выполнение алгоритмов, записанных на языках программирования, следует учесть, что приведенные в таблице тексты программ на разных языках эквивалентны, поэтому учащийся должен выбрать тот язык, который ему наиболее знаком и далее работать только с ним, не обращая внимания на остальные столбцы таблицы.
Пример:
Определите значение целочисленных переменных а и b после выполнения фрагмента программы:
| Бейсик | Паскаль | Алгоритмический |
| а=2468 | а:=2468; | а:=2468 |
| b= (a MOD 1000)*10 | b:=(a mod 1000)ПО; | b:=mod(a, 1000)*10 |
| а=а\1000 + 6 | а:=а div 1000 + 6; | a:=div(a, 1000) +b |
| '\ и MOD — опера- | {div и mod — опера- | |div и mod — функ- |
| ции, вычисляющие | ции, вычисляющие | ции, вычисляющие |
| результат деления | результат деления | результат деления |
| нацело первого ар- | нацело первого ар- | нацело первого ар- |
| гумента на второй и | гумента на второй и | гумента на второй и |
| остаток от деления | остаток от деления | остаток от деления |
| соответственно | соответственно} | соответственно |
1)a =22, b=20