infoegehelp.ru

Успешно сдать ЕГЭ по информатике
  • Главная
  • Контакты
  • Карта сайта
  • Помощь сайту
Важно
  • Демо варианты ЕГЭ
  • Учим числа: 2 в степени
  • Биты, байты, килобайты
Решение задач
  • Задачи вне основных разделов информатики
Разделы информатики
  • 2011-12-18-14-33-54Системы счисления
  • 2011-12-18-16-45-20Алгебра логики
  • 2011-12-18-16-55-26Программирование
  • 2011-12-18-16-53-40Кодирование информации
  • 2011-12-18-16-56-19Компьютерные сети и Интернет
  • -excelЭлектронные таблицы (Excel)
  • 2011-12-18-16-57-50Базы данных
  • 2011-12-18-16-58-50Графы
  • 2011-12-18-17-00-15Файловая система
  • Устройство компьютера
  • ПО компьютера

Разбор задачи C1 (демо ЕГЭ 2005)

Рассматривается стандартная шахматная доска размером 8х8. Примем, что i – номер вертикали (может принимать значения от 1 до 8), j – номер горизонтали (также может принимать значения от 1 до 8). В левом нижнем углу, т.е. на поле i =1, j=1 (это поле черного цвета) стоит черный король. Напомним, что король может ходить на 1 клетку в любом направлении (по горизонтали, вертикали или диагонали). В правом нижнем углу, т.е. на поле i =8, j=1 (это поле белого цвета) стоит белый король. Введены обозначения: P(i,j) ‑ минимальное число ходов, за которое черный король может попасть на поле (i,j);   V(i,j)  ‑ минимальное число ходов, за которое белый король может попасть на поле (i,j).

Программист написал программу, в которой требовалось определить все такие поля (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)
Шахматное поле выглядит так:

Задача С1 ЕГЭ по информатике 2005 шахматное поле

Черным и белым кружками обозначены черный и белый король, соответственно.

Чтобы попасть в нужное поле (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тек) - текущее положение короля. Далее короли должны двигаться как описано в пункте выше.
Рассмотрим для примера движение королей в поле (i=2,j=8). Оно выделено зеленым цветом.

Задача С1 ЕГЭ по информатике 2005 движение к полю (2,8)

Проанализируем движение королей. Искомое конечное поле - (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) )

Перейти к другим задачам.

 

Rambler's Top100

© Латыпова В.А., 2012-2020. Все права защищены.
Копирование материалов сайта только с разрешения администрации сайта