酒と泪とRubyとRailsと

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

アルゴリズムの勉強: オリジナルの数値フォーマットの加算[AOJ 1137][Ruby/Python][文字列操作]

引き続きプログラミングの基礎体力づくりと、Pythonの勉強を兼ねてアルゴリズムを勉強中です。今回は『カッコが閉じているかのチェック』について勉強しました。AIZU Online Judgeで対応している問題は、『Numeral System』です。ごくごく初歩的な問題ですが、いかに戦略を立てて素早く解くかを意識するとまた楽しくなってきます。


サンプル問題(AOJ)

Numeral System
Aizu Online Judge。”m”,”c”,”x”,”i” の4個の文字と “2”,”3”,”4”,”5”,”6”,”7”,”8”,”9” の8個の数字を 使った整数値の新しいフォーマットの加算と結果表示をする。

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
30
31
32
33
34
35
36
DICT = { 'm' => 1000, 'c' => 100, 'x' => 10, 'i' => 1 }.freeze

def mcxi_to_digit(s)
  sum = 0
  DICT.each do |k, v|
    if s.include?(k)
      if s[s.index(k)-1] >= '2' and s[s.index(k)-1] <= '9'
        sum += s[s.index(k)-1].to_i * v
      else
        sum += v
      end
    end
  end
  return sum
end

def digit_to_mcxi(n)
  str = ''
  DICT.to_a.map do |k, v|
    val = n/v
    n = n%v
    if val >= 2
      str += "#{val}#{k}"
    elsif val == 1
      str += k
    end
  end
  return str
end

n = gets.to_i
n.times do
  a, b = gets.chomp.split(' ')
  sum = mcxi_to_digit(a) + mcxi_to_digit(b)
  puts digit_to_mcxi(sum)
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
24
25
26
def mxciToDegit(s):
  dict = {'m': 1000, 'c': 100, 'x': 10, 'i': 1}
  sum = 0
  for c in dict:
    if c in s:
      if "2" <= s[s.index(c)-1] <= "9":
        sum += int(s[s.index(c)-1])*dict[c]
      else:
        sum += dict[c]
  return sum

n = int(raw_input())
for i in range(n):
  a, b = raw_input().split()
  sum = mxciToDegit(a) + mxciToDegit(b)

  st = ""
  list =((1000, "m"), (100, "c"), (10, "x"), (1, "i"))
  for d, c in list:
    val = sum/d
    if val >= 2:
      st += str(val) + c
    elif val == 1:
      st += c
    sum = sum%d
  print st

Aizu Online Judgeのサンプルソース

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

morizyun/aoj-ruby-python - GitHub

最近解いたAOJの問題

AOJタグのついた最近解いた問題一覧

おすすめの書籍