Задание 6 Параграф 1.6 ГДЗ Босова 9 класс Углубленный уровень (Информатика)
Рассмотрим вариант решения задания из учебника
Босова, Аквилянов 9 класс, Просвещение:
Рассмотрим задачу на шахматной доске. В левом верхнем углу находится король. Король может перемещаться только вправо, вниз или по диагонали вправо-вниз на одну клетку. Необходимо определить количество различных маршрутов короля, приводящих его в правый нижний угол.
Число маршрутов для каждой клетки кроме первой — это сумма из трёх возможных предыдущих клеток: слева, справа, по диагонали
x, y – координаты клетки
K(x,y) = K(x-1,y) + K(x,y-1) + K(x-1,y-1)
Клетки по краям поля вниз и слева от исходного положения Короля все имеют всего 1 маршрут, либо вниз, либо вправо
Программа:
n=8
# Создание массива 8х8
F = [[0] * n for i in range(n)]
# Заполнение крайних клеток 1-ми
for i in range(n):
F[i][0] = 1
for j in range(n):
F[0][j] = 1
# Заполнение таблицы сверху вниз
for i in range(1, n):
for j in range(1, n):
F[i][j] = F[i][j - 1] + F[i - 1][j] + F[i - 1][j - 1]
print('Количество маршрутов =',F[n-1][n-1])
Окно вывода:
Количество маршрутов = 48639
