回答編集履歴
8
微修正しました。
test
CHANGED
|
@@ -12,7 +12,7 @@
|
|
|
12
12
|
|
|
13
13
|
```lang-Ruby
|
|
14
14
|
|
|
15
|
-
def ncr(n,r)
|
|
15
|
+
def ncr(n, r)
|
|
16
16
|
|
|
17
17
|
r = [r, n - r].min
|
|
18
18
|
|
|
@@ -74,7 +74,7 @@
|
|
|
74
74
|
|
|
75
75
|
```lang-Python
|
|
76
76
|
|
|
77
|
-
def ncr(n,r):
|
|
77
|
+
def ncr(n, r):
|
|
78
78
|
|
|
79
79
|
r = min(r, n - r)
|
|
80
80
|
|
7
コードの改行をなくす。
test
CHANGED
|
@@ -108,8 +108,6 @@
|
|
|
108
108
|
|
|
109
109
|
result *= numerator[k]
|
|
110
110
|
|
|
111
|
-
|
|
112
|
-
|
|
113
111
|
return result
|
|
114
112
|
|
|
115
113
|
|
6
コードが冗長だったので短くする。
test
CHANGED
|
@@ -82,15 +82,9 @@
|
|
|
82
82
|
|
|
83
83
|
if r == 1: return n;
|
|
84
84
|
|
|
85
|
-
numerator = [
|
|
85
|
+
numerator = [n - r + i + 1 for i in range(r)]
|
|
86
86
|
|
|
87
|
-
denominator = [
|
|
87
|
+
denominator = [i + 1 for i in range(r)]
|
|
88
|
-
|
|
89
|
-
for k in range(r):
|
|
90
|
-
|
|
91
|
-
numerator[k] = n - r + k + 1
|
|
92
|
-
|
|
93
|
-
denominator[k] = k + 1
|
|
94
88
|
|
|
95
89
|
for p in range(2, r + 1):
|
|
96
90
|
|
5
ncrに統一する。
test
CHANGED
|
@@ -12,7 +12,7 @@
|
|
|
12
12
|
|
|
13
13
|
```lang-Ruby
|
|
14
14
|
|
|
15
|
-
def c(n,r)
|
|
15
|
+
def ncr(n,r)
|
|
16
16
|
|
|
17
17
|
r = [r, n - r].min
|
|
18
18
|
|
|
@@ -64,7 +64,7 @@
|
|
|
64
64
|
|
|
65
65
|
(0..N).each{|a|
|
|
66
66
|
|
|
67
|
-
cnt += c(N, a)
|
|
67
|
+
cnt += ncr(N, a)
|
|
68
68
|
|
|
69
69
|
}
|
|
70
70
|
|
4
質問の例が悪かった反省の言葉を入れる。
test
CHANGED
|
@@ -4,7 +4,7 @@
|
|
|
4
4
|
|
|
5
5
|
（Ruby版およびPython版どちらの場合も、）
|
|
6
6
|
|
|
7
|
-
質問の例だと**工夫なしの方が速い**のですが、
|
|
7
|
+
質問の例だと残念ながら**工夫なしの方が速い**のですが、
|
|
8
8
|
|
|
9
9
|
N が大きいときの計算をさせると**工夫なしより速くなりました。**
|
|
10
10
|
|
3
Ruby版も追加しました。
test
CHANGED
|
@@ -1,14 +1,76 @@
|
|
|
1
|
-
入山徳夫氏によるnCrを高速に求めるアルゴリズムの
|
|
1
|
+
入山徳夫氏によるnCrを高速に求めるアルゴリズムの
|
|
2
2
|
|
|
3
|
-
|
|
3
|
+
Ruby版およびPython版です。
|
|
4
4
|
|
|
5
|
-
|
|
5
|
+
（Ruby版およびPython版どちらの場合も、）
|
|
6
6
|
|
|
7
|
-
|
|
7
|
+
質問の例だと**工夫なしの方が速い**のですが、
|
|
8
8
|
|
|
9
|
-
工夫なしより速くなりました。
|
|
9
|
+
N が大きいときの計算をさせると**工夫なしより速くなりました。**
|
|
10
10
|
|
|
11
11
|
|
|
12
|
+
|
|
13
|
+
```lang-Ruby
|
|
14
|
+
|
|
15
|
+
def c(n,r)
|
|
16
|
+
|
|
17
|
+
r = [r, n - r].min
|
|
18
|
+
|
|
19
|
+
return 1 if r == 0
|
|
20
|
+
|
|
21
|
+
return n if r == 1
|
|
22
|
+
|
|
23
|
+
numerator = (n - r + 1..n).to_a
|
|
24
|
+
|
|
25
|
+
denominator = (1..r).to_a
|
|
26
|
+
|
|
27
|
+
(2..r).each{|p|
|
|
28
|
+
|
|
29
|
+
pivot = denominator[p - 1]
|
|
30
|
+
|
|
31
|
+
if pivot > 1
|
|
32
|
+
|
|
33
|
+
offset = (n - r) % p
|
|
34
|
+
|
|
35
|
+
(p - 1).step(r - 1, p){|k|
|
|
36
|
+
|
|
37
|
+
numerator[k - offset] /= pivot
|
|
38
|
+
|
|
39
|
+
denominator[k] /= pivot
|
|
40
|
+
|
|
41
|
+
}
|
|
42
|
+
|
|
43
|
+
end
|
|
44
|
+
|
|
45
|
+
}
|
|
46
|
+
|
|
47
|
+
result = 1
|
|
48
|
+
|
|
49
|
+
(0..r - 1).each{|k|
|
|
50
|
+
|
|
51
|
+
result *= numerator[k] if numerator[k] > 1
|
|
52
|
+
|
|
53
|
+
}
|
|
54
|
+
|
|
55
|
+
return result
|
|
56
|
+
|
|
57
|
+
end
|
|
58
|
+
|
|
59
|
+
|
|
60
|
+
|
|
61
|
+
N = 10000
|
|
62
|
+
|
|
63
|
+
cnt = 0
|
|
64
|
+
|
|
65
|
+
(0..N).each{|a|
|
|
66
|
+
|
|
67
|
+
cnt += c(N, a)
|
|
68
|
+
|
|
69
|
+
}
|
|
70
|
+
|
|
71
|
+
p cnt == 2 ** N
|
|
72
|
+
|
|
73
|
+
```
|
|
12
74
|
|
|
13
75
|
```lang-Python
|
|
14
76
|
|
2
コードを修正しました。
test
CHANGED
|
@@ -36,7 +36,7 @@
|
|
|
36
36
|
|
|
37
37
|
if pivot > 1:
|
|
38
38
|
|
|
39
|
-
offset = (n-r) % p
|
|
39
|
+
offset = (n - r) % p
|
|
40
40
|
|
|
41
41
|
for k in range(p - 1, r, p):
|
|
42
42
|
|
1
誤字を修正しました。
test
CHANGED
|
@@ -4,7 +4,7 @@
|
|
|
4
4
|
|
|
5
5
|
工夫なしの方が速いのですが、
|
|
6
6
|
|
|
7
|
-
N が大きいときの計算をさ
|
|
7
|
+
N が大きいときの計算をさせると
|
|
8
8
|
|
|
9
9
|
工夫なしより速くなりました。
|
|
10
10
|
|