CodeIQ に出した「最大公約フィボナッチ数(?)」の解説・解題

CodeIQ に「最大公約フィボナッチ数(?)」( https://codeiq.jp/ace/nabetani_takenori/q649 )という問題を出した。
挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

で。
まずは問題

問題

正の整数 B に対して
a[0]=1, 
a[1]=B, 
a[i]=a[i-1]+a[i-2] if 2≦i
で定義される数列を Fibo{B} と書きます。

例えば、Fibo{5} は
1, 5, 6, 11, 17, 28, 45, 73, 118, 191, ...
と続く数列です。

ある Fibo{B} に m と n が含まれていて、m ≦ n となっている場合、m を n の約フィボナッチ数と呼びます。
Fibo{5} には 17 と 73 が含まれているので、17 は 73 の約フィボナッチ数です。
73 は Fibo{14} にも含まれていますので、29 も 73 の約フィボナッチ数です。
( Fibo{14} は、1, 14, 15, 29, 44, 73, 117, 190, ... という数列です )

x の約フィボナッチ数であり、y の約フィボナッチ数でもある数のうち、最も大きなものを「x と y の最大公約フィボナッチ数」と呼び、GCFibo( x, y ) と書きます。

例えば、73 の約フィボナッチ数をすべて列挙すると
1, 5, 6, 11, 14, 15, 17, 28, 29, 36, 37, 44, 45, 72, 73
となります。
一方 97 は、Fibo{4}, Fibo{48}, Fibo{96}, Fibo{97} に含まれているので、97の約フィボナッチ数は
1, 4, 5, 9, 14, 23, 37, 48, 49, 60, 96, 97
です。
両者に含まれている数は 1, 5, 14, 37 ですが、このうち最も大きなものは 37 なので、GCFibo( 73, 97 ) は 37 となります。

というわけで、最大公約フィボナッチ数についてはわかっていただけたと思います。

さて。以下の4件の最大公約フィボナッチ数
GCFibo( 23, 25 ), GCFibo( 308, 320 ), GCFibo( 6168, 9877 ), GCFibo( 18518, 19942 )
を求めて下さい。

■補足
Fibo{B}、約フィボナッチ数、最大公約フィボナッチ数、GCFibo(x,y) は、いずれもこの問題のために作られた用語です。

出題の意図とか

集合の操作をきちんとやれること、というのが主眼だった。

集合に含まれているかどうかを調べる
集合の合併( union )を求める
集合の共通部分( intersection )を求める
集合から、条件を満たす部分を抜き出す
集合から最大値を選び出す

など、あるいはそれの代わりになる処理が必要だったと思う。

アイディアの源泉は、名前のとおり、最大公約数。最大公約数（のようなもの）を求めるにあたり、エラトステネスのふるいが使えなかったらどうするのか、というところからスタートした。

ruby による実装例

手元ではまず ruby で実装した。
ruby なんかだと集合操作は用意されているのですごくコンパクトになるんだけど、組み込みのコンテナクラスが Hash と Array しかないので集合という切り口になるとちょっともったいない感じになりやすい。
標準添付ライブラリの Set もあるけど、まあ Set を使うほどじゃないかなとも思い、こういう実装になった：

#!ruby

# 最初の二項を指定して Fibonacci 数列を求める
def fibos(a,b)
  Enumerator.new{ |y|
    loop do
      y << a
      a, b = b, a + b
    end
  }
end

# 「約フィボナッチ数」を求める。重複あり、整列せず。
def dfibo( n )
  (1..n).flat_map{ |b|
    fb=fibos( 1, b ).take_while{ |x| x<=n }
    fb.include?(n) ? fb : []
  }
end

# 「最大公約フィボナッチ数」を求める。
def gcfibo( *x )
  x.map{ |e| dfibo(e) }.inject( &:& ).max
end

[
  [ 23, 25 ],[308, 320],[ 6168, 9877 ],[ 18518, 19942 ]
].map{ |x|
  "GCFibo(#{x.join(",")}) = #{gcfibo(*x)}"
}.join(", ").tap{ |x| puts x }

flat_map かなぁとも思うんだけど、こんなところで。
何の工夫もない全探索なんだけど、この問題にはこれで十分。
【追記】
dfibo で fb.include?(n) という計算で判断しているけど、しえるさんの

@Nabetani ありがとうございます。実装例のfb.include?(n)はfb.last==nの方が速いと思いました。C++の方は今から読みます。回文基数のような発見がありそうですので。
— しえる (@cielavenir) 2014, 1月 20

という指摘の通り、fb.last==n の方が速い。
私が計算量のことを気にしていなかったことがよく分かる(すいません)。

計算量を減らす試み - C++ による実装例

一部の方が気づいた通り、計算量を大幅に減らすことができる。先ほどの ruby でも、手元で実行すると1秒かからないのでこれで全く問題ないんだけど、なんとなく悔しい感じはすると思う。

で。

Fibo{B} を、B に具体的な数を入れずに書き出すとすぐにわかると思うんだけど、Fibo{B} の各項は概ね

F[n]+F[n+1]×B

となる。ここで F[n] は、普通のフィボナッチ数。つまり、0, 1, 1, 2, 3, 5, ... を示す。
逆に言うと。x が Fibo{B} に含まれている場合、

x=F[n] + F[n+1]×B

となるような n が存在する。
n の値は、F[n]<x の範囲で調べれば良いので、xが2万ぐらいでも 20回ちょっとで済んでしまう。1000倍ぐらい速くなる。

なお。
先ほど「概ね」と書いたのは、上の式だと x=1 の時にうまくいかないから。

これを利用して慣れない C++11 で書くとこんな感じになる。

#include <iostream>
#include <utility>
#include <iterator>
#include <set>
#include <algorithm>
#include <initializer_list>

using namespace std;

class Fibonacci
{
  pair<int,int> m;
public:
  Fibonacci( int a, int b )
  : m{ a, b }
  {}
  auto first()->int const{  return m.first;  }
  auto second()->int const{  return m.second;  }
  auto operator++()->Fibonacci& { 
    m=make_pair( second(), first()+second() );
    return *this;
  }
};

auto collect( set<int> & r, int limit, int base )->void
{
  for ( Fibonacci f{1,base}; f.second() <= limit; ++f ){
    r.insert( f.second() );
  }
}

auto dfibo( int n ) -> set<int>
{
  set<int> r{ 1 };
  for( Fibonacci f{1,1} ; f.second()<n ; ++f ){
    if ((n - f.first()) % f.second() == 0) {
      collect(r, n, (n - f.first()) / f.second());
    }
  }
  return r;
}

auto gcfibo( int a, int b ) -> int 
{
  set<int> const ra{ dfibo( a ) };
  set<int> const rb{ dfibo( b ) };
  return *find_if( ra.rbegin(), ra.rend(), [& rb]( int ea )->bool{
    return rb.find( ea ) != rb.end();
  } );
}

auto test( int a, int b ) -> void
{
  int result{ gcfibo( a, b ) };
  cout << "GCFibo( "<< a << ", " << b << " ) = " << result << "\n";
}

auto main(int argc, char const * argv[] )->int
{
  int samples[][2] = {
    { 23, 25 },
    { 308, 320 },
    { 6168, 9877 },
    { 18518, 19942 } };
  for( auto const & e : samples ){
    test( e[0], e[1] );
  }
}

先ほどの ruby 版との差は、関数 dfibo。
Fibonacci(1, 1) で作った普通のフィボナッチ数列を使って、Fibo{B} の B を求めている。

gcfibo では find_if を使っているけど、set_intersection を使うのも悪くないと思う。

気になったこととか

具体的な数字は書かないけど、ほとんどの方が全問正解だった。不正解の方もケアレスミスばかりで、全般的には簡単だったのかなと思ったけど、どうだろう。

2つの集合に含まれる値のうちで最大のもの

今回の例では、対象となる集合があまり大きくないので二重ループで書いても全然困らないんだけど、普通こうやるよ、というものはある。

以下、サイズ a の集合 A とサイズ b の集合 B があるということにする。

ひとつは：

A, B を整列する。
A に含まれる値を、大きい物から順に調査 ( 調査対象を e と呼ぶ )
e が B に含まれるかどうか調べる。

というもの。先ほどの C++ 版はこれ。
「e が B に含まれるかどうか調べる」という処理で2分探索が使えるので、単純に見えて結構速い。

もうひとつは：

A, B を整列する
A の末尾を指すポインタ（のようなもの）pa とBの末尾を指すポインタ（のようなもの）pb を用意する。
「pa の指す値と pb の指す値のうち、大きい方を一つ前に戻す」を繰り返す
繰り返す途中で paの指す値と pbの指す値が等しくなったら終了

というもの。
こちらのほうが速いことが多いと思うけど、書くべきコードの量が多くなりやすいので前者でも悪くないと思う。

前述の ruby 版はどちらでもなく、「AとBの共通部分を抽出してから最大値」なのでちょっと無駄な計算をしていることになる。

再帰による計算量の爆発

フィボナッチ数の計算。
定義式

a[0]=1, 
a[1]=B, 
a[i]=a[i-1]+a[i-2] if 2≦i

をそのまま実装してしまっている方が何名かいらっしゃったのが気になった。
この問題では、最悪の場合でも a[23] ぐらいまであれば足りる。
a[23] をこのままの計算で求めると、実は関数呼び出しが 10万回ぐらい行われてしまう。すごくもったいない。
23回ぐらいのループになるようにアルゴリズムを見なおすのがおすすめだけど、このままのアルゴリズムでメモ化するという手もある。
この問題では困らない程度のことではあるのでわかっててやるぶんには問題ないんだけど、わかってやってるよ、というコメントがほしいところではある。

言語

使用言語はこんな感じになった。

ruby 16名
C++ 10名
Java 8名
Python 8名
PHP 5名
C言語 4名
JavaScript 4名
perl 4名

Python と C++ が予想よりも多かった。

そろばんや筆算の人は、いなかった。
今回の問題なら、コンピュータなしでも頑張れば行ける範囲だと思う。私はやりたくないけどね。

問題についてもうちょっと、他

オフラインリアルタイムどう書く( 現在第18回の参加者募集中 ) では出さないようにしている数学っぽい問題を出してみた。
思ったよりも好評だった反面、問題文が理解し難いという声も複数頂いた。
数学っぽい文章を見慣れている人には悩まずに読めるように書いたつもりなんだけど、第三者によるレビューとかは経ていないのでどうなのかよくわからない。

12345 のような答えになるペアを作る方法を知りたい、という声を何件かいただいたので、説明すると。

答えを含む Fibo{B} を2つ選ぶ。( 以下、Fibo{B0}, Fibo{B1} と呼ぶ)
Fibo{B0} から、答えより大きな値をいくつか選ぶ。(以下、N0 と呼ぶ )
Fibo{B1} から、答えより大きな値をいくつか選ぶ。(以下、N1 と呼ぶ )
N1 に含まれている値を N0 から除去した集合から、適当に1個選ぶ( 以下、q0 と呼ぶ )
N0 に含まれている値を N1 から除去した集合から、適当に1個選ぶ( 以下、q1 と呼ぶ )

とすると、GCFibo( q0, q1 ) は最初の答えになる。

最後に

今月中に次の問題を出す予定（未着手）なのでよろしくお願い致します。

Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。