Прикреплённый файл «circpath.py»
Загрузка 1 #!/usr/bin
2 # coding: UTF8
3 '''
4 На окружности отметили N точек и пронумеровали их последовательно числами от
5 1 до N. Требуется найти количество различных простых ломаных с вершинами
6 в некоторых из отмеченных точек и с концами в точках с номерами i и j. Ломаная
7 называется простой, если она не проходит дважды через одну точку и не содержит
8 самокасаний и самопересечений.
9 Вводятся три натуральных числа N, i, j (2 ≤ N ≤ 2 000, 1 ≤ i < j ≤ N)
10
11 Без ограничения общности можно считать i = 0 < j < N ≤ 2000.
12 '''
13
14 import sys
15 from array import *
16
17 def calc(k,N):
18 '''Проверочная рекурсивная функция'''
19 p=1
20 for i in xrange(1,k):
21 p+=calc(k-i,N-i)
22 for i in xrange(N-1,k,-1):
23 p+=calc(k,i)
24 return p
25
26 def sieve(k, N):
27 '''F(k,N) = сумма Cm*F(i,j) 1 < i < N. 1 < j < N, Cm=1,0
28 → актуальны только коэффициенты при F(i,j)
29 '''
30 C1,p={(k,N):1},0
31 while C1:
32 C2={}
33 for k,N in C1:
34 p+=C1[(k,N)]
35 for i in xrange(1,k):
36 C2[(k-i,N-i)]=C2.setdefault((k-i,N-i),0)+C1[(k,N)]
37 for i in xrange(N-1,k,-1):
38 C2[(k,i)]=C2.setdefault((k,i),0)+C1[(k,N)]
39 C1=C2
40 return p
41
42 def stair(k,N):
43 '''Без разницы, в каком порядке вычислять коэффициенты'''
44 C,p={(k,N):1},0
45 while C:
46 (k,N),v=C.popitem()
47 p+=v
48 for i in xrange(1,k):
49 C[(k-i,N-i)]=C.setdefault((k-i,N-i),0)+v
50 for i in xrange(N-1,k,-1):
51 C[(k,i)]=C.setdefault((k,i),0)+v
52 return p
53
54 def lower(k,N):
55 '''Вычисляем коэффициенты так, чтобы на i-м шаге
56 вычислять только коэффициенты при (j,l<=N-i)'''
57 C,p=[{} for i in xrange(N)]+[{k:1}],0
58 while len(C)>1:
59 Ns=C.pop()
60 N=len(C)
61 for k,v in Ns.items():
62 p+=v
63 for i in xrange(1,k):
64 C[N-i][k-i]=C[N-i].setdefault(k-i,0)+v
65 for i in xrange(N-1,k,-1):
66 C[i][k]=C[i].setdefault(k,0)+v
67 return p
68
69 def table(k,N):
70 '''Вычисляем коэффициенты так, чтобы на i-м шаге
71 вычислять только коэффициенты при (j,l<=N-i)
72 Воспользуемся таблицей вместо словаря
73 '''
74 C,p=[[0]*(k+1) for i in xrange(N+1)],0
75 C[N][k]=1
76 while len(C)>1:
77 Ns=C.pop()
78 Ns=[(i,Ns[i]) for i in xrange(len(Ns)) if Ns[i]]
79 N=len(C)
80 for k,v in Ns:
81 p+=v
82 for i in xrange(1,k):
83 C[N-i][k-i]+=v
84 for i in xrange(N-1,k,-1):
85 C[i][k]+=v
86 return p
87
88 fun=len(sys.argv)>3 and sys.argv[3] or "table"
89 print eval(fun+"(int(sys.argv[2]),int(sys.argv[1]))")
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2011-09-26 11:35:37, 0.4 KB) [[attachment:.pythonstartup]]
- [получить | показать] (2011-09-26 11:35:37, 0.5 KB) [[attachment:Sav_2_Circledot.py]]
- [получить | показать] (2011-09-26 11:35:37, 0.8 KB) [[attachment:Sav_3_Thief.py]]
- [получить | показать] (2011-09-26 11:35:37, 0.7 KB) [[attachment:Tkachenko_Bag.py]]
- [получить | показать] (2011-09-26 11:35:37, 3.1 KB) [[attachment:circpath.py]]
Вам нельзя прикреплять файлы к этой странице.