プログラム解説：CodeIQ「連分数の足し算」

問題の概要

問題を引用します。

【概要】連分数の足し算をしてください。
足し算の結果も、連分数にしてください。

【入出力】
入力は
[7;3,5,9]+[4;6,8]
こんな感じです。
この入力が右図の左辺にある足し算に対応しています。

出力は、
[11;2,10]
のような感じです。足し算の結果は右図の右辺の通りになりますので、これを入力と同じような形式の文字列にしてください。
末尾の改行はあってもなくても構いません。

【例】

入力出力

[7;3,5,9]+[4;6,8] [11;2,10]

[2;1,1,1,5]+[3;2,1,5] 6

【補足】
2つの連分数を足す問題しか出ません。
入力の連分数内の各項は一桁、項数は2以上8以下です。
出力の連分数内の各項は、一桁とは限りませんが、全て正の整数になります。
最初の区切り文字だけセミコロンで、残りはコンマです。
足し算の結果がぴったり整数になる場合は「6」のように、括弧などはつけずに出力してください。
不正な入力に対処する必要はありません。
連分数についてはWikipediaの記事が参考になるかもしれません（ならないかもしれません）。

入力	出力
[7;3,5,9]+[4;6,8]	[11;2,10]
[2;1,1,1,5]+[3;2,1,5]	6

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

# 連分数を普通の分数に直す
def parse(line)
	c, other = line.sub("[", "").sub("]", "").split(";")
	arr = other.split(",").map{|i| i.to_i}

	arr.unshift(c.to_i)

	arr_p = []
	arr_q = []

	# k = 0
	if arr.size >= 1 then
		arr_p[0] = arr[0]
		arr_q[0] = 1
	end

	# k = 1
	if arr.size >= 2 then
		arr_p[1] = arr[1] * arr[0] + 1
		arr_q[1] = arr[1]
	end

	# k >= 2
	if arr.size >= 3 then
		for k in 2...arr.size
			arr_p[k] = arr[k] * arr_p[k-1] + arr_p[k-2]
			arr_q[k] = arr[k] * arr_q[k-1] + arr_q[k-2]
		end
	end

	return Rational(arr_p.last, arr_q.last)
end

# 普通の分数を連分数に直す
def getResult(r)
	a = r.numerator
	b = r.denominator

	if b == 1 then return a.to_s end

	arr_a = [a/b]	# 整数部分
	arr_b = [b]		# 分母
	arr_c = [a%b]	# 余り

	i = 1
	begin
		arr_b[i] = arr_c[i-1]
		arr_a[i] = arr_b[i-1] / arr_b[i]
		arr_c[i] = arr_b[i-1] % arr_b[i]
		i += 1
	end while arr_c.last > 0

	return formatResult(arr_a)
end

# 連分数の書式を整える
def formatResult(arr)
	str = "["
	str += arr.shift.to_s + ";"
	str += arr.join(",") + "]"
	return str
end

# main
while line = gets
	line.strip!
	if line.empty? then next end

	a,b = line.split("+")
	r = parse(a)+parse(b)
	puts getResult(r)
end

解説

★★の問題ですが結構難しいです。
Wikipediaの記事は参考になりますが、私はもう少し噛み砕いた説明をWebで探しました。

考え方

入力の連分数を普通の分数に直して足し算し、結果を再度連分数にする必要があることはすぐわかるでしょう。なので、大きく分けて連分数→普通の分数、分数の足し算、普通の分数→連分数の3つの処理が必要です。
ただし、RubyにはRationalがあるので分数の足し算は自力で実装する必要がありません。
連分数→普通の分数もRationalを使ってやってみたのですがうまくいかなかったので自力で実装しました。

parse()

入力値の文字列（連分数）を普通の分数にする処理です。
Wikipediaの記事の「連分数の性質」の部分をプログラムにしたものです。
Wikipediaの式の
　[a₀,a₁,a₂,…,a_n-1]がarr、
　[p₀,p₁,p₂,…,p_n]がarr_p、
　[q₀,q₁,q₂,…,q_n]がarr_q、
に相当します。
あとはWikipediaの式の通り、
　k=0の時にarr_p[0] = arr[0], arr_q[0] = 1
　k=1の時にarr_p[1] = arr[1] * arr[0] + 1, arr_q[1] = arr[1]
として、それ以降の項は
　arr_p[k] = arr[k] * arr_p[k-1] + arr_p[k-2]
　arr_q[k] = arr[k] * arr_q[k-1] + arr_q[k-2]
として計算するだけです（なんの説明にもなっていない ^^;)。
結果はRationalにして返します。

getResult()

普通の分数を連分数にします。
変数aは分子、bは分母です。

分母が1の場合は計算の必要もありませんし、出力形式が連分数の場合と違うので先に処理してしまいます（41行目）。

分数を連分数に直す処理もWikipediaの「連分数の計算方法」の通りですが、私はこのサイトを参照しました。参考にしたサイトの通りですがコードの説明をします。

参照したサイトと同じく36/11の場合を例に説明します。
まず、a=36, b=11です。
arr_a[0]はa/bの商で3になります。arr_b[0]はbなので11、arr_c[0]はa/bの余りなので3になります。これは何を意味しているかというと、
36/11 = a[0]+c[0]/b[0] = 3+3/11を表します。

次に、c[0]/b[0] = 3/11を処理しなければならないのですが3/11 = 1/(11/3) = 1/(3+2/3)という風にします。
この時11/3の分母はarr_c[0]なのでarr_b[1] = arr_c[0]です。
そして、arr_a[1] = arr_b[0] / arr_b[1]、arr_c[1] = arr_b[0] % arr_b[1]となります。
これを一般化すると49〜51行目のようになります。

余りが0になった場合、それ以上処理は続けられないのでループを終了します（53行目）。
最終的にarr_aが連分数を表しますが、最初の項だけ「;」で区切られるので書式を整える必要があります。それをformatResult()で行います（簡単だし本質に無関係なので説明しません）。

雑感

高校の数学で連分数はやったのですが、計算が面倒臭いので余り好きではなかったことを思い出しました。
プログラムにするのも結構面倒臭いです。
どうでもいいことですが、この問題が出題された時には出題を見落としていて1月あまり経ってから全ての問題を見たらやっていないことを発見して回答したという経緯があります。出題されている問題に追いついてからは全ての（プログラミングの）問題をやっているため先頭の数問しかチェックしていなかったのですが、気づかないうちに後ろに流れてしまっていたようです。

CodeIQ：連分数の足し算

問題の概要

私のプログラム

解説

考え方

parse()

getResult()

雑感