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

猫尾製作所

あまりアテにしないでね

連分数展開の逆操作を行う

数学 連分数

連分数展開  [ a_0, a_1, a_2, \cdots , a_n ] が与えられたとします。それを単一の分数に直す計算は単純な手計算では大変面倒です。ですが、次のような漸化式でもって  [ a_0, a_1, a_2, \cdots , a_n ] の 途中までの連分数展開  [ a_0, a_1, a_2, \cdots , a_k ] ( k \le n ) を単一の分数  p_k / q_k に直したときの  p, q の値が計算できます。

 p_0 = a_0,  p_1 = a_1 a_0 + 1,  p_n = a_n p_{n-1} + p_{n-2} (n \ge 2),
 q_0 = 1,  q_1 = a_1,  q_n = a_n q_{n-1} + q_{n-2} (n \ge 2).

それを利用して、有限連分数を単一の分数に変換するプログラムを Ruby で今朝方、書きました。

# 引数の個数
len = ARGV.length

# 引数が与えられていなければ異常終了
if len == 0 then
	puts "Please give one or more integers."
	exit -1
end

# 引数 {a} を整数に変換
a = Array.new()
for k in 0..(len-1) do
	a[k] = ARGV[k].to_i
end

# p, q を用意
p = Array.new()
q = Array.new()

# k = 0 のとき
if len >= 1 then
	p[0] = a[0]
	q[0] = 1
end

# k = 1 のとき
if len >= 2 then
	p[1] = a[1] * a[0] + 1
	q[1] = a[1]
end

# k ≧ 2 のとき
if len >= 3 then
	for k in 2..(len-1) do
		p[k] = a[k] * p[k-1] + p[k-2]
		q[k] = a[k] * q[k-1] + q[k-2]
	end
end

# 最終的な結果
p = p[len-1]
q = q[len-1]

puts "Result = #{p} / #{q}"
exit 0

使い方は引数に  a_0 から順に  a_i を入力していくだけです。

[1, 2, 3, 2, 4, 5] に対しては

% ruby fractional.rb 1 2 3 2 4 5
Result = 533 / 371

といった具合です。

しかし、当然ながらあくまでも有限連分数しか扱えません。連分数展開は私のお気に入りになってしまっているので、今後もまた連分数に関する記事を書いていくことにしますね。今日のこの記事が基点となるかも。

興味深い書籍が、今年5月のブルーバックスの新刊の中にあります。私ももちろん所有しております(けれども、あまりよみすすめていない)

連分数のふしぎ (ブルーバックス)

連分数のふしぎ (ブルーバックス)