或るプログラマの開発日記

日々の勉強したことの備忘録なんかに使っていきます

CodeIQ 「タンジェント・フラクション」問題解答コード

CodeIQ問題の解答公開記事です。
codeiq.jp

問題の概要

今回は以下のような問題でした。

  • 0 < \alpha < \beta < \pi/2を満たす実数\alpha,\betaの組について、tan(\alpha),tan(\beta),tan(\alpha+\beta)がすべて単位分数(分母が自然数、分子が 1 )となるものを考えます。(\alpha,\betaの単位はラジアン)
  • 正の実数{m}に対し、{m\leqq\alpha+\beta}の範囲で題意を満たす{\alpha,\beta}の組の個数を{F(m)}と定義します。
  • 正の実数 m(0.001 < m < 1)が与えられた時のF(m)の値を出力しなさい。

方針

この問題を解くためには、以下の三角関数の公式を使います。

tan(\alpha+\beta) = \displaystyle \frac{tan(\alpha)+tan(\beta)}{1-tan(\alpha)tan(\beta)}

題意から、tan(\alpha),tan(\beta)はそれぞれ単位分数となるので、a,b自然数とした時に、それぞれ\displaystyle \frac{1}{a},\displaystyle \frac{1}{b}とあらわす事が出来ます。これを先の公式に当てはめると、

tan(\alpha+\beta) = \displaystyle \frac{\displaystyle \frac{1}{a}+\frac{1}{b}}{1- \displaystyle \frac{1}{ab}} = \displaystyle \frac{a+b}{ab-1}

となります。

というわけで、tan(m) \le \displaystyle \frac{a+b}{ab-1} を満たし、且つ右辺が単位分数になるような自然数a,bの組み合わせの数を算出すれば良いと言う事になります。

解答コード

こちらが提出したコードになります。

class Codeiq3182
  def solve(m)
    cnt = 0
    tan_m = Math.tan(m)
    max_b = (1 / Math.tan( m / 2.0 )).to_i
    (2..max_b).each do |b|
      i=((b**2 -1).to_f / (2 * b).to_f).ceil
      (i..(b-1)).each do |n|
        (a, r) =  ((n*b) + 1).divmod(b-n)
        next if  (r != 0)
        tan_ab = (a + b).to_f / ((a * b) -1)
        break if(tan_ab < tan_m)
        cnt += 1
      end
    end
    return cnt
  end
end
puts Codeiq3182.new.solve(gets.to_f)

\displaystyle \frac{a+b}{ab-1}が単位分数になるので、n自然数とした時に
\displaystyle \frac{n(a+b)}{ab-1} = 1が成り立つ自然数a,b,nの組を求める方法で解いています。
上記の式を組み変えると、\displaystyle a = \frac{nb+1}{b-1}になるので、右辺を実際に計算して余り0になるb,nの組み合わせの数をカウントしてます。
bの値を定義した時、aの値が計算上1以上になるようにnの初期値を調整しているのが、工夫といえば工夫なのかもしれません。

感想とか

三角関数とか使うのは学生時代以来なので、最初は問題の内容を理解するだけでいっぱいいっぱいでした(><)

記事ではさらっとtanの公式を書いていますが、実際はかなり数学の解説サイトをググって調べてきたものです。もはやこのへんの公式とかは、頭の中からすっぽり抜け落ちてしまってますなー。。


また、今回の解法もかなりしらみつぶし的なやり方で解いているので、もう少し効率の良いやり方があるのかと色々考えては見ましたが、現状ではこれが精一杯ですw

実行速度は、まだまだ改善の余地はありそうですね。