C++　報酬ポイント：300以上

まず、ご質問にある黄金比というのはフィボナッチ数のことですよね。

フィボナッチ数の比は黄金比に収束しますが黄金比とフィボナッチ数は同じものではありませんのでご注意を。

本問題は内容こそシンプルですが実に多くの問題を孕んでいます。

まずは再帰関数の効率に関する問題。

質問文にあるnumcalがフィボナッチ数を求めている箇所かと思いますが、再帰を利用していますよね。

この実装は簡単で、理屈としては正しいのですが非常に効率が悪いのです。

例えばnumcal(5)を計算することを考えて見ます。

numcal(5)を計算するためにnumcal(4)とnumcal(3)を計算する必要がありますので、numcal(4)とnumcal(3)を呼び出します。

numcal(4)を計算するためにnumcal(3)とnumcal(2)を計算する必要がありますので、numcal(3)とnumcal(2)を呼び出します。

一方numcal(3)を計算するためにnumcal(2)とnumcal(1)を計算する必要があります。

このように呼び出しがどう連鎖するかを示したのが次の図です。

numcal(5)を計算するのに結局numcal(1)を2回、numcal(2)を3回、numcal(3)を2回も計算することになります。

本来であればそれぞれ1回計算すればよいはずですので効率が悪いことがご理解頂けると思います。

例として挙げたnumcal(5)程度ですとnumcal()を呼び出す回数は合計9回程度ですが、例えばnumcal(50)ですと数億回以上numcal()関数が呼ばれることになります。これだと普通の時間では計算が終わりません。

(このnumcalが呼ばれる回数は指数関数的に増大します)

また、再帰に限らず関数内で関数を呼び出す場合、メモリのスタックという領域を使います。

通常のプログラムではそれほど問題になることは多くありませんが再帰関数を使うと、この領域をあっという間に食いつぶしてプログラムが正常動作しなくなることがあります。

以上の点からnumcalの実装には再帰呼び出しを使わないほうが良いでしょう。

さらに、3桁台の数字を入力する必要があるということですのでnumcal(999)までは計算可能にしたいということだと思いますがこの結果は恐ろしいほど大きな数字になりますので処理系が用意している整数型では表現しきれません。

例えばlongが4バイトの処理系ですとunsigned longで表現できる数字は0から4294967295までです。

ちなみにnumcal(48)を計算すると4807526976となり、unsigned longでは格納できません。

お使いの処理系がlong longをサポートしているようであればunsigned long longを利用すればnumcal(999)まで計算できると思います。

もしサポートしていないのであれば、結果を格納する整数を表すクラスなどを自作する必要があるかと思います。

以下のようにしてみて下さい。

unsigned long long numcal(int n)
{
	if ( n <= 2 ) return 1;
	unsigned long long a = 1;
	unsigned long long b = 1;
	unsigned long long c;
	for ( int i = 3 ; i <= n ; ++i ) {
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}

ただし、これを格納するHogeクラスの数値表現もunsigned long longにする必要があります。

さて、Hogeクラスに入力された数字が結果に幾つ含まれているかですが、

digitに各桁が格納されるようになっているようですので

int Hoge::count(int n) const {
	int c = 0;
	for ( std::vector<short>::const_iterator it = digit.begin() ; it != digit.end() ; ++it )
		if ( *it == n ) ++c;
	return c;
}

で良いのではないかと思います。

numcal関数はフィボナッチ数を計算しているようですが、二つ問題があります。

一つ目の問題は計算時間です。このような再帰処理は n が大きくなるにつれて急激に計算時間が増加します。詳細は以下のURLが詳しいですが、n=100のような場合は、まず計算は終わりません。非現実的です。

http://anchoret.seesaa.net/article/52858842.html

二つ目の問題は計算精度です。フィボナッチ数はn=80ぐらいで15桁を越えてしまいますが、このような桁数の大きな数値は、普通のプログラムでは取り扱うことが出来ません。大きな数字を扱う専用のライブラリを別途利用する必要があります。

ではどうするか？ですが、まず一つ目の計算時間の問題は、一般項をそのまま計算することで解決できます。

http://ja.wikipedia.org/wiki/フィボナッチ数

で、"正確な整数値は以下の式で与えられる"と一般式が載っていますので、これをそのままC言語で書きます。

int numcal(int n)
{
  const double phi = (1.0 + sqrt(5))/2.0;

  return floor( pow(phi, n )/sqrt(5) + 0.5 );
}

ただ、このままでは nが80を越えた辺りで、計算結果がおかしくなります。計算精度の問題があるからです。

計算精度の問題は、たとえば gmp というライブラリを使えば解決できます。gmpについては使い方の説明が以下のpdf に良くまとまっていますので、これを参考に上記の関数を書き換えれば良いです。

http://ayapin.film.s.dendai.ac.jp/~matuda/TeX/PDF/27th.pdf