酒と泪とRubyとRailsと

Ruby on Rails と Objective-C は酒の肴です!

『アルゴリズムのキホン』を読みました & AOJでやってみた!【書評】

半年ほど前に読んだ『アルゴリズムのキホン』を再勉強も兼ねて読みなおしています。プログラミングの基礎力を高めるのが今の目標なので徹底的に頑張ります!

ちなみに、アルゴリズム系を勉強するときにオススメなのが、会津大学が提供している『Aizu Online Judge』です。日本語の問題も多数ありますし、基本的なところからスタートできるので導入としてはすごくおすすめです。 また、新しい言語を勉強するときににも、パズルをとくような感覚で勉強していけるのですごくいい練習になると思います!

(05-01 20:50) ポーカーの手札の解法を追加


データ構造

ハッシュテーブル

データを入力値としたハッシュ関数により得られる値が、ルート配列の要素番号となる

データ構造

1) ルート配列と呼ばれる要素数Nの配列
2) ルート配列の要素を先頭ポインタとするリスト => ルート配列の各要素がデータを管理

アルゴリズム

ユークリッドの互除法

概要

ユークリッドの互除法 - Wikipedia

Rubyで最小公倍数を求める

サンプル問題(AOJ)

GCD and LCM - Aizu Online Judge
Aizu Online Judgeの最大公約数(GCM: the greatest common divisor)と、最小公倍数(LCM: least common multiple)を求める問題。

Rubyのサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Array
  # 最大公約数: 2つ以上の正の整数に共通な約数(公約数)のうち最大のもの
  def lcm
    self.inject do |a, b|
      a*b/self.gcd
    end
  end

  # 最小公倍数: 2つ以上の正の整数の共通な倍数(公倍数)のうち最小のもの
  # ユークリッドの互除法
  def gcd
    self.inject do |a, b|
      while b > 0
        a, b = b, a if a < b
        a, b = b, a%b
      end
      return a
    end
  end
end

while str = gets
  a = str.split(' ').map(&:to_i)
  puts "#{a.gcd} #{a.lcm}"
end

# output
# 2 24
# 10000000 150000000

Pythonのサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# coding:utf-8
import sys

# 最大公約数
def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

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

for s in sys.stdin:
  a, b = map(int,s.split())
  gcd_num = gcd(a, b)
  lcm_num = lcm(a, b)
  print "%d %d"%(gcd_num, lcm_num)

# output
# 2 24
# 10000000 150000000

エラトステネスの篩(ふるい)

概要

エラトステネスの篩 - Wikipedia

サンプル問題(AOJ)

Prime Number - Aizu Online Judge
Aizu Online Judgeの6 桁以下の素数を求める問題。

Ruby ソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
n = 1000000

# エラトステネスの篩
# 指定された整数以下の全ての素数を見つける
ns = (n**0.5).to_i + 1
is_prime = [false, false] + [true]*(n-1)
2.upto(ns) do |i|
  next if !is_prime[i]
  (i*i).step(n, i) do |j|
    is_prime[j] = false
  end
end

count = 0
list = (0..n).map do |i|
  count += 1 if is_prime[i]
  count
end

while gets
  puts list[$_.to_i]
end

Python のサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from bisect import bisect

n = 1000000
sn = int(n**0.5)+1

num = [False, False] + [True]*(n-1)
for i in xrange(2, int(n**0.5)+1):
  if num[i]:
    for j in xrange(i**2, n, i):
      num[j] = False
prime = [i for i in xrange(2, n) if num[i]]

while True:
  try:
    print bisect(prime, input())
  except:
    break

動的計画法

概要

動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる

サンプル問題(AOJ)

A First Grader
Aizu Online Judge。動的計画法を使って数式のパターン数を計算する問題。

Rubyサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = gets.to_i
arr = gets.split(' ').map(&:to_i)
answer = arr[n-1]

dp = Array.new(n).map { Array.new(21, 0) }
dp[0][arr[0]] = 1
1.upto(n-2) do |i|
  0.upto(20) do |j|
    next if dp[i-1][j] == 0
    vp = j + arr[i]
    vm = j - arr[i]

    dp[i][vp] += dp[i-1][j] if vp <= 20
    dp[i][vm] += dp[i-1][j] if vm >= 0
  end
end

puts dp[n-2][answer]

Python サンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = input()
arr = map(int, raw_input().split())
answer = arr[n-1]

dp = [[0]*21 for i in range(n)]
dp[0][arr[0]] = 1

for i in range(1, n-1):
  for j in range(21):
    if dp[i-1][j] == 0: continue
    vp = j + arr[i]
    vm = j - arr[i]

    if vp <= 20:
      dp[i][vp] += dp[i-1][j]
    if vm >= 0:
      dp[i][vm] += dp[i-1][j]

print dp[n-2][answer]

ポーカーの手札から役を求める

サンプル問題

Poker Hand
ポーカーの手札から役を答える問題。そんなに難しくない問題なので頭の体操にピッタリ!

Rubyのサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
while s = gets do
  cards = s.split(',').map(&:to_i)
  card_count = Array.new(13){0}
  cards.each { |c| card_count[c-1] += 1 }
  str = card_count.join
  card_count.delete(0)

  scr = 'null'
  case card_count.sort
    when [1,4]
      scr = 'four card'
    when [2,3]
      scr = 'full house'
    when [1,1,1,1,1]
      scr = 'straight' if str =~ /1{5}/ or str =~ /10{8}1{4}/
    when [1,1,3]
      scr = 'three card'
    when [1,2,2]
      scr = 'two pair'
    when [1,1,1,2]
      scr = 'one pair'
  end
  puts scr
end

Pythonのサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
for s in sys.stdin:
  hand = sorted(map(int, s.split(',')))
  kind = len(set(hand))
  ma = max([hand.count(i) for i in hand])

  ans = 'null'
  if kind == 4:
    ans = 'one pair'
  elif kind == 3:
    if ma == 2:
      ans = 'two pair'
    else:
      ans = 'three card'
  elif kind == 2:
    if ma==4:
      ans = 'four card'
    else:
      ans = 'full house'
  else:
    if hand == [1,10,11,12,13] or (hand[4] - hand[0]) == 4:
      ans = 'straight'
  print ans

Aizu Online Judgeのサンプルソース

当面はAOJを解きながら、アルゴリズムの再勉強をしていくつもりです。Ruby/PythonでのAOJの回答は下のリポジトリに保存しておきます。もしツッコミとかあれば是非^^

morizyun/aoj-ruby-python - GitHub

変更来歴

(04-29 14:55) 動的計画法の解法を追加
(05-01 20:50) ポーカーの手札の解法を追加

おすすめの書籍