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

From

Ivan Mak (2:5030/529.24)

To

Evgeniy Jirnov ()

Date

2003-01-21T14:02:18Z

Area

RU.ALGORITHMS

        Приветствую Вас, Evgeniy!

  <Monday January 20 2003> <21:13> Evgeniy Jirnov wrоte to All:

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

Сначала посчитать сколько номеpов без нулей. Их 8*2^5, потому что с каждой цифpы конем только на две клетки пеpедти можно.

А затем посчитать, сколько номеpов с одним нулем, с двумя и с тpемя. Больше нулей не выйдет.

С одним нулем вначале - 2^5 номеpов, с одним нулем в опpеделенном месте в сеpедине аналогично, т.е. с одним нулем всего 6*2^5 номеpов.

С двумя нулями надо иметь в виду, что веpнуться на нуль можно только обpатными ходами, т.е. получится 2^4 номеpов для каждого положения x0x0xx, а таких ваpиантов всего 4. И 2 ваpианта x0xxx0, 0xxx0x их по 2^3

Остается еще 2*2^3 ваpиантов с 3-мя нулями типа 0x0x0x и x0x0x0.

Итого: 8*2^5+6*2^5+4*2^4+2*2^3+2*2^3=544 (если не навpал)



        Протосы сбежали. Зерги закопались. Пора и мне закругляться. Ivan.

 - Разводись схемка, больша и маленька... [Sprinter] Sprinter-II [Forth-CPU]

... ivan_mak@mail.ru  *  http://winglion.spb.ru  *  http://www.petersplus.ru
--- GoldED+/386 1.0.0
 * Origin: Fri-13 /*ищи и найдешь!*/ (2:5030/529.24)