Разбор задачи C1 (демо ЕГЭ 2005)
Программист написал программу, в которой требовалось определить все такие поля (i,j), для которых P(i,j) = V(i,j), и выдать на экран соответствующие значения i,j (текст программы приведен ниже).
1) Выдаст ли программа, написанная программистом, поле, для которого
i=4, j=5 ?
2) Указать все из перечисленных ниже полей, которые удовлетворяют постановке задачи, т.е. для таких полей должно быть выполнено P(i,j) = V(i,j)
(i=1, j=8), (i=2, j=8), (i=1, j=7), (i=5, j=5), (i=8, j=6)
3) Видно, что программист допустил ошибку в программе. Укажите, какую доработку программы нужно провести, чтобы она соответствовала постановке задачи (такая доработка может быть проведена неединственным образом – годится любой правильный вариант доработки)
| Программа на языке Паскаль | Программа на языке Бейсик |
|---|---|
|
var i,j: integer; begin writeln('искомые поля'); for j:=5 to 8 do for i:=1 to 8 do begin if (i=9-j) or (i=j) then writeln('i=',i, 'j=',j); end; end. |
PRINT "Искомые поля" FOR J=5 TO 8 FOR I=1 TO 8 IF (I=9-J) OR (I=J) THEN PRINT "I="; I PRINT "J="; J ENDIF NEXT I NEXT J END |
| Программа на Алгоритмическом | Программа на языке СИ |
| алг нач цел i,j вывод 'искомые поля' нц для j от 5 до 8 нц для i от 1 до 8 если i=9-j или i=j то вывод 'i=',i,'j=',j все кц кц кон |
#include <stdio.h> void main() { int i,j; printf("искомые поля"); for(j=4;j<8;j++) for(i=0;i<8;i++){ if( (i==9-j)||(i==j) ) printf("i=%d j=%d",i+1,j+1); } } |
часть 1)
Программа выдаст поле (4,5), т.к. выполнится условие i=9-j.
i=4, j=5. Подставляем эти значения в условие: 4=9-5 => 4=4.
часть 2)
Шахматное поле выглядит так:
Черным и белым кружками обозначены черный и белый король, соответственно.
Чтобы попасть в нужное поле (iкон,jкон) за минимальное число ходов короли должны двигаться следующим образом:
- если их певоначальная позиция (i0,j0) содержит вертикаль или диагональ, равную конечной, т.е. i0=iкон или j0=jкон, то дальше они должны двигаться только:
- по горизонтали (при i0=iкон), увеличивая j0 на 1 при j0<jкон (черный король) и уменьшая j0 на 1 при j0>jкон (белый король), до тех пор пока не достигнут jкон;
- вверх по вертикали (при j0=jкон), увеличивая i0 на 1, до тех пор пока не достигнут iкон.
- если их певоначальная позиция (i0,j0) не содержит вертикаль или диагональ, равную конечной, то короли должны двигаться по диагонали вверх, пока не попадут на конечную вертикаль (iтек=iкон) или горизонталь (jтек=jкон). (iтек,jтек) - текущее положение короля. Далее короли должны двигаться как описано в пункте выше.
Проанализируем движение королей. Искомое конечное поле - (2,8)
Рассмотрим траекторию движения черного короля. На рисунке выше она обозначена розовыми стрелками.
Первоначальная позиция черного короля: (1,1). 1≠2, 1≠8, поэтому король идет по диагонали вверх, попадая в поле - (2,2) (1 ход).
Текущая позиция (2,2) содержит вертикаль искомого поля, т.к. iтек=iкон (2=2). Поэтому дальше король движется только вверх по вертикали, пока не дойдет до конечного поля, совершая при этом 6 ходов.
Количество ходов черного короля: P(2,8)=1+6=7 ходов.
Рассмотрим траекторию движения белого короля. На рисунке выше она обозначена синими стрелками.
Первоначальная позиция белого короля: (8,1). 8≠2, 1≠8, поэтому король идет по диагонали вверх, попадая в поле - (7,2) (1 ход).
7≠2, 2≠8 =>король идет по диагонали вверх, попадая в (6,3) (1 ход).
6≠2, 3≠8 =>король идет по диагонали вверх, попадая в (5,4) (1 ход).
5≠2, 4≠8 =>король идет по диагонали вверх, попадая в (4,5) (1 ход).
4≠2, 5≠8 =>король идет по диагонали вверх, попадая в (3,6) (1 ход).
3≠2, 6≠8 =>король идет по диагонали вверх, попадая в (2,7) (1 ход).
Всего 6 ходов по диагонали вверх.
Текущая позиция (2,7) содержит вертикаль искомого поля, т.к. iтек=iкон (2=2). Поэтому дальше король движется вверх по вертикали (1 ход), попадая в позицию (2,8).
Количество ходов белого короля: V(2,8)=6+1=7 ходов.
P(2,8)=V(2,8) =>поле (i=2,j=8) удовлетворяет постановке задачи.
Кратко рассмотрим остальные поля.
Поле (i=1,j=8)
| Фигура | Позиция при ходе: | |||||||
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| черный король | (1,1) | (1,2) | (1,3) | (1,4) | (1,5) | (1,6) | (1,7) | (1,8) |
| белый король | (8,1) | (7,2) | (6,3) | (5,4) | (4,5) | (3,6) | (2,7) | (1,8) |
P(1,8)=V(1,8)=7 =>поле (i=1,j=8) удовлетворяет постановке задачи.
Поле (i=1, j=7)
| Фигура |
Позиция при ходе: |
|||||||
|---|---|---|---|---|---|---|---|---|
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
| черный король |
(1,1) |
(1,2) |
(1,3) |
(1,4) |
(1,5) |
(1,6) |
(1,7) |
- |
| белый король |
(8,1) |
(7,2) |
(6,3) |
(5,4) |
(4,5) |
(3,6) |
(2,7) |
(1,7) |
P(1,7)=6 ходов, V(1,7)=7 ходов =>P(1,7)≠V(1,7) =>поле (1,7) не удовлетворяет постановке задачи.
Поле (i=5, j=5)
| Фигура |
Позиция при ходе: |
||||
|---|---|---|---|---|---|
| 0 |
1 |
2 |
3 |
4 |
|
| черный король |
(1,1) |
(2,2) |
(3,3) |
(4,4) |
(5,5) |
| белый король |
(8,1) |
(7,2) |
(6,3) |
(5,4) |
(5,5) |
P(5,5)=V(5,5)=4 =>поле (i=5,j=5) удовлетворяет постановке задачи.
Поле (i=8, j=6)
| Фигура |
Позиция при ходе: |
|||||||
|---|---|---|---|---|---|---|---|---|
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
| черный король |
(1,1) |
(2,2) |
(3,3) |
(4,4) |
(5,5) |
(6,6) |
(7,6) |
(8,6) |
| белый король |
(8,1) |
(8,2) |
(8,3) |
(8,4) |
(8,5) |
(8,6) |
- |
- |
P(8,6)=7 ходов, V(8,6)=5 ходов =>P(8,6)≠V(8,6) =>поле (8,6) не удовлетворяет постановке задачи.
Получили, что постановке задачи удовлетворяют поля: (i=1, j=8), (i=2, j=8), (i=5, j=5).
часть 3)
Доработка для корректной работы программы на языках программирования:
| Паскаль | Бейсик |
|---|---|
| вместо if (i=9-j) or (i=j) написать if (i>=9-j) AND (i<=j) |
вместо IF (I=9-J) OR (I=J) написать IF (I>=9-J) AND (I<=J) |
| Алгоритмический | Си |
| вместо если i=9-j или i=j написать если i>=9-j и i<=j |
вместо if( (i==9-j)||(i==j) ) написать if( (i>=9-j)&&(i<=j) ) |