CodeIQ：円周率に近似できる分数

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「円周率に近似できる分数」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

分母、分子ともに整数の分数を使って円周率に近似することを考えます。
小数第 n 位までが円周率と一致するもののうち、分母が最小のものをπ(n)とします。

例えば、n = 1 のとき、π(1) = 19/6 = 3.166…、
n = 2 のとき、π(2) = 22/7 = 3.1428…、
n = 3 のとき、π(3) = 245/78 = 3.14102…
となります。

標準入力から n が与えられたとき、π(n) の分母を求め、標準出力に出力してください。
なお、nは11以下の正の整数とします。
参考）小数点以下11桁までの円周率は以下の通りです。
3.14159265358

【入出力サンプル】
標準入力

2

標準出力

7

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def solve(r)
	pi_s = "3.14159265358"
	pi = pi_s[0,2+r].to_f

	n = 6
	while true
		m = (pi * n).ceil
#		printf("pi=%f, m=%d, n=%d, m/n=%d, pi*10**%d=%d\n", pi, m, n, (m * 10**r)/n, r, (pi * 10**r).floor)

		if (m * 10**r)/n == (pi * 10**r).floor then
			return n
		end

		n += 1
	end
end

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

	p solve(line.to_i)
end

解説

あまり難しくはありません。単純に順番にやっていけばできます。

考え方

考え方は非常に単純です。
例えば3.14（小数点以下2桁）の場合だとfloor(10²*ceil(3.14*x)/x)=10²*3.14となるxを探せば良いというだけです。

main

入力値を数値にしてsolve()に渡し、結果を印字します。

solve(r)

定数pi_sは円周率小数点以下11桁までの文字列表現です。
piはr桁までの円周率（浮動小数点）です。

問題から分母はn=6から始めれば良いことがわかります。
あとはnを1ずつ増やしながら考え方の通りにチェックし、見つかったところでそのnを返すだけです。

雑感

O(n)なのであんまり効率良くありません。
問題を見た時から答えはそれほど大きな桁にならなそうだったのでこれでやってしまいましたが、もっと効率良く探す方法がありそうです。