teratail
回答率
85.48%
質問するログイン新規登録
トップに関する質問大きな数字でもコンビネーションの計算を速く求めるには？

編集履歴

質問編集履歴

12

コードの修正を行う。

2015/05/05 12:19

投稿

manman
manman

スコア233

test CHANGED
File without changes
test CHANGED
@@ -26,7 +26,7 @@
26
26
 
27
27
  (0..a).each{|b|
28
28
 
29
- cnt += c(a, b)
29
+ cnt += ncr(a, b)
30
30
 
31
31
  }
32
32
 

11

関数をncrに統一する。

2015/05/05 12:19

投稿

manman
manman

スコア233

test CHANGED
File without changes
test CHANGED
@@ -4,15 +4,15 @@
4
4
 
5
5
  ```lang-ruby
6
6
 
7
- def c(m, n)
7
+ def ncr(n, r)
8
8
 
9
- n = m - n if n > m - n
9
+ r = n - r if r > n - r
10
10
 
11
- return 0 if n < 0
11
+ return 0 if r < 0
12
12
 
13
- return 1 if n == 0
13
+ return 1 if r == 0
14
14
 
15
- return (m - n + 1..m).inject(:*) / (1..n).inject(:*)
15
+ return (n - r + 1..n).inject(:*) / (1..r).inject(:*)
16
16
 
17
17
  end
18
18
 
@@ -40,35 +40,7 @@
40
40
 
41
41
  速く求められるようにするには
42
42
 
43
- 以下をどのように埋めればよろしいでしょうか？
43
+ ncr をどのように定めればよろしいのでしょうか？
44
-
45
- ```lang-ruby
46
-
47
- def c(m, n)
48
-
49
- ？？？
50
-
51
- end
52
-
53
-
54
-
55
- N = 1000
56
-
57
- cnt = 0
58
-
59
- (0..N).each{|a|
60
-
61
- (0..a).each{|b|
62
-
63
- cnt += c(a, b)
64
-
65
- }
66
-
67
- }
68
-
69
- p cnt == 2 ** (N + 1) - 1
70
-
71
- ```
72
44
 
73
45
 
74
46
 

10

コードの修正を行う。

2015/05/05 11:51

投稿

manman
manman

スコア233

test CHANGED
File without changes
test CHANGED
@@ -1,4 +1,4 @@
1
- 以下の工夫なしのコードでは、コンビネーションの計算をするのに
1
+ 以下の**工夫なし**のコードでは、コンビネーションの計算をするのに
2
2
 
3
3
  １分以上かかっています。
4
4
 
@@ -31,8 +31,6 @@
31
31
  }
32
32
 
33
33
  }
34
-
35
- # trueと出力されるはず
36
34
 
37
35
  p cnt == 2 ** (N + 1) - 1
38
36
 
@@ -68,8 +66,6 @@
68
66
 
69
67
  }
70
68
 
71
- # trueと出力されるはず
72
-
73
69
  p cnt == 2 ** (N + 1) - 1
74
70
 
75
71
  ```
@@ -78,7 +74,7 @@
78
74
 
79
75
  （追記）
80
76
 
81
- ちなみに、Python版（工夫なし）では同じ計算を１分以内で行います。
77
+ ちなみに、Python版（**工夫なし**）では同じ計算を１分以内で行います。
82
78
 
83
79
  ```lang-Python
84
80
 

9

文を追加しました。

2015/05/05 11:36

投稿

manman
manman

スコア233

test CHANGED
File without changes
test CHANGED
@@ -1,4 +1,6 @@
1
- 以下のコンビネーションの計算をするのに１分以上かかっています。
1
+ 以下の工夫なしのコードでは、コンビネーションの計算をするのに
2
+
3
+ １分以上かかっています。
2
4
 
3
5
  ```lang-ruby
4
6
 

8

追記を追加しました。

2015/05/05 11:24

投稿

manman
manman

スコア233

test CHANGED
File without changes
test CHANGED
@@ -36,15 +36,11 @@
36
36
 
37
37
  ```
38
38
 
39
-
40
-
41
39
  大きな数字でもコンビネーションの計算を
42
40
 
43
41
  速く求められるようにするには
44
42
 
45
43
  以下をどのように埋めればよろしいでしょうか？
46
-
47
-
48
44
 
49
45
  ```lang-ruby
50
46
 
@@ -77,6 +73,8 @@
77
73
  ```
78
74
 
79
75
 
76
+
77
+ （追記）
80
78
 
81
79
  ちなみに、Python版（工夫なし）では同じ計算を１分以内で行います。
82
80
 

7

Python版を追加。

2015/05/04 18:35

投稿

manman
manman

スコア233

test CHANGED
File without changes
test CHANGED
@@ -75,3 +75,57 @@
75
75
  p cnt == 2 ** (N + 1) - 1
76
76
 
77
77
  ```
78
+
79
+
80
+
81
+ ちなみに、Python版（工夫なし）では同じ計算を１分以内で行います。
82
+
83
+ ```lang-Python
84
+
85
+ from math import factorial
86
+
87
+
88
+
89
+ def product(iterable):
90
+
91
+ prod = 1
92
+
93
+ for n in iterable:
94
+
95
+ prod *= n
96
+
97
+ return prod
98
+
99
+
100
+
101
+ def npr(n, r):
102
+
103
+ return product(range(n - r + 1, n + 1))
104
+
105
+
106
+
107
+ def ncr(n, r):
108
+
109
+ if r > n // 2:
110
+
111
+ r = n - r
112
+
113
+ return npr(n, r) // factorial(r)
114
+
115
+
116
+
117
+ N = 1000
118
+
119
+ cnt = 0
120
+
121
+ for a in xrange(N + 1):
122
+
123
+ for b in xrange(a + 1):
124
+
125
+ cnt += ncr(a, b)
126
+
127
+
128
+
129
+ print cnt == 2 ** (N + 1) - 1
130
+
131
+ ```

6

コードをスッキリさせた。

2015/05/04 18:32

投稿

manman
manman

スコア233

test CHANGED
File without changes
test CHANGED
@@ -4,15 +4,11 @@
4
4
 
5
5
  def c(m, n)
6
6
 
7
- return 1 if m == n
8
-
9
- return 0 if m < n
7
+ n = m - n if n > m - n
10
8
 
11
9
  return 0 if n < 0
12
10
 
13
11
  return 1 if n == 0
14
-
15
- n = m - n if n > m - n
16
12
 
17
13
  return (m - n + 1..m).inject(:*) / (1..n).inject(:*)
18
14
 

5

コードの修正を行う。

2015/05/04 15:37

投稿

manman
manman

スコア233

test CHANGED
File without changes
test CHANGED
@@ -12,15 +12,9 @@
12
12
 
13
13
  return 1 if n == 0
14
14
 
15
- if n <= m - n
15
+ n = m - n if n > m - n
16
16
 
17
- return (m - n + 1..m).inject(:*) / (1..n).inject(:*)
17
+ return (m - n + 1..m).inject(:*) / (1..n).inject(:*)
18
-
19
- else
20
-
21
- return (n + 1..m).inject(:*) / (1..m - n).inject(:*)
22
-
23
- end
24
18
 
25
19
  end
26
20
 

4

どこを埋めるか分かりやすくしました。

2015/05/04 14:44

投稿

manman
manman

スコア233

test CHANGED
File without changes
test CHANGED
@@ -60,7 +60,7 @@
60
60
 
61
61
  def c(m, n)
62
62
 
63
-
63
+ ？？？
64
64
 
65
65
  end
66
66
 

3

遅いコードも追加。

2015/05/04 05:28

投稿

manman
manman

スコア233

test CHANGED
File without changes
test CHANGED
@@ -1,3 +1,53 @@
1
+ 以下のコンビネーションの計算をするのに１分以上かかっています。
2
+
3
+ ```lang-ruby
4
+
5
+ def c(m, n)
6
+
7
+ return 1 if m == n
8
+
9
+ return 0 if m < n
10
+
11
+ return 0 if n < 0
12
+
13
+ return 1 if n == 0
14
+
15
+ if n <= m - n
16
+
17
+ return (m - n + 1..m).inject(:*) / (1..n).inject(:*)
18
+
19
+ else
20
+
21
+ return (n + 1..m).inject(:*) / (1..m - n).inject(:*)
22
+
23
+ end
24
+
25
+ end
26
+
27
+
28
+
29
+ N = 1000
30
+
31
+ cnt = 0
32
+
33
+ (0..N).each{|a|
34
+
35
+ (0..a).each{|b|
36
+
37
+ cnt += c(a, b)
38
+
39
+ }
40
+
41
+ }
42
+
43
+ # trueと出力されるはず
44
+
45
+ p cnt == 2 ** (N + 1) - 1
46
+
47
+ ```
48
+
49
+
50
+
1
51
  大きな数字でもコンビネーションの計算を
2
52
 
3
53
  速く求められるようにするには
@@ -14,12 +64,24 @@
14
64
 
15
65
  end
16
66
 
17
- # 100C50を計算
18
67
 
68
+
19
- p c(100, 50)
69
+ N = 1000
70
+
71
+ cnt = 0
72
+
73
+ (0..N).each{|a|
74
+
75
+ (0..a).each{|b|
76
+
77
+ cnt += c(a, b)
78
+
79
+ }
80
+
81
+ }
82
+
83
+ # trueと出力されるはず
84
+
85
+ p cnt == 2 ** (N + 1) - 1
20
86
 
21
87
  ```
22
-
23
- 注意）
24
-
25
- nC0 = 1 とか求められるようにしてください。

2

小文字でないと動かない？

2015/05/04 05:26

投稿

manman
manman

スコア233

test CHANGED
File without changes
test CHANGED
@@ -8,7 +8,7 @@
8
8
 
9
9
  ```lang-ruby
10
10
 
11
- def C(m, n)
11
+ def c(m, n)
12
12
 
13
13
 
14
14
 
@@ -16,7 +16,7 @@
16
16
 
17
17
  # 100C50を計算
18
18
 
19
- p C(100, 50)
19
+ p c(100, 50)
20
20
 
21
21
  ```
22
22
 

1

初心者マーク追加。

2015/05/03 08:19

投稿

manman
manman

スコア233

test CHANGED
File without changes
test CHANGED
File without changes