目的の数字が現れるフィボナッチ数列の最小の初項・第2項をC++で求める

かってぃさん（@katty0324）の次のポストを参考に，目的の数字が現れるフィボナッチ数列の最初の2項を求めるプログラムを書いてみました．

フィボナッチの問題やっと解けたけど、あんまり意味もないよね。Cだったら10行くらい。 URL

2010-07-15 06:08:06 via Twitpic

数列クラス

なるべく数列っぽく解きたいなぁ，と思ったので数列基底クラスをまず作り，それを継承する形にしました．

/*
@brief 数列基底クラス
*/
class Nums
{
protected:
	//! 数列の要素を管理
	vector<int> V;

	/*
	@brief 数列を定義
	@param[in] i 何番目の要素か
	*/
	virtual int Def(const unsigned int i) = 0;

	/*
	@brief 初項をセットするとき利用
	@param[in] val 代入する値
	*/
	void Set(int val) {
		V.push_back(val);
	}

private:
	/*
	@brief 足りない項を追加
	@param[in] n 何番目まで追加するか
	*/
	void Add(const unsigned int n) {
		for (unsigned int i=V.size(); i<=n; i++) {
			Set(Def(i));
		}	
	}
public:
	/*
	@brief 項の値にアクセス
	@param[in] k アクセスする項の番号
	*/
	int operator[](const unsigned int k) {
		if (k >= V.size()) {
			Add(k);
		}
		return V[k];
	}
};

実際の値はvectorで管理します．数列の各値についてはoperator[]をオーバーロードしてa[10]のように取得します．計算量が減るように，例えばこれまで10番目の項より小さい項しか見ていない時に10番目にアクセスしたら，初めて10番目まで計算するようにしています．数列の定義は純粋仮想関数Defをオーバーロードして定義します．初項はSetで代入します．

数列a,b,cの定義

aはフィボナッチ数列，b，cはよく分かりませんが，きっとそう解けば解けるのでしょう．と思って作成します．

// Fibonacci数列
class ANums : public Nums
{
private:
	int Def(const unsigned int i) {
		return V[i-1] + V[i-2];
	}
public:
	ANums() {
		Set(1);
		Set(1);
	}
};

// 数列b
class BNums : public Nums
{
private:
	ANums A;
	int Def(const unsigned int i) {
		return static_cast<int>(ceil(static_cast<double>(V[i-1]) * A[i-1] / (A[i-1] + A[i])));
	}
public:
	BNums(unsigned int m) : A() {
		Set(m-1);
	}
};

// 数列c
class CNums : public Nums
{
private:
	BNums B;
	int Def(const unsigned int i) {
		return V[i-1] + ((i%2)?-1:1)*(B[i] - 1);		
	}
public:
	CNums(unsigned int m) : B(m) {
		Set(m-1);
	}
};

実際に解いてみた

#include <iostream>
#include "sequence.h" // 上記クラスが定義されている

int main()
{
	int num;
	cout << "数字を入力してください：";
	cin >> num;

	// 数列cを定義
	CNums c(num);

	// 収束するまで計算
	int i;
	for (i=1; c[i] != c[i-1]; i++);

	// 書き出し
	int d1 = c[i], d2 = num, k = 0; 
	while (d1 > 0 && d2 > 0) {
		if (k%2) {
			cout << d1 << endl;
			d1 -= d2;
		} else {
			cout << d2 << endl;
			d2 -= d1;
		}
		k++;
	}
	return 0;
}

結果：

数字を入力してください：1111111111
1111111111
686704432
424406679
262297753
162108926
100188827
61920099
38268728
23651371
14617357
9034014
5583343
3450671
2132672
1317999
814673
503326
311347
191979
119368
72611
46757
25854
20903
4951

計算量が少ないので，こんなデカイ数字についても答えを出すことが出来ます．

普通に書くと…

正直に書いたコードだと以下のようになります．

#include <stdio.h>

void solveMinFibonacciPair(int &first, int &second, const int num)
{
	first = second = num;
	for (int i=1; i<second; i++) {
		for (int j=i; j<second; j++) {
			int a = i, b = j;
			while (a < num && b < num) {
				if (a > b)	b += a;
				else		a += b; 
			}
			if (a == num || b == num) {
				if (i + j < first + second) {
					first  = i;
					second = j;
				}
			}
		}
	}
}

int main()
{
	int first, second;
	solveMinFibonacciPair(first, second, 11111111); // 終わらなーい
	printf("1st: %d; 2nd: %d\n", first, second);
	return 0;
}