【ruby】テストで頻出する数式や数列、公式、定理

2025/01/21に公開

就職活動やプログラミングテストで頻出する数式や数列、公式、定理を以下にまとめます。これらはアルゴリズムや数学的思考を必要とする問題でよく利用されます。


1. 数列に関する公式

等差数列

  • 一般項: ( a_n = a_1 + (n - 1) \cdot d )
    • ( a_1 ): 初項
    • ( d ): 公差
  • : ( S_n = \frac{n}{2} \cdot (a_1 + a_n) )

等比数列

  • 一般項: ( a_n = a_1 \cdot r^{n-1} )
    • ( r ): 公比
  • :
    • ( S_n = a_1 \cdot \frac{1 - r^n}{1 - r} ) (( r \neq 1 ))
    • 無限等比数列の和: ( S = \frac{a_1}{1 - r} ) (( |r| < 1 ))
具体例

問題:

数列 ( 2, 5, 8, 11, 14 ) の第10項と、最初の10項の和を求める。

解法:

  • 初項: ( a_1 = 2 )
  • 公差: ( d = 3 )
  • 第10項: ( a_{10} = a_1 + (10 - 1) \cdot d = 2 + 9 \cdot 3 = 29 )
  • : ( S_{10} = \frac{10}{2} \cdot (a_1 + a_{10}) = 5 \cdot (2 + 29) = 155 )

実装:

a1 = 2
d = 3
n = 10

a10 = a1 + (n - 1) * d
s10 = n * (a1 + a10) / 2

puts "第10項: #{a10}" # => 第10項: 29
puts "和: #{s10}"    # => 和: 155

2. 素数関連

  • エラトステネスの篩(Sieve of Eratosthenes):
    • 1から( N )までの素数を効率的に列挙するアルゴリズム。

素数判定

def is_prime?(n)
  return false if n < 2
  (2..Math.sqrt(n).to_i).each do |i|
    return false if n % i == 0
  end
  true
end
具体例

問題:

数値 29 が素数かどうかを判定する。

解法:

  1. 素数は ( 2 ) 以上で、約数が ( 1 ) と自分自身のみ。
  2. ( \sqrt{29} \approx 5.38 ) なので、2から5までで割り切れるか確認。
  3. 割り切れないため、29 は素数。

実装:

def is_prime?(n)
  return false if n < 2
  (2..Math.sqrt(n).to_i).each do |i|
    return false if n % i == 0
  end
  true
end

puts is_prime?(29) # => true

3. 組み合わせと順列

順列(Permutation)

  • 公式: ( P(n, r) = \frac{n!}{(n - r)!} )

組み合わせ(Combination)

  • 公式: ( C(n, r) = \frac{n!}{r! \cdot (n - r)!} )

実装例

def factorial(n)
  (1..n).reduce(1, :*)
end

def combination(n, r)
  factorial(n) / (factorial(r) * factorial(n - r))
end
具体例

問題:

5人から2人を選ぶ方法の順列と組み合わせを求める。

解法:

  • 順列: ( P(5, 2) = \frac{5!}{(5 - 2)!} = 5 \cdot 4 = 20 )
  • 組み合わせ: ( C(5, 2) = \frac{5!}{2! \cdot (5 - 2)!} = \frac{20}{2} = 10 )

実装:

def factorial(n)
  (1..n).reduce(1, :*)
end

n, r = 5, 2
permutation = factorial(n) / factorial(n - r)
combination = factorial(n) / (factorial(r) * factorial(n - r))

puts "順列: #{permutation}"  # => 順列: 20
puts "組み合わせ: #{combination}" # => 組み合わせ: 10

4. ユークリッドの互除法

  • 目的: 2つの整数の最大公約数(GCD)を求める。
  • 公式:
    • ( \text{GCD}(a, b) = \text{GCD}(b, a % b) )
    • 再帰で計算可能。

実装例

def gcd(a, b)
  return a if b == 0
  gcd(b, a % b)
end
具体例

問題:

36 と 48 の最大公約数を求める。

解法:

  1. ( \text{GCD}(48, 36) = \text{GCD}(36, 48 % 36) = \text{GCD}(36, 12) )
  2. ( \text{GCD}(36, 12) = \text{GCD}(12, 36 % 12) = \text{GCD}(12, 0) )
  3. 答えは 12。

実装:

def gcd(a, b)
  return a if b == 0
  gcd(b, a % b)
end

puts gcd(36, 48) # => 12

5. フィボナッチ数列

  • 一般項(漸化式): ( F(n) = F(n-1) + F(n-2) )
    • 初期条件: ( F(0) = 0, F(1) = 1 )

高速な計算方法(行列の累乗)

def fibonacci(n)
  return n if n <= 1
  fib = [0, 1]
  (2..n).each { |i| fib[i] = fib[i - 1] + fib[i - 2] }
  fib[n]
end
具体例

問題:

フィボナッチ数列の10番目の値を求める。

解法:

  1. ( F(0) = 0, F(1) = 1 )
  2. ( F(n) = F(n-1) + F(n-2) )
  3. ( F(10) = 55 )。

実装:

def fibonacci(n)
  return n if n <= 1
  fib = [0, 1]
  (2..n).each { |i| fib[i] = fib[i - 1] + fib[i - 2] }
  fib[n]
end

puts fibonacci(10) # => 55

6. モジュロ演算

  • プログラミングテストでよく使用される「余り」を扱う演算。
  • 性質:
    • ( (a + b) % c = ((a % c) + (b % c)) % c )
    • ( (a \cdot b) % c = ((a % c) \cdot (b % c)) % c )
具体例

問題:

( (1234 + 5678) % 100 ) を計算する。

解法:

  1. ( 1234 % 100 = 34 )
  2. ( 5678 % 100 = 78 )
  3. ( (34 + 78) % 100 = 112 % 100 = 12 )。

実装:

a, b, c = 1234, 5678, 100
result = (a % c + b % c) % c
puts result # => 12

7. 三角形に関する公式

ヘロンの公式

  • 三角形の面積 ( S ) を 3 辺 ( a, b, c ) から計算する。
  • 公式:
    ( S = \sqrt{s \cdot (s - a) \cdot (s - b) \cdot (s - c)} )
    • ( s = \frac{a + b + c}{2} )(半周長)
具体例

問題:

三角形の辺の長さが 3, 4, 5 のとき、面積を求める。

解法:

  1. ( s = \frac{3 + 4 + 5}{2} = 6 )
  2. ( S = \sqrt{6 \cdot (6 - 3) \cdot (6 - 4) \cdot (6 - 5)} = \sqrt{6 \cdot 3 \cdot 2 \cdot 1} = 6 )

実装:

a, b, c = 3, 4, 5
s = (a + b + c) / 2.0
area = Math.sqrt(s * (s - a) * (s - b) * (s - c))
puts area # => 6.0

8. 二分探索

  • 目的: ソート済み配列において、特定の値を効率的に探す。
  • 計算量: ( O(\log N) )

実装例

def binary_search(arr, target)
  left, right = 0, arr.size - 1
  while left <= right
    mid = (left + right) / 2
    if arr[mid] == target
      return mid
    elsif arr[mid] < target
      left = mid + 1
    else
      right = mid - 1
    end
  end
  -1 # 見つからなかった場合
end
具体例

問題:

ソート済み配列 [1, 3, 5, 7, 9] から 7 を探す。

解法:

  1. 中央値は 5 → 7 > 5 のため右半分へ。
  2. 中央値は 7 → 発見。

実装:

def binary_search(arr, target)
  left, right = 0, arr.size - 1
  while left <= right
    mid = (left + right) / 2
    return mid if arr[mid] == target
    arr[mid] < target ? left = mid + 1 : right = mid - 1
  end
  -1 # 見つからなかった場合
end

puts binary_search([1, 3, 5, 7, 9], 7) # => 3

9. グラフ理論の基本

ダイクストラ法

  • 最短経路を求めるアルゴリズム。
  • 計算量: ( O(V^2) ) または ( O((V + E) \log V) )(ヒープを使用した場合)。
具体例

問題:

以下のグラフで頂点 A から各頂点への最短距離を求める。

A -1-> B -2-> C
A -4-> C

実装:

require 'set'

def dijkstra(graph, start)
  distances = Hash.new(Float::INFINITY)
  distances[start] = 0
  pq = Set.new([start])

  until pq.empty?
    current = pq.min_by { |node| distances[node] }
    pq.delete(current)

    graph[current].each do |neighbor, weight|
      new_distance = distances[current] + weight
      if new_distance < distances[neighbor]
        distances[neighbor] = new_distance
        pq.add(neighbor)
      end
    end
  end

  distances
end

graph = {
  'A' => {'B' => 1, 'C' => 4},
  'B' => {'C' => 2},
  'C' => {}
}

puts dijkstra(graph, 'A') # => {"A"=>0, "B"=>1, "C"=>3}

10. その他便利な公式

  • 階差数列: 数列の差を計算して規則性を見つける問題。
  • 指数計算の高速化(累乗のモジュロ):
    • ( a^b % c ) を効率的に計算する。
def mod_exp(a, b, c)
  result = 1
  while b > 0
    result = (result * a) % c if b.odd?
    a = (a * a) % c
    b /= 2
  end
  result
end

これらの数式やアルゴリズムは、コーディングテストやプログラミング課題で頻出です。事前に理解して、実装方法を練習しておくとよいでしょう!

Discussion