⛳
【ruby】テストで頻出する数式や数列、公式、定理
就職活動やプログラミングテストで頻出する数式や数列、公式、定理を以下にまとめます。これらはアルゴリズムや数学的思考を必要とする問題でよく利用されます。
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 が素数かどうかを判定する。
解法:
- 素数は ( 2 ) 以上で、約数が ( 1 ) と自分自身のみ。
- ( \sqrt{29} \approx 5.38 ) なので、2から5までで割り切れるか確認。
- 割り切れないため、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 の最大公約数を求める。
解法:
- ( \text{GCD}(48, 36) = \text{GCD}(36, 48 % 36) = \text{GCD}(36, 12) )
- ( \text{GCD}(36, 12) = \text{GCD}(12, 36 % 12) = \text{GCD}(12, 0) )
- 答えは 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番目の値を求める。
解法:
- ( F(0) = 0, F(1) = 1 )
- ( F(n) = F(n-1) + F(n-2) )
- ( 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 ) を計算する。
解法:
- ( 1234 % 100 = 34 )
- ( 5678 % 100 = 78 )
- ( (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 のとき、面積を求める。
解法:
- ( s = \frac{3 + 4 + 5}{2} = 6 )
- ( 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 を探す。
解法:
- 中央値は 5 → 7 > 5 のため右半分へ。
- 中央値は 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