« 2016年8月 | トップページ | 2017年6月 »

2016年10月 2日 (日)

「トライアングル・メイズ問題」の高度じゃないコード

提出忘れして抜けたりしましたが「高度じゃないコード」シリーズその17「トライアングル・メイズ問題」です。

出題された問題 ⇒ https://codeiq.jp/challenge/2833

まずは、F(n)の求め方を考えます。F(1)=1, F(2)=2, F(3)=6, F(4)=42 です。これから、次の式が予想できます。

F(n + 1) = F(n) * ( F(n) + 1 )

さて、最終的に求めるのは F(n) を 1000003 で割った余りですが、上記の式から考えると、途中の計算も 1000003 で割った余りで計算しても同じ結果となることは明らかです。よって、これ以降の F(n) は F(n) を 1000003 で割った余りとして説明します。

ここで、n が最大値 108 の時に上記の式で普通に計算していると、1秒以内では計算が終わりません。そこで、ここでも、1000003 で割った余りを求めることに注目します。F(n) は最長でも 1000003 回までの計算のうちに、それまでの結果と同じ結果が出てくるはずです。そして、それ以降は、その間のループとなります。

ということで、次のような Ruby のコードを作りました。ループの折り返し点と戻り先を調べると同時に F(n) の値を記録しておき、n の値に対応した位置の値を表示しています。確認のため、n = 10 で計算してみましたが、答えは 998593 となりました。

もし、ゴルフをするなら、ループの折り返し点と戻り先を固定値として組むことになると思いますが、今回はパスです。

| | コメント (0) | トラックバック (0)

« 2016年8月 | トップページ | 2017年6月 »