Мастер-класс "Программирование на шахматной доске"

• 1 слайд

  МАСТЕР-КЛАСС
  «Программирование на шахматной доске»
  Подготовила Плотникова С.В., учитель информатики лицея-интерната «Эрудит»
  Методика решения олимпиадных задач по информатике
  

• 2 слайд

  занятия по информатике
  «Программирование на шахматной доске»
  
  Цель занятия: ознакомиться с технологией решения олимпиадных задач по информатике, основанных на работе с таблицами, выробатать навыки ориентирования в таблицах.
  
  
  Мастер-класс
  2
  

• 3 слайд

  АЛЕЕТ ОСЕНЬ ЦЕННЫМИ ДАРАМИ,
  ЕЩЕ ОДИН ЖИВОТВОРЯЩИЙ ДЕНЬ.
  ХЛЕБА ЧЕРВОНЯТ ЖЕЛТЫМИ ШНУРАМИ,
  ХРУСТАЛЬНЫХ ВОД ФИЛОСОФИЧНА СЕНЬ.
  
  ДВА ВЕЧЕРА ЦЕПЛЯВШИЕСЯ ШИШКИ
  АРТИСТ ПИСАЛ, БЕЗДОННА СИНЕВА.
  ДОРОЖНЫЙ ШЛАК ЦЕЛУЮТ ЧЕРВЯЧИШКИ,
  ЕЩЕ ПОКРЫТА ФЛОКСАМИ ТРАВА.
  Василий Николаевич Панов
  (1906 – 1973),
  шахматист, шахматный литератор
  

• 4 слайд

  Шахматная доска имеет размерность 8х8.
  Состоит из клеток 2х цветов.
  Координаты каждой клетки состоят из буквы и цифры.
  Горизонтальное расположение клетки определяется буквой от A до H, а вертикальное – цифрой от 1 до 8.
  Клетка с координатой А1 имеет черный цвет.
  
  
  ОСНОВЫ
  4
  

• 5 слайд

  РАЗМИНКА
  На шахматной доске на одной из клеток стоял конь. Он сделал несколько ходов и вернулся в ту же клетку. Какое количество ходов он сделал?
  5
  

• 6 слайд

  КЛЕТКИ
  Требуется по заданной координате шахматной доски определить цвет клетки.
  Входные данные:
  координата клетки на шахматной доске: всего два символа – буква и цифра (без пробелов).
  Выходные данные:
  «WHITE», если указанная клетка белого цвета.
  «BLACK», если указанная клетка черная.
  Примеры.
  
  6
  

• 7 слайд

  РЕШЕНИЕ
  7
  

• 8 слайд

  ШАХМАТНЫЙ
  КОНЬ
  Заданы две клетки доски. Требуется определить, возможно ли попасть из одной клетки в другую одним ходом шахматного коня.
  Входные данные:
  Координаты двух клеток в общепринятом формате.
  Выходные данные:
  «YES», если возможно из одной клетки в другую попасть за один ход.
  «NO», если одна клетка недостижима из другой за один ход.
  Примеры.
  
  8
  

• 9 слайд

  РЕШЕНИЕ
  9
  

• 10 слайд

  10
  

• 11 слайд

  11
  

• 12 слайд

  О ферзях
  Вася недавно начал заниматься шахматами и где-то прочел головоломку, в которой нужно было расставить максимальное количество ферзей на доске 8х8 так, чтобы хотя бы одно поле оказалось небитым. Помогите Васе решить эту задачу для доски NxN.
  12
  

• 13 слайд

  О ферзях
  Входные данные:
  натуральное число N – размеры шахматной доски NxN (1 ≤ N ≤ 100)..
  
  Выходные данные:
  максимальное количество ферзей, которых можно расставить на шахматной доске NxN так, чтобы одна клетка оставалась небитой..
  
  Примеры.
  
  13
  

• 14 слайд

  РЕШЕНИЕ
  14
  

• 15 слайд

  РЕШЕНИЕ
  На доске NxN всего N2 клеток.
  Ферзей нельзя ставить на 3N – 2 клетки.
  Для ферзей остается
  N2 – (3N – 2) клетки.
  15
  

• 16 слайд

  16
  

• 17 слайд

  ЕЖИК
  На шахматной доске размером 8x8 расставлено k пронумерованных фишек. Ежик, который собирает эти фишки, выходит из клетки с координатами (1,1) и должен собрать все фишки в порядке возрастания их номеров. Из клетки с координатами (x, y) ежик может переместиться только в одну из четырех соседних.
  Требуется определить, какое минимальное количество ходов нужно сделать, чтобы собрать все фишки.
  Если ежик проходит через клетку, где содержится фишка с большим номером, чем он сейчас должен взять, то оставляет ее на месте.
  
  17
  

• 18 слайд

  ЕЖИК
  Входные данные:
  количество фишек k, координаты фишек.
  Выходные данные:
  единственное число – минимальное количество шагов, которое потребуется для сбора всех фишек в порядке возрастания их номеров.
  Примеры.
  
  18
  

• 19 слайд

  РЕШЕНИЕ
  Из клетки с координатами (x, y) ежик может переместиться только в одну из четырех соседних:
  (x+1,y), (x-1,y), (x,y+1) или (x,y-1).
  1
  2
  3
  4
  │x-x1│ шагов при переходе между столбцами .
  │y-y1│шагов при переходе между строками.
  
  К общей сумме нужно добавлять сумму модулей разности между соответствующими координатами.
  a(x,y)  b(x1,y1)
  пройти через все столбцы между стартовым и конечным;
  пройти через все строки между стартовой и конечной.
  19
  

• 20 слайд

  РЕШЕНИЕ
  20
  

• 21 слайд

  Какое наименьшее число фишек нужно поставить на клетки шахматной доски размера NxN, чтобы на каждой прямой, проходящей через центр произвольной клетки и параллельной каким-либо сторонам или диагоналям доски, стояла хотя бы одна фишка?
  Входные данные:
  натуральное число N – размеры шахматной доски (1≤N≤100)..
  
  Выходные данные:
  Наименьшее число фишек, удовлетворяющее условие задачи..
  
  Пример
  
  ЗАДАЧА 1
  21
  

• 22 слайд

  Напишите программу, которая сможет сообщить, на какие клетки можно пойти конем с заданной клетки.
  Входные данные:
  Координаты клетки, где стоит конь.
  
  Выходные данные:
  Координаты клеток, на которые за один ход может попасть конь, находящийся на заданной клетке.
  
  Пример
  
  ЗАДАЧА 2
  22
  

• 23 слайд

  …
  Фокстротами Шесть Девушек Пленились,
  Эстрадных Танцев Фантастичней Па,
  Едва Ступающий Цыпленок Вылез,
  А Селезень Блуждающий Пропал.
  …
  …
  Жена, Толкая Хилую Подругу,
  Желает Сняться Этим Выходным,
  Ценя Сама Арктическую Вьюгу,
  Бросает Шар Арбуза Четверым.
  …
  23
  

• 24 слайд

  БЛАГОДАРЮ
  ЗА ВНИМАНИЕ!
  [e-mail]