Задача 001

Задание: Найдите количество способов провести шашку на первую линию шахматной доски любого размера. Необходимо учесть, что шашка делает ход только на клетку справа или слева по диагонали перед собой в направлении первой линии.

Напишите, пожалуйста, программу с возможностью ввода трёх чисел через пробел, номер столбца (x) и номер строки (y) на шахматной доске, где стоит шашка и количество клеток по ширине доски (w width). y и w целые числа больше 1, w > x, x > 0. Программа, в результате работы, должна вывести число равное количеству способов провести шашку на первую линию шахматной доски (в дамки).

I вариант решения задачи:

# d — дано;  x, y — начальные координаты шашки на шахматной доске
# w — ширина шахматной доски
# f — функция, которая возвращает количество вариантов
# пути шашки в дамки (на первую строку).

def f(x,y,w):
        if x < 1  or x > w:
            return 0
        if y == 1:
            return 1
        else:
            return f(x -1, y-1, w) + f(x+1, y-1, w)

while True:
    d = [int(i) for i in input('Введите x y w: ').split()]
    print(f(*d))

Лист. 1. Программа решающая, с помощью рекурсии, задачу о проходе шашки в дамки.

II вариант решения задачи:

Решим

Рис. 2. Таблица, составленная в программе OpenOffice Calc, решающая задачу о проходе шашки в дамки.

III вариант решения задачи:

# Программа возвращает количество вариантов пути шашки в дамки
# (на первую строку).
# d — дано;  x, y — начальные координаты шашки на шахматной доске.
# w — ширина шахматной доски.

while True:
    x, y, w = [int(i) for i in input('Введите x y w: ').split()]
    A = [0] + [1]*w +[0]
    B = [0] * (w + 2)
    for j in range(1, y):
        for i in range(1, w+1):
            B[i] = A[i-1] + A[i+1]
        A = B.copy()
    print(A[x])

Лист. 2. Программа решающая, с помощью вложенного цикла, задачу о проходе шашки в дамки.

Python