Прикреплённый файл «2014-04-18-knight.py»

Загрузка

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз. Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
   5 '''
   6 import sys
   7 
   8 def dump():
   9     print "Maximal front:",mlen
  10     for y in xrange(1,N+1):
  11         print "".join(["{:<2}".format(Res.get((x,y),".")) for x in xrange(1,M+1)])
  12 
  13 M,N = len(sys.argv)>2 and (int(sys.argv[1]),int(sys.argv[2])) or (11,15)
  14 if (M+N)%3!=2:
  15     print "No way"
  16     sys.exit(0)
  17 Sum={(1,1):1}
  18 mlen=1
  19 while Sum:
  20     NSum={}
  21     for m,n in Sum:
  22         if n+2<=N and m+1<=M:
  23             NSum[(m+1,n+2)]=NSum.get((m+1,n+2),0)+Sum[(m,n)]
  24         if n+1<=N and m+2<=M:
  25             NSum[(m+2,n+1)]=NSum.get((m+2,n+1),0)+Sum[(m,n)]
  26     Sum,Res = NSum,Sum
  27     mlen=max(mlen,len(Sum))
  28     # dump()
  29 print Res[(M,N)]

Прикреплённые файлы

Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.

Вам нельзя прикреплять файлы к этой странице.