編集履歴

質問編集履歴

コードの修正を行う。

2015/05/05 12:19

投稿

manman

スコア233

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -12,7 +12,7 @@
 cnt = 0
 (0..N).each{|a|
   (0..a).each{|b|
-    cnt += c(a, b)
+    cnt += ncr(a, b)
   }
 }
 p cnt == 2 ** (N + 1) - 1

関数をncrに統一する。

2015/05/05 12:19

投稿

manman

スコア233

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -1,11 +1,11 @@
 以下の**工夫なし**のコードでは、コンビネーションの計算をするのに
 １分以上かかっています。
 ```lang-ruby
-def c(m, n)
+def ncr(n, r)
-  n = m - n if n > m - n
+  r = n - r if r > n - r
-  return 0 if n < 0
+  return 0 if r < 0
-  return 1 if n == 0
+  return 1 if r == 0
-  return (m - n + 1..m).inject(:*) / (1..n).inject(:*)
+  return (n - r + 1..n).inject(:*) / (1..r).inject(:*)
 end
 N = 1000
@@ -19,22 +19,8 @@
 ```
 大きな数字でもコンビネーションの計算を
 速く求められるようにするには
-以下をどのように埋めればよろしいでしょうか？
+ncr をどのように定めればよろしいのでしょうか？
-```lang-ruby
-def c(m, n)
- ？？？
-end
-N = 1000
-cnt = 0
-(0..N).each{|a|
-  (0..a).each{|b|
-    cnt += c(a, b)
-  }
-}
-p cnt == 2 ** (N + 1) - 1
-```
 （追記）
 ちなみに、Python版（**工夫なし**）では同じ計算を１分以内で行います。
 ```lang-Python

コードの修正を行う。

2015/05/05 11:51

投稿

manman

スコア233

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -1,4 +1,4 @@
-以下の工夫なしのコードでは、コンビネーションの計算をするのに
+以下の**工夫なし**のコードでは、コンビネーションの計算をするのに
 １分以上かかっています。
 ```lang-ruby
 def c(m, n)
@@ -15,7 +15,6 @@
     cnt += c(a, b)
   }
 }
-# trueと出力されるはず
 p cnt == 2 ** (N + 1) - 1
 ```
 大きな数字でもコンビネーションの計算を
@@ -33,12 +32,11 @@
     cnt += c(a, b)
   }
 }
-# trueと出力されるはず
 p cnt == 2 ** (N + 1) - 1
 ```
 （追記）
-ちなみに、Python版（工夫なし）では同じ計算を１分以内で行います。
+ちなみに、Python版（**工夫なし**）では同じ計算を１分以内で行います。
 ```lang-Python
 from math import factorial

文を追加しました。

2015/05/05 11:36

投稿

manman

スコア233

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -1,4 +1,5 @@
-以下のコンビネーションの計算をするのに１分以上かかっています。
+以下の工夫なしのコードでは、コンビネーションの計算をするのに
+１分以上かかっています。
 ```lang-ruby
 def c(m, n)
   n = m - n if n > m - n

追記を追加しました。

2015/05/05 11:24

投稿

manman

スコア233

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -17,11 +17,9 @@
 # trueと出力されるはず
 p cnt == 2 ** (N + 1) - 1
 ```
 大きな数字でもコンビネーションの計算を
 速く求められるようにするには
 以下をどのように埋めればよろしいでしょうか？
 ```lang-ruby
 def c(m, n)
  ？？？
@@ -38,6 +36,7 @@
 p cnt == 2 ** (N + 1) - 1
 ```
+（追記）
 ちなみに、Python版（工夫なし）では同じ計算を１分以内で行います。
 ```lang-Python
 from math import factorial

Python版を追加。

2015/05/04 18:35

投稿

manman

スコア233

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -36,4 +36,31 @@
 }
 # trueと出力されるはず
 p cnt == 2 ** (N + 1) - 1
+```
+ちなみに、Python版（工夫なし）では同じ計算を１分以内で行います。
+```lang-Python
+from math import factorial
+def product(iterable):
+    prod = 1
+    for n in iterable:
+        prod *= n
+    return prod
+def npr(n, r):
+    return product(range(n - r + 1, n + 1))
+def ncr(n, r):
+    if r > n // 2:
+        r = n - r
+    return npr(n, r) // factorial(r)
+N = 1000
+cnt = 0
+for a in xrange(N + 1):
+    for b in xrange(a + 1):
+        cnt += ncr(a, b)
+print cnt == 2 ** (N + 1) - 1
 ```

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

2015/05/04 18:32

投稿

manman

スコア233

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -1,11 +1,9 @@
 以下のコンビネーションの計算をするのに１分以上かかっています。
 ```lang-ruby
 def c(m, n)
-  return 1 if m == n
-  return 0 if m < n
+  n = m - n if n > m - n
   return 0 if n < 0
   return 1 if n == 0
-  n = m - n if n > m - n
   return (m - n + 1..m).inject(:*) / (1..n).inject(:*)
 end

コードの修正を行う。

2015/05/04 15:37

投稿

manman

スコア233

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -5,11 +5,8 @@
   return 0 if m < n
   return 0 if n < 0
   return 1 if n == 0
-  if n <= m - n
+  n = m - n if n > m - n
-    return (m - n + 1..m).inject(:*) / (1..n).inject(:*)
+  return (m - n + 1..m).inject(:*) / (1..n).inject(:*)
-  else
-    return (n + 1..m).inject(:*) / (1..m - n).inject(:*)
-  end
 end
 N = 1000

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

2015/05/04 14:44

投稿

manman

スコア233

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -29,7 +29,7 @@
 ```lang-ruby
 def c(m, n)
+ ？？？
 end
 N = 1000

遅いコードも追加。

2015/05/04 05:28

投稿

manman

スコア233

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -1,3 +1,28 @@
+以下のコンビネーションの計算をするのに１分以上かかっています。
+```lang-ruby
+def c(m, n)
+  return 1 if m == n
+  return 0 if m < n
+  return 0 if n < 0
+  return 1 if n == 0
+  if n <= m - n
+    return (m - n + 1..m).inject(:*) / (1..n).inject(:*)
+  else
+    return (n + 1..m).inject(:*) / (1..m - n).inject(:*)
+  end
+end
+N = 1000
+cnt = 0
+(0..N).each{|a|
+  (0..a).each{|b|
+    cnt += c(a, b)
+  }
+}
+# trueと出力されるはず
+p cnt == 2 ** (N + 1) - 1
+```
 大きな数字でもコンビネーションの計算を
 速く求められるようにするには
 以下をどのように埋めればよろしいでしょうか？
@@ -6,8 +31,14 @@
 def c(m, n)
 end
-# 100C50を計算
-p c(100, 50)
+N = 1000
+cnt = 0
+(0..N).each{|a|
+  (0..a).each{|b|
+    cnt += c(a, b)
+  }
+}
+# trueと出力されるはず
+p cnt == 2 ** (N + 1) - 1
-```
+```
-注意）
-nC0 = 1 とか求められるようにしてください。

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

2015/05/04 05:26

投稿

manman

スコア233

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -3,11 +3,11 @@
 以下をどのように埋めればよろしいでしょうか？
 ```lang-ruby
-def C(m, n)
+def c(m, n)
 end
 # 100C50を計算
-p C(100, 50)
+p c(100, 50)
 ```
 注意）
 nC0 = 1 とか求められるようにしてください。

初心者マーク追加。

2015/05/03 08:19

投稿

manman

スコア233

title CHANGED Viewed

File without changes

body CHANGED Viewed

File without changes