Up

フィボナッチ数の計算

再帰・関数オブジェクト

 

フィボナッチ数は次式

、　、

で与えられる。この式は、再帰的呼び出しの関数としてそのまま表すことができる。リスト１に例を示す。

 

＝＝＝＝＝＝＝＝＝＝　リスト１　＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

include <iostream>

 

using namespace std;

 

double Fibonacci(int n) {

        double v;

        if (n <= 0) {

                v = 0.0;

        }

        else if (n == 1) {

                v = 1.0;

        }

        else {

                v = Fibonacci(n - 2) + Fibonacci(n - 1);

        }

        return v;

}

 

int main() {

        cout << "n = ";

        int n;

        cin >> n;

        cout << "Fibonacci(" << n << ") = " << Fibonacci(n) << endl;

 

        cout << endl << "何か文字キーを押してから、Enterキーを押して終了。" << endl;

        char ck;

        cin >> ck;

        return 0;

}

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

 

上のプログラムを、Visual Studio 2015で新規作成するときは、まず、メニュ項目「ファイル｜新規作成｜プロジェクト」を選ぶ。

表示された「新しいプロジェクト」ダイアログウィンドウにおいて、「テンプレート｜Visual C++｜全般」を選んで表示されるものから「空のプロジェクト」を選んでプロジェクトを作成する。

プロジェクトが作成されたら、メニュ項目「プロジェクト｜新しい項目の追加」を選ぶ。表示される「新しい項目の追加」ダイアログウィンドウにおいて「Visual C++｜コード」を選び、表示されたものから「C++ファイル（.cpp）」を選ぶ。

追加項目として表示されるC++ファイルに上のコードを書き込めばよい。実行例を図１に示す。

図１

 

Visual Studio 2015におけるC++プログラムの新規作成については、ウェブサイト

http://y-okamoto-psy1949.la.coocan.jp/booksetc/introvcpp/On_vs2015/

に説明を用意している。

フィボナッチ数を再帰的に計算する場合、

というように、同じ関数が複数回再帰的に呼び出されるということが起こる。上の場合、が２回呼び出されている。このため、が大きくなると同じ関数が多数回呼び出されることが起こり、そのために計算時間が長くなる。

同じ関数の複数回の呼び出しを避けるため、計算結果を配列に保存する方法を採用したものがリスト２の関数Fibonacci_Aである。

 

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝　リスト２　＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

#include <iostream>

#include <time.h>               //              function time()

 

using namespace std;

 

double Fibonacci(int n) {

        double v;

        if (n <= 0) {

                v = 0.0;

        }

        else if (n == 1) {

                v = 1.0;

        }

        else {

                v = Fibonacci(n - 2) + Fibonacci(n - 1);

        }

        return v;

}

 

double Fibonacci_A(int n) {

        double v;

        if (n <= 0) {

                v = 0.0;

        }

        else if (n == 1) {

                v = 1.0;

        }

        else {

        //      v = Fibonacci(n - 2) + Fibonacci(n - 1);

                double * F = new double[n + 1];

                F[0] = 0.0;

                F[1] = 1.0;

                for (int i = 2; i <= n; i++)

                        F[i] = F[i - 2] + F[i - 1];

                v = F[n];

                delete[] F;

        }

        return v;

}

 

 

int main() {

        cout << "n = ";

        int n;

        cin >> n;

        time_t t0, t1;

        time(&t0);

        cout << "Fibonacci(" << n << ") = " << Fibonacci(n) << endl;

        time(&t1);

        cout << difftime(t1, t0) << "s" << endl;

 

        time(&t0);

        cout << "Fibonacci(" << n << ") = " << Fibonacci_A(n) << endl;

        time(&t1);

        cout << difftime(t1, t0) << "s" << endl;

 

        cout << endl << "何か文字キーを押してから、Enterキーを押して終了。" << endl;

        char ck;

        cin >> ck;

        return 0;

}

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

 

実行結果は図２のようになる。

図２

 

再帰的方法を用いた場合では９秒掛かっている処理が、計算結果を配列に保存して重複計算を避けた場合では１秒以下（図２では０秒の表示）で処理されていることがわかる。リスト２のプログラムの実行においては、の値を大きくとり過ぎると計算がなかなか終わらないので注意が必要である。

再帰的方法で処理時間が掛かるのは、同じ処理を複数回呼び出すためであるので、これは２項係数の漸化式を用いる場合でも同じである。再帰的呼び出しで重複処理がない場合は、アルゴリズムの表現の分かり易さと処理の効率化が期待できる。例えば、データを何らかの基準で並べる場合、単純なソートに比べてクイックソートは高速である。

　リスト２の関数Fibonacci_Aでは、関数が呼び出されて必要な場合、配列が用意され値が設定されるが、関数の実行が終了すると配列は廃棄される。計算結果の格納された配列を関数の実行後も保持しておくと、多数回Fibonacci数を求める場合、配列に設定されたすでに計算済みの値を利用することができる。リスト３では、関数内に配列を保持するために関数をクラス型CFibonacciとして用意し、クラス型内に配列を用意している。クラス型において演算子( )を定義すれば、関数オブジェクト（ファンクター；functor）として使用できる。リスト３では、( ) が

double operator()(int n)

という形式で、演算子としての( ) と、引数リストを宣言する( )と２回現れていることに注意。クラス型を

CFibonacci f;

と宣言すれば、

f(n);

で、オブジェクト f の演算子 ( ) が、n を実引数として呼び出される。演算子も関数（メソッド）の一種であることに注意。

 

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝　リスト３　＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

#include <iostream>

#include <time.h>               //              function time()

#include <Windows.h>            //              function QueryPerformanceFrequency/Counter()

#include <cmath>                //              function pow()

 

using namespace std;

 

double Fibonacci_A(int n) {

        double v;

        if (n <= 0) {

                v = 0.0;

        }

        else if (n == 1) {

                v = 1.0;

        }

        else {

                //      v = Fibonacci(n - 2) + Fibonacci(n - 1);

                double * F = new double[n + 1];

                F[0] = 0.0;

                F[1] = 1.0;

                for (int i = 2; i <= n; i++)

                        F[i] = F[i - 2] + F[i - 1];

                v = F[n];

                delete[] F;

        }

        return v;

}

 

class CFibonacci {

        double * F;

        int isize;

public:

        CFibonacci() {

                F = new double[1001];

                F[0] = 0.0;

                F[1] = 1.0;

                isize = 1;

        }

        virtual ~CFibonacci() {

                delete[] F;

        }

        double operator()(int n) {

                double v;

                if (n <= isize) {

                        v = F[n];

                }

                else if (n > 1000) {

                        v = -1;

                }

                else {

                        for (int i = isize + 1; i <= n; i++)

                                F[i] = F[i - 2] + F[i - 1];

                        v = F[n];

                        isize = n;

                }

                return v;

        }

};

 

class MyTime {

        LARGE_INTEGER L_I;

        int freq;

        double c;

public:

        MyTime(): c(pow(2.0, 32.0))

        {

                BOOL ck = QueryPerformanceFrequency(&L_I);

                if (ck) {

                        freq = L_I.LowPart;

        //              cout << "H = " << L_I.HighPart << "   L = " << L_I.LowPart << endl << endl;

                }

                else {

                        freq = -1;

                }

        }

        //              msec

        double operator()() {

                if (freq < 0) {

                        return -1.0;

                }

                else {

                        QueryPerformanceCounter(&L_I);

                        double v = L_I.HighPart * c + L_I.LowPart;

                        return 1000.0 * v / freq;

                }

        }

};

 

 

int main() {

        double VF[1001];

        time_t t0, t1;

        double dt0, dt1;

        MyTime mt;

        time(&t0);

        dt0 = mt();

        for (int n = 0; n <= 1000; n++)

                VF[n] = Fibonacci_A(n);

        time(&t1);

        dt1 = mt();

        for (int n = 990; n <= 1000; n++)

                cout << "Fibonacci(" << n << ") = " << VF[n] << endl;

        cout << "t1 - t0 = " << difftime(t1, t0) << "s" << endl;

        cout << "dt1 - dt0 = " << dt1 - dt0 << "ms" << endl;

 

        CFibonacci f;

        time(&t0);

        dt0 = mt();

        for (int n = 0; n <= 1000; n++)

                VF[n] = f(n);

        time(&t1);

        dt1 = mt();

        for (int n = 990; n <= 1000; n++)

                cout << "CFibonacci(" << n << ") = " << VF[n] << endl;

        cout << "t1 - t0 = " << difftime(t1, t0) << "s" << endl;

        cout << "dt1 - dt0 = " << dt1 - dt0 << "ms" << endl;

 

 

        cout << endl << "何か文字キーを押してから、Enterキーを押して終了。" << endl;

        char ck;

        cin >> ck;

        return 0;

}

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

 

リスト３のプログラムを実行すると図３のようになる。

図３

 

実行時間は、関数timeによる秒単位の測定の他に、ミリ秒単位での測定のためのクラス型MyTimeを用意して、関数オブジェクトの呼び出しの形で計時している。毎回必要な配列を用意して終了時に廃棄する関数Fibonacci_Aを用いる場合、約３ミリ秒掛かっている処理が、クラス型CFibonacciの関数オブジェクトf()を用いるしょりでは約0.03ミリ秒の処理時間となっている。クラス型CFibonacciでは、n の値を1000までとしている。これは、double型でのオーバーフローを避けるためである。

なお、リスト３のプログラムは圧縮ファイルFibonacci_C.zipとして用意した。ファイル名Fibonacci_C.zipをクリックしてダウンロード解凍すれば、Visual Studio 2015で開くことができる。

 

 

Up