Шахматный номер

From

Konstantin Azarov ()

To

Evgeniy Jirnov ()

Date

2003-01-21T05:06:11Z

Area

RU.ALGORITHMS

From: "Konstantin Azarov" <azarov@comtv.ru>

Hello, Evgeniy!

 EJ> Кто знает алгоритм решения:
 EJ> Телефонный номер называется шахматным, если его цифры набираются
 EJ> ходом шахматного коня. Требуется подсчитать сколько можно набрать
 EJ> 6-значных шахматных номер начинающихся с заданной цифры. Вопрос -
 EJ> как?

Вот как:

Пусть мы знаем количество номеров длины l начинающихся с заданной циры и
оканчивающихся на цифру i (i=0..9). Пусть это будет F(l, i). Спрашивается,
сколько будет номеров длины l+1 заканчивающихся на цифру j? Например, для
j=7 это будет F(l+1, 7) = F(l, 2) + F(l, 6), а для j=5 это будет 0. Дальше
считаем F(6, i), полагая F(1, A)=1; F(1, j)=0, где j<>A, и A - заданная
цифра.

--- ifmail v.2.15dev5
 * Origin: Comcor-TV (2:5020/400)