『遠山啓エッセンス〈6〉中学・高校の数学教育』を読んでいます．年末までに第1〜5巻を読み終えていて，年が明けてから先に第7巻を通読し，第6巻がシリーズ最終となります．
この序盤(p.15)に，面白い記述を見つけました．
割り算をこのように重ねれば*1，互除法の計算ができること，それと，割り算の筆算記号の「曲げて書くやつ*2」が閉じ括弧で表現できること．2つとも，言われてみればその通りです．
さっそくコーディングです．
#!/usr/bin/env ruby # -*- coding: utf-8 -*- # dop.rb : 割り算の筆算(division on paper) # 筆算の除算 # ruby dop.rb 345 12 # ruby dop.rb -l 345 12 # 筆算の除算を応用した最大公約数計算(遠山啓エッセンス第6巻pp.15-16) # ruby dop.rb -g 36 14 # ruby dop.rb -g 259 189 # ruby dop.rb -g 1024 864 # オプションの違いが分かる例 # ruby dop.rb 1545 12 # ruby dop.rb -l 1545 12 # ruby dop.rb -g 1545 12 # ruby dop.rb -g -l 1545 12 require "optparse" class DivisionOnPaper class Line def initialize(i = 0, b = "", opt = {}) @indent = i # 字下げ幅 @body = b # 本体 if opt[:right] @indent -= @body.length raise "right justification error" if @indent < 0 end @over = opt[:over] # 上に引く横線．nilはなし，trueは自動，Rangeで範囲指定 @under = opt[:under] # 下に引く横線．nilはなし，trueは自動，Rangeで範囲指定 # 工夫すれば消去できそう end attr_accessor :indent, :body, :over, :under def to_s " " * @indent + @body end def length @indent + @body.length end def to_range (@indent...length) end def make_line(r) case r when Range # do nothing when true r = to_range else return "" end " " * r.first + "-" * (r.last - r.first) + "\n" end def make_line_over make_line(@over) end def make_line_under make_line(@under) end end class DivMod # s = DivisionOnPaper::DivMod.new(1545, 12) # s.q == 1 # s.qn == 12 # s.r == 34 # s.qn_shift == 2 # 「15」の下に「12」と書く際，左にシフトする桁数 # s.r_shift == 1 # 引き算して「34」と書く際，左にシフトする桁数 # s.q_true == 100 # s.qn_true == 1200 # s.r_true == 345 ######### # 1 # ----- # 12)1545 # 12 # --- # 34 attr_accessor :q, :r, :qn, :qn_shift, :r_shift, :q_true, :qn_true, :r_true def initialize(dividend, divisor) q_tmp = dividend / divisor @qn_shift = q_tmp.to_s.length - 1 qn_pow10 = 10 ** @qn_shift @q = q_tmp / qn_pow10 @qn = @q * divisor @q_true = @q * qn_pow10 @qn_true = @qn * qn_pow10 @r_true = dividend - qn_true q_tmp2 = @r_true / divisor @r_shift = q_tmp2.to_s.length - 1 r_pow10 = 10 ** @r_shift @r = @r_true / r_pow10 end end def initialize(n1, n2, opt = {}) @num1 = n1 # 被除数 @num2 = n2 # 除数 @line_a = [] # 出力情報．DivisionOnPaper::Lineインスタンスのリスト @opt_lump = opt[:lump] # 除算詳細非表示オプション @opt_gcd = opt[:gcd] # 最大公約数計算オプション raise "invalid dividend" if @num1 <= 0 raise "invalid divisor" if @num2 <= 0 end def to_s @line_a.map do |line| line.make_line_over + line.to_s + "\n" + line.make_line_under end.join end def do_divide(num1 = @num1, num2 = @num2) # メソッド内でnum1, num2の値は変わらない # 除数)被除数 body = "%d)%d" % [num2, num1] if @line_a.empty? # 最初の除算 lineno_quotient = -1 column_right = body.length @line_a << Line.new(0, body, :over => ((num2.to_s.length)...(body.length))) else # 2回目以降最初の除算 lineno_quotient = @line_a.length - 1 line = @line_a[lineno_quotient] indent = line.indent column_right = indent + body.length line.body = body # 横線処理(underを消せれば，もっと楽できそうなのだが) if @opt_lump if lineno_quotient >= 1 r = @line_a[lineno_quotient - 1].under @line_a[lineno_quotient - 1].under = nil else r = nil end else r = line.over end if Range === r line.over = ((r.first)...column_right) else line.over = (indent...column_right) end @line_a[lineno_quotient] = line end if @opt_lump # 詳細な(桁に注意した)割り算は不要 q, r = num1.divmod(num2) qn = num2 * q @line_a << Line.new(column_right, "%d" % qn, :under => ((column_right - num1.to_s.length)...(column_right)), :right => true) @line_a << Line.new(column_right, "%d" % r, :right => true) else # 詳細な(桁に注意した)割り算を実施 n1 = num1 while n1 >= num2 s = DivMod.new(n1, num2) $stderr.puts s.inspect if $DEBUG @line_a << Line.new(column_right - s.qn_shift, "%d" % s.qn, :right => true) @line_a << Line.new(column_right - s.r_shift, "%d" % s.r, :over => ((column_right - n1.to_s.length)...(column_right - s.r_shift)), :right => true) n1 = s.r_true end end # (最終的な)商 if lineno_quotient < 0 @line_a.unshift(Line.new(column_right, "%d" % num1.div(num2), :right => true)) else q = num1.div(num2) spc = num1.to_s.length + 1 - q.to_s.length @line_a[lineno_quotient - 1].body += " " * spc + "%d" % q end end def calc_gcd num1, num2 = @num1, @num2 if num1 < num2 puts "(swapped)" num1, num2 = num2, num1 end while num2 > 0 do_divide(num1, num2) num1, num2 = num2, num1 % num2 end end def start if @opt_gcd calc_gcd else raise "divident is smaller than divisor" if @num1 < @num2 do_divide end print self.to_s end end if __FILE__ == $0 op = OptionParser.new opt = {} op.on("-l", "--lump", "division in a lump") {opt[:lump] = true} op.on("-g", "--gcd", "calculation for greatest common divisor") {opt[:gcd] = true} op.parse!(ARGV) dividend = (ARGV.shift || 345).to_i divisor = (ARGV.shift || 12).to_i DivisionOnPaper.new(dividend, divisor, opt).start end
小学校で学ぶ，割り算の筆算も，できるようにしました．《割り算の筆算》というPDFファイルによると，これは長除法と呼ばれるそうです．
デフォルトはこの割り算とし，コマンドラインオプションで，「途中の計算を書かない」「最大公約数を求める」を指定できるようにしました．ソースファイル先頭に書いた実行例で，出力は以下のようになります．
$ ruby dop.rb 1545 12
128
-----
12)1545
12
---
34
24
---
105
96
---
9
$ ruby dop.rb -l 1545 12
128
-----
12)1545
1536
----
9
$ ruby dop.rb -g 1545 12
128
-----
12)1545
12
---
34
24
---
105
96 1
------
9)12
9 3
----
3)9
9
-
0
$ ruby dop.rb -g -l 1545 12
128
-----
12)1545
1536 1
-------
9)12
9 3
----
3)9
9
-
0コードはすらすら書けたわけではなく，悪戦苦闘の連続でした．主要なものを挙げてみると：
- 数値情報を文字列として配列（ただし，文字列の配列ではなくDivisionOnPaper::Lineインスタンスの配列として）で保持し，横線はその文字列の上か下につけるようにしましたが，-gと-lを同時に指定したときには，横線が2重に出力されてしまうことに気づき，泥臭い方法で対処しました．
- DivisionOnPaper::DivModクラスにコメントとして書きましたが，「ある桁で商を立てて引き算する」という1回の操作で，どのような情報を求めればよいかについて，時間をかけて検討しました．実は，そこに書かれているインスタンス変数のうちいくつかは，本体（DivisionOnPaperクラス内）で使われていませんが，検算しやすくするために記載しています．
- 2つの数の大小にも，注意を払わないといけません．具体的には，被除数が除数よりも小さいときですが，-gオプションがないときは，"divident is smaller than divisor"という出力で例外を出して終了し，-gオプションがあるときは，値を交換してから割り算を始めるようにしました．
書籍の例題も，確認しておきましょう．
$ ruby dop.rb -g 36 14
2
---
14)36
28 1
-----
8)14
8 1
----
6)8
6 3
---
2)6
6
-
0
$ ruby dop.rb -g 259 189
1
----
189)259
189 2
-------
70)189
140 1
------
49)70
49 2
-----
21)49
42 3
-----
7)21
21
--
0ちなみに最大公約数は，最後の「)」のすぐ左の数となります．36と14の最大公約数は2，259と189に対しては7です．
数値はすべて合っています．横線はいくつか違っているところがあるのですが，自分のコードの出力のほうが，一貫性がとれています．
*1:『ハシゴ式にすると』と書かれています．個人的にはハシゴよりも，階段を連想するのですが．
*2:正式名称は…割算の筆算で使う漢字の厂垂れの様な記号?の正式名称は何というのですか? - 正... - Yahoo!知恵袋．へえ．
