Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Ruby script to calculate binomial coefficients.
#*********************************************
# 二項係数計算モジュール
#
# DATE AUTHOR VERSION
# 2019.10.19 mk-mode.com 1.00 新規作成
#
# Copyright(C) 2019 mk-mode.com All Rights Reserved.
#*********************************************
module BinomCoeff
# 二項係数の計算(1)
# 計算式: (n r) = n! / r!(n -r)!
#
# @param n: n の値
# @param r: r の値
# @return : 二項係数
def binom_1(n, r)
return 1 if r == 0 || r == n
return fact(n) / (fact(r) * fact(n - r))
rescue => e
raise
end
# 二項係数の計算(2)
# 計算式: (n r) = ((n - 1) r) + ((n - 1) (k - 1))
# (recursively)
#
# @param n: n の値
# @param r: r の値
# @return : 二項係数
def binom_2(n, r)
return 1 if r == 0 || r == n
return binom_2(n - 1, r) + binom_2(n - 1, r - 1)
rescue => e
raise
end
# 二項係数の計算(3)
# 計算式: (n r) = (n / r) * ((n - 1) (k - 1))
# (recursively)
#
# @param n: n の値
# @param r: r の値
# @return : 二項係数
def binom_3(n, r)
return 1 if r == 0 || r == n
return n * binom_3(n - 1, r - 1) / r
rescue => e
raise
end
# 二項係数の計算(4)
# 計算式: (n r) = Π(n - i + 1) / i (i = 1, ..., r)
#
# @param n: n の値
# @param r: r の値
# @return : 二項係数
def binom_4(n, r)
return 1 if r == 0 || r == n
return (1..r).inject(1) { |s, i| s * (n - i + 1) / i }
rescue => e
raise
end
# 階乗の計算
def fact(x)
return x == 0 ? 1 : (1..x).inject(&:*)
rescue => e
raise
end
end
#! /usr/local/bin/ruby
#***************************************************
# 二項係数の計算
#
# DATE AUTHOR VERSION
# 2019.10.19 mk-mode.com 1.00 新規作成
#
# Copyright(C) 2019 mk-mode.com All Rights Reserved.
#***************************************************
#
require './binom_coeff'
class TestBinom
include BinomCoeff
# テストしたい n と r の組み合わせ
DATA = [
[ 0, 1],
[ 1, -1],
[ 1, 0.9],
[ 1.1, 1],
[ 1, 0],
[ 1, 1],
[ 10, 2],
[ 100, 3],
[1000, 4],
[5000, 500],
[5000, 2500],
]
# 計算
#
# 計算式
# 1. (n r) = n! / r!(n -r)!
# 2. (n r) = ((n - 1) r) + ((n - 1) (k - 1))
# (recursively)
# 3. (n r) = (n / r) * ((n - 1) (k - 1))
# (recursively)
# 4. (n r) = Π(n - i + 1) / i (i = 1, ..., r)
#
# **注意**
# 計算式(2) では、 n と r の組み合わせにより重くなる。
def calc
DATA.each do |n, r|
if n.integer? && r.integer? && r >= 0 && n >= r
r = n - r if r * 2 > n
b = binom_1(n, r)
#b = binom_2(n, r)
#b = binom_3(n, r)
#b = binom_4(n, r)
else
b = "ERROR"
end
puts "(%5s %5s) = %s" % [n.to_s, r.to_s, b]
end
rescue => e
msg = "[ERROR][#{self.class.name}.#{__method__}] #{e}\n"
msg << e.backtrace.map { |tr| "\t#{tr}" }.join("\n")
$stderr.puts msg
end
end
TestBinom.new.calc if __FILE__ == $0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.