読者です 読者をやめる 読者になる 読者になる

或るプログラマの開発日記

日々の勉強したことの備忘録なんかに使っていきます

Rubyで素因数分解を行う

素因数分解C言語Javaで行う場合、自力で小さい素数から順に割っていく方法なんかが取られるかと思いますが、Rubyでは標準モジュールに素因数分解の処理が用意されていたのでメモ。

Primeクラスのprime_divisionメソッド

Rubyでは、このメソッド一発で素因数分解が出来ます。Ruby便利すぎる。。

使い方
require "prime"
p Prime.prime_division(360)#=>[[2, 3], [3, 2], [5, 1]]
p Prime.prime_division(1683)#=>[[3, 2], [11, 1], [17, 1]]
p Prime.prime_division(65536)#=>[[2, 16]]
p Prime.prime_division(8635844967113809)#=>[[89652331, 1], [96325939, 1]]

prime_divisionメソッドは2次元配列で結果を返してきます。

例として360を素因数分解すると、
360=2^3 \times 3^2 \times 5^1
となります。戻り値は各素因数とそのベキ指数の2要素の配列の配列ということですね。

因みに、prime_divisionメソッドにかなり大きい数の素数を引数に与えると結構処理時間が掛かります。

最大公約数、最小公倍数の求め方/ユーグリットの互除法

今回もアルゴリズムに関して学んだ知識のメモ。ユーグリットの互除法について調べてみました。

ユーグリットの互除法とは

最大公約数を求める手法です。

ユークリッドの互除法ユークリッドのごじょほう、英: Euclidean Algorithm)は、2 つの自然数の最大公約数を求める手法の一つである。

https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95

高校数学なんかでも学ぶ内容ですし、かなり有名なアルゴリズムですね。

ユーグリットの互除法のアルゴリズム

割り算で求めるやり方と引き算で求めるやり方があります。
以下、それぞれのやり方での整数aとb(a >= b)の最大公約数の求め方を記載します。

割り算バージョン
  1. aをbで割った余りを求める。
  2. 余りが0の場合、bが最大公約数。
  3. 余りが0以外の場合、除数(割った数)を先程の余りで割りその余りを求める。
  4. これを余りが0になるまで繰り返す。余りが0になった時の除数が最大公約数
引き算バージョン
  1. aをbで引いた差を求める。
  2. 差が0の場合、bが最大公約数。
  3. 差が0以外の場合、引いた数と差の大きい方から小さい方を引いた差を求める。
  4. これを差が0になるまで繰り返す。差が0になった時の減数(引いた数)が最大公約数

計算量としては割り算で求めるやり方のほうが少ないかと思われます。

最小公倍数の求め方

最大公約数が求めることができれば、最小公倍数は以下の式で求める事が出来ます。

A,Bの最小公倍数=A×B÷A,Bの最大公約数

実装

というわけで、今回もRubyで実装してみます。

#割り算バージョン
def gcd(a, b)
  a, b = b, a if a < b
  loop do
    m = a % b
    return b if m == 0
    a, b = b, m
  end
end

#引き算バージョン
def gcd2(a, b)
  loop do
    a, b = b, a if a < b
    d = a - b
    return b if d == 0
    a, b = b, d
  end
end

#最小公倍数
def lcm(a, b)
  return ((a * b) / gcd(a, b))
end

puts gcd(1071, 1029)#=>21
puts gcd2(1071, 1029)#=>21
puts lcm(1071, 1029)#=>52479

おまけ

ま、Rubyの場合は標準でメソッドが用意されているんですけどねー。

puts 1071.gcd(1029)#=>21
puts 1071.lcm(1029)#=>52479

解法の中身を理解する事も重要だと思います。

エラトステネスのふるいを実装してみる

アルゴリズムに関する知識も自分の中にストックしておきたいということで、今回は「エラトステネスのふるい」について調査したものをメモ。

エラトステネスのふるいとは

素数の一覧を簡易的に求める手法です。

エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。

https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9

手法としては極めて簡潔で、2以上の整数のリストから先ず2の倍数を削除し、次に3の倍数をリストから削除、次に5の倍数を削除という具合に小さい素数から順にその合成数を削除するというやり方です。

アルゴリズム

或る整数nまでの素数を求める場合

  1. 2からnまでの整数を列挙した探索リストを作成する。
  2. 配列の先頭の数を素数リストに移動し、その数の倍数を配列から篩い落とす。
  3. 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
  4. 探索リストに残った数を素数リストに移動して処理終了。

以上の要領で処理を行います。

実装

Rubyで実装をしてみました。2からMAX_NUMまでの素数リストを作成、出力するプログラムです。

MAX_NUM = 120
array = (2..MAX_NUM).to_a
x = 2
s = Math::sqrt(MAX_NUM)
loop do
  pn = array.find{|num| num >= x }
  array.delete_if{|num| num != pn && num % pn == 0 }
  break if x >= s
  x += 1
end
p array

実行結果

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]

Rubyの標準モジュールPrime

Rubyでは素数を扱うモジュールが標準で用意されています。
(実は、実装した後にこの事実に気づいた。。( ̄▽ ̄;))

class Prime (Ruby 2.4.0)

require "prime"
p Prime.each(120).to_a
#=>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]


なんだか、車輪の再発明みたいになってしまったが、今回仕組みは理解出来たので良しとしておこうか。

Rubyのinject/reduceメソッドに関するメモ

つい最近までRubyのinjectやらreduceが何してるか分からんかったので調査したことをメモ。

inject/reduceメソッド

injectメソッドは、ブロックを使って繰り返し計算を行うのに使います。ブロックに順に「要素1、要素2」、「ブロックの前回の戻り値、要素3」、「ブロックの前回の戻り値、要素4」、...を渡します。メソッドの戻り値はブロックが最後に返した値になります。

http://ref.xaio.jp/ruby/classes/enumerable/inject

イメージとしては、ハッシュや配列(要はEnumerableオブジェクト)の各要素に対して繰り返し処理を行い一つに纏めた結果を返す処理に使うものかなーという感じです。

因みにreduceは、injectメソッドの別名となります。mapとcollectの関係みたいなものですね。

使い方いろいろ

injectメソッドの使用例として、配列の合計を求める方法が良く使われます。
以下、サンプルとしていろんな書き方を試してみました。

array = (1..20).to_a

p array.inject {|sum, n| sum + n }#=>210
p array.inject(0){|sum, n| sum + n }#=>210
p array.inject(0,:+)#=>210
p array.inject(:+)#=>210

#100を初期値にしてみる
p array.inject(100,:+)#=>310

injectの書き方にもブロックで要素を処理する方法や、初期値を指定または省略する方法、またメソッドの引数でシンボルを渡して処理する方法があります。

また、配列の合計を計算する以外の使い方もあります。

次の例では初期値を空のハッシュで定義し、レシーバの配列から条件に合致する値のみを追加したハッシュを返す処理を行っています。初期値を配列にすれば、結果を配列で返すことも可能です。

array = (1..10).to_a.reduce({}) do |arr, item |
  arr << item if item % 2 == 0
  arr
end

p array
#=>{2=>true, 4=>true, 6=>true, 8=>true, 10=>true}

工夫次第で、配列周りの処理を簡潔に記述できそうですね。

参考URL

reduceやinjectという名称と処理のイメージが中々結び付かなかったのですが、以下のURLの記事の説明がなかなか分かりやすかったです。
Rubyist Magazine - map と collect、reduce と inject ―― 名前の違いに見る発想の違い

Rubyで多重ループを抜ける方法

Rubyの大域脱出に関するメモ。

ネストが深いループから何かの条件で一気に抜けたい場合、Rubyではcatch-throwを使うのが適切なようです。

書き方

以下が大域脱出のサンプル。如何にもサンプルの為のサンプルという感じですが、ネストしたループから抜けているのがお分かりいただけるかと。

catch(:break_loop) do
  (1..5).each do |x|
    (1..5).each do |y|
      puts "x=%d, y=%d" % [x,y]
      throw :break_loop  if x * y > 10
    end
  end
end

実行結果

x=1, y=1
x=1, y=2
x=1, y=3
x=1, y=4
x=1, y=5
x=2, y=1
x=2, y=2
x=2, y=3
x=2, y=4
x=2, y=5
x=3, y=1
x=3, y=2
x=3, y=3
x=3, y=4

JavaC++に慣れた人だと、catch節には例外処理を書くものだというイメージがあったりするのですが、Rubyの場合はその辺は切り離して考えたほうが良さそうです。

オブジェクトを返すこともできます

catch内部に定義した変数を返却する事も可能。こういう書き方を覚えておくと何かの時に役に立つのかもしれません。

(a,b,c) = catch(:break_loop) do
  (1..20).each do |x|
    (1..20).each do |y|
      (1..20).each do |z|
        throw(:break_loop, [x,y,z])  if x * y * z > 1000
      end
    end
  end
end
puts "a=%d, b=%d, c=%d" % [a,b,c]#=>a=3, b=17, c=20

雑感

RubyはGOTO文がありませんので、上の例以外に一気にネストを抜ける為には例外をraiseするか、メソッドに分割してreturnする方法ぐらいしかありませんね。

Rubyのヒアドキュメントを使ってみる

Rubyのヒアドキュメントに関するメモ。文字列を扱うちょっとしたプログラムで結構使えます。

ヒアドキュメントとは

普通の文字列リテラルはデリミタ(", ', ` など)で囲まれた 文字列ですが、ヒアドキュメントは `<<識別子' を含む行の次の行から `識別子' だけの行の直前までを文字列とする行指向のリテラルです。

https://docs.ruby-lang.org/ja/latest/doc/spec=2fliteral.html#here

ヒアドキュメントを使うメリットとして、

  • 複数行の文章を変数で扱う場合、コード上にそのまま記述可能。
  • ダブルコーテーション、シングルコーテーションを含む文字列もエスケープ無しで記述可能。

があります。

ヒアドキュメントの書き方

一口にヒアドキュメントといっても、色んな書き方があるのでまとめてみます。

基本

下の例はEOSを識別子としています。慣例的にEOSまたはEOFを使うことが多いようですが、開始と終了の識別子が合っていればなんでもかまいません。

puts <<EOS
"Hello World!"
EOS
#=>"Hello World!"
式展開

ヒアドキュメントは、通常の文字列と同じく式展開が可能です。シングルコーテーションで開始の識別子を囲むと式展開はされません。

name = "Taro"
puts <<"STR1"
Hello! #{name}
STR1
#=>Hello! Taro

puts <<'STR2'
Hello! #{name}
STR2
#=>Hello! #{name}
インデント

通常は終了の識別子を行頭に書かないとエラーになりますが、識別子の前にハイフンをつけると、終了の識別子をインデントできます。

3.times do
  puts <<-EOS
    Hello World!
  EOS
end
#=>    Hello World!
#=>    Hello World!
#=>    Hello World!

但し、上の例では余計なインデントがヒアドキュメントに含まれてしまいます。Ruby2.3以降ではチルダをつけることで、余計なインデントを除去してくれます。

3.times do
  puts <<~EOS
    Hello World!
  EOS
end
#=>Hello World!
#=>Hello World!
#=>Hello World!
コマンド実行

以下のように書くことでコマンド実行ができます。Windowsで動作確認済み。

puts <<`ENV`
env 
ENV

SQLなんかを扱うのに便利

個人的に良く使う例として、SQLのようなダブルコーテーション、シングルコーテーションがある文字列を扱うのに便利なので、複数のinsert文やselect文を生成したい時に使います。

s =<<STR1
0001
0002
0003
0004
0005
STR1
s.split.each do |str1|
  [1,2].each do|num1|
    puts <<~SQL
      select * from table where col1 = "#{str1}" and col2 = #{num1};"
    SQL
  end
end

実行結果

select * from table where col1 = "0001" and col2 = 1;"
select * from table where col1 = "0001" and col2 = 2;"
select * from table where col1 = "0002" and col2 = 1;"
select * from table where col1 = "0002" and col2 = 2;"
select * from table where col1 = "0003" and col2 = 1;"
select * from table where col1 = "0003" and col2 = 2;"
select * from table where col1 = "0004" and col2 = 1;"
select * from table where col1 = "0004" and col2 = 2;"
select * from table where col1 = "0005" and col2 = 1;"
select * from table where col1 = "0005" and col2 = 2;"

CodeIQ 「ロンリー・ルーク」問題の解答コード公開

久々の投稿になります。
今回はCodeIQの問題の解答コードを公開します。

codeiq.jp

問題

今回の問題の概要です。

  • 自然数 n, k に対し、縦横 n×n のマス目にチェスのルークの駒を k 個配置します。このとき、自身から見て上下方向・左右方向のいずれにも他の駒が存在しないような駒を「はぐれルーク」と呼びます。
  • 1 つのマスに 2 個以上の駒を置かないよう、ランダムに駒を配置します。このとき、はぐれルークの個数の期待値を F(n, k) と定義します。
  • 自然数 n, m に対し、1 ≦ k ≦ m の範囲の自然数 k に対する F(n, k) の和を G(n, m) と定義します。
  • 1000*G(n, m)の整数部分の値を出力してください。

方針

F(n, k)について、k=1~mまでの和を求めるので、F(n,k)の値の求め方を考えます。

  • k=1の場合、「はぐれルーク」は1個なので期待値は1
  • k > n-1の2乗+1の場合、どう配置しても「はぐれルーク」は無いので期待値は0
  • kの値が上記以外の場合について、全配置の組み合わせについて「はぐれルーク」の個数を計算

まあ、要はしらみつぶしというやつですww

解答

以下が、提出したコード。n×n の盤面を1次元配列で表現しているのが多少の工夫といえば工夫かも。

def func(n, k)
  return 1.0 if k == 1
  return 0.0 if ((n - 1) ** 2 ) + 1 < k
  numOfLonelyLuke = 0
  numOfCombination = 0
  (0..(n**2 - 1)).to_a.combination(k) do |array|
    numOfCombination += 1
    array.each do |x|
      isLonely = true
      array.each do |y|
        next if x == y
        if (x / n == y / n) || (x % n == y % n)
          isLonely = false
          break;
        end
      end
      numOfLonelyLuke += 1 if isLonely
    end
  end
  numOfLonelyLuke / numOfCombination.to_f
end
(n, m) = gets.split.map(&:to_i)
num = 0.0
(1..m).each do |k|
  num += func(n, k)
end
puts (num *1000).to_i

感想

今までもCodeIQの問題は解いてましたが、公開するのは今回が初めてです。
また、この機会に他の方の解答コードを見てみましたが、エレガントな解法で実装されてる方が結構いらっしゃったので驚きでした。
次はもう少し綺麗な解き方を目指すようにしないとなー。

ま、自分もまだまだ精進が必要だなーと感じ入りました。ほんと。(´Д`)