Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 14.12.2010, 00:12
Новичок

Отправить личное сообщение для irvind25 Посмотреть профиль Найти все сообщения от irvind25
 
Регистрация: 13.12.2010
Сообщений: 1

Задача о кузнечике
Здравствуйте.
Есть задачка:
Дан абстрактный кузнечик, и абстрактная бесконечная трехмерная сетка, в узлах которой может находится кузнечик. Кузнечик находится в узле с координатами (0,0,0). Перемещается он может на одну клетку в 6-ти направлениях: вверх, вниз, вправо, влево, вперед, назад.
Также дано число n (0 <= n <= 200). Нужно найти количество возможных последовательностей перемещений кузнечика, так, чтобы его путь состоял из 2*n шагов, и начинался из нач. точки и заканчивался там же. Но во конечную точку при перемещении он может посетить только один раз.

Никак не могу сообразить, какие есть адекватные пути/алгоритмы решения этой задачи. Не подскажите?
  #2  
Старый 14.12.2010, 01:56
гocть

 
Сообщений: n/a

чо тут думать. элементарная задача на динмическое программирование. считаешь для каждой клетки число путей каждой длины в неё из нуля не проходящие дважды через ноль, затем суммируешь для каждой клетки число путей длины n умножить на число путей 200-n.
  #3  
Старый 14.12.2010, 01:58
гocть

 
Сообщений: n/a

и еще поделить на что-то надо чтобы не пересчитаться, но это мелочи реализации. идея, думаю, ясна
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра