alt text

Митя придумал новую игру. Дана клетчатая доска размером 6×66×6 клеток, на которой расставлены препятствия.
В начале партии фигурка игрока стоит на клетке (1,1) (клетка, находящаяся на пересечении первой снизу строки и первого слева столбца). За ход фигурка может сделать один из трех шагов:
-перейти на соседнюю клетку сверху,
-перейти на соседнюю клетку справа,
-перейти на соседнюю клетку по диагонали сверху-справа.
Попасть на клетку можно, только если на ней нет препятствия. Цель: попасть на клетку (6,6).

Помогите Мите определить, сколько различных партий можно сыграть на этом поле. В качестве ответа выведите одно целое число.

задан 30 Дек '16 12:08

Заполняем таблицу числами по строкам слева направо. В каждую клетку вписываем число способов в неё попасть из (1,1). Если попасть нельзя, то вписываем 0. Первая снизу строка примет вид 111000 (считая чёрную клетку). Во второй строке будут числа 135666. Здесь число в клетке равно сумме чисел в клетках слева, снизу, и по диагонали слева снизу. Таблица по этому правилу заполняется однозначно. У меня вышло 466 в клетке (6,6), но полезно перепроверить.

(30 Дек '16 12:49) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×91

задан
30 Дек '16 12:08

показан
901 раз

обновлен
30 Дек '16 12:49

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru