CodeIQ/マヨイドーロ問題 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• CodeIQ/マヨイドーロ問題 へ行く。

このページでは[[CodeIQ>https://codeiq.jp/]]&note{codeiq-official:[[CodeIQ｜ITエンジニアのための実務スキル評価サービス>https://codeiq.jp/]], 2015-12-06閲覧};で結城浩先生から出題されたマヨイドーロ問題について解説しています。

*マヨイドーロ [#m63c03c6]
-マヨイドーロ問題の詳細は[[こちら>https://codeiq.jp/q/2549]]&note{mayoi-codeiq:[[結城浩の「マヨイドーロ問題」 | CodeIQ>https://codeiq.jp/q/2549]], 2015-12-03公開, 2015-12-06閲覧};
-結城浩先生のCodeIQのページは[[こちら>http://www.hyuki.com/codeiq/]]&note{codeiq-hyuki-official:[[CodeIQの問題に挑戦しよう！>http://www.hyuki.com/codeiq/]], 2015-12-06閲覧};

*幾つか手で動かしてみる [#b2a0a85a]
-問題ではNは「N回まで反転して良い」ということになっている
-簡単のために「N回ちょうど」反転する方法がいくつあるか、数えてみる
**N=0のとき [#c14c9889]
-この時は反転できないので、そのままZから出て行く方法しか無い
-1通りのみ
-X→B→C→Z
**N=1のとき [#ec8b3661]
-Bで反転する経路と、Cで反転する経路の2通りある
-X→B→A→Y
-X→B→C→B→A→Y
**N=2のとき [#lbf2e6bd]
-以下の3通り
-X→B→A→B→C→Z
-X→B→C→B→C→Z
-X→B→C→B→A→B→C→Z
**N=3のとき [#a3165a78]
-以下の5通り
-X→B→A→B→A→Y
-X→B→C→B→A→B→A→Y
-X→B→A→B→C→B→A→Y
-X→B→C→B→C→B→A→Y
-X→B→C→B→A→B→C→B→A→Y
**まとめてみる [#n1311161]
-当然、奇数回反転するとZから、偶数回反転するとYから出る
-そこで、pをZからN回ちょうど反転して出る経路の数、qをYからN回ちょうど反転して出る経路の数といて表にしてみる
|N|p|q|
|0|1|0|
|1|0|2|
|2|3|0|
|3|0|5|
-詳細は結城先生の解説に書かれているので割愛するが、
-&mimetex(F(N)=F(N-2)+F(N-1));という形で表すことができ、これはフィボナッチ数列を表す
-ただし、フィボナッチ数列は&mimetex(F_{3}=2);なのに対し、今回の反転は&mimetex(N=1);の時に経路数が2である
-なので、N回ちょうど反転するときの経路数は&mimetex(F_{N+2});で表される
-さて、あとは、フィボナッチ数列を求める実装だけである
*単純な実装 [#q16ca076]
-教科書に出てきそうな、再帰の参考例
#geshi(C++,number){{
unsigned long long simpleFibonacciNumber(int n)
{
	unsigned long long retValue = 0;
	switch(n)
	{
		case 0:
			retValue = 0;
			break;
		case 1:
		case 2:
			retValue = 1;
			break;
		default:
			retValue = simpleFibonacciNumber(n-1)+simpleFibonacciNumber(n-2);
			break;
	}
	return retValue;
}
}}
-このsimpleFibonacciNumber関数は、nを渡すと、n番目のフィボナッチ数を返してくれる
-問題では、&mimetex(n<N);となるような、偶数のnの、フィボナッチ数を足し合わせれば良い
**単純な実装の限界 [#n14751bd]
-しかし、この実装方法だと、計算時間が指数時間で増加し、爆発する
-後述するが、フィボナッチ数は指数関数的に増え、そのフィボナッチ数を計算するための時間が単純に足しあわされていくので、計算時間が到底間に合わなくなる
-今回の自動採点は、1秒以内に計算が終了しないと、不正解扱いになってしまうため、この実装方法では間に合わない

*一般項を用いた実装 [#r388184f]
-[[行列のべき乗とフィボナッチ数列]]でも説明したが、フィボナッチ数は以下の一般項で表されることが知られている
-&mimetex(p_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\});
-で、前述の単純な再帰の実装では計算時間がフィボナッチ数同様に足し算の形で増えていく
-なので、フィボナッチ数と比例して増えることになり、計算時間は&mimetex(O(c^N));で増える
-ここで一般項を用いることで再帰しない実装方法を試す
-以下が実装例
-&mimetex(\sqrt{5}); や&mimetex(\frac{1}{\sqrt{5}});などの定数は事前に計算して固定値で記入しておいた。

#geshi(C++,number){{
#include <cmath>
const double positivleHalfRoot5 = 1.618033988749894848204586834365638117720309179805762862135448;
const double negativeHalfRoot5 = -0.61803398874989484820458683436563811772030917980576286213544;
const double inverseRoot5 = 0.447213595499957939281834733746255247088123671922305144854179;

unsigned long long powerComputationFibonacciNumber(int n)
{
	double retValue;
	retValue  = pow(positivleHalfRoot5, n);
	retValue -= pow(negativeHalfRoot5, n);
	retValue *= inverseRoot5;
	return (unsigned long long)(retValue + 0.5f);
}
}}
-なんとも単純
-これだと計算時間はべき乗の分だけですむ
-return するときに0.5f足し算しているのは、四捨五入するための計算
-これにより、丸め誤差を四捨五入して整数に変換する

**一般項を用いた実装の限界 [#sd90bd69]
-一般項を用いた実装の場合、ネックはdoubleの分解能にある
-[[Wikipedia>https://ja.wikipedia.org/wiki/%E5%80%8D%E7%B2%BE%E5%BA%A6%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E7%82%B9%E6%95%B0]]&note{wp-double:[[倍精度浮動小数点数 - Wikipedia>https://ja.wikipedia.org/wiki/%E5%80%8D%E7%B2%BE%E5%BA%A6%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E7%82%B9%E6%95%B0]], 2015-08-24 08:10版, 2015-12-06閲覧};を見るとわかるが、一般的な(IEEE754で定義された)double 型の仮数部は53bit分の分解能を持つ
-&mimetex(53\log_{10}(2)\approx 15.9545897701);であり、10進数でだいたい16桁ぐらいから丸め誤差が整数として現れ始める

|n                 |73              |74              |75              |76              |77              |78              |79|
|べき乗で求めた結果|806515533049393 |1304969544928657|2111485077978050|3416454622906706|5527939700884756|8944394323791464|14472334024676218|
|足し算で求めた結果|806515533049393 |1304969544928657|2111485077978050|3416454622906707|5527939700884757|8944394323791464|14472334024676221|
|桁数(10進数)      |15桁|16桁|16桁|16桁|16桁|16桁|17桁|
|                  |                |                |ここまで計算結果OK|丸め誤差が整数として現れる|||桁が上がる度に&br();丸め誤差がどんどん大きくなる|

-C++の規約にはないものの、コンパイラ次第では128bit/80bit長の浮動小数点型がある
--Visual Studio 2012。無し。long doubleも8バイト長
--gcc。long doubleは12バイト長。でも実体は80bit。指数部15bit、仮数部64bit。
-80bitのfloatを使ったとしても仮数部は64bitしかなく、&mimetex(64\log_{10}(2)\approx 19.2659197225);であり、10進数で20桁ぐらいから丸め誤差が整数として現れはじめる
-どうやっても浮動小数点ではテストケースをパスできない
 

*計算速度と精度を考慮した実装 [#me298f2c]
-計算速度で言えば、べき乗を利用した実装は十分だったが、問題は精度
-そこで、再度整数型に戻り、整数型でフィボナッチ数を計算してみる
-単純な足し算をする実装も、方法を変えればそこそこのスピードで計算できる
-既に計算されたフィボナッチ数を再帰で再度計算していたのが処理時間が遅い原因
-そこで1度計算されたフィボナッチ数を配列に保存するように実装してみる
-以下実装
#geshi(C++,number){{
#include <vector>
std::vector<unsigned long long> fibonacci;
unsigned long long simpleFibonacciNumber2(int i)
{
	if(fibonacci.empty())
	{
		fibonacci.push_back(0);
	}
	if(fibonacci.size() == 1)
	{
		fibonacci.push_back(1);
	}
	if(fibonacci.size() == 2)
	{
		fibonacci.push_back(1);
	}
	if(i <= 0)
	{
		return 0;
	}
	if((unsigned int)i < fibonacci.size())
	{
		return fibonacci[i];
	}
	for(unsigned int j = fibonacci.size()-1;j < (unsigned int)i;j++)
	{
		unsigned long long p = fibonacci[fibonacci.size()-1];
		unsigned long long q = fibonacci[fibonacci.size()-2];
		fibonacci.push_back(p+q);
	}
	return fibonacci[i];
}
}}
-この実装方法だと、計算した分をどんどん足しあわせて配列を長くしていく
-29行目の push_back で配列の後方にどんどんフィボナッチ数を追加していく
-単純な再帰実装だと計算時間は&mimetex(O(c^N));だが、これだと&mimetex(O(N));で済む。
-計算時間的にはこれでも一瞬で終わる
-が、再度オーバーフローの問題が現れる。

**計算速度と精度を考慮した実装での限界 [#sc1788da]
-整数型に戻しても、64bitの壁が存在する

 N   フィボナッチ数       フィボナッチ数の16進数表現
 89  1779979416004714189  0x18B3C1D91E77DECD
 90  2880067194370816120  0x27F80DDAA1BA7878
 91  4660046610375530309  0x40ABCFB3C0325745
 92  7540113804746346429  0x68A3DD8E61ECCFBD
 93  12200160415121876738 0xA94FAD42221F2702 ←ここでMSBが埋まる(=64bitすべて使って表現が必要になる)
 94  1293530146158671551  0x111F38AD0840BF6BF ←オーバーフローが発生
 
-テストケースでは最大N=2015の結果を求められる 
-というわけで、残念ながら、どうしても多倍長整数の実装が必要になる
-今回はC++で挑戦したが、他の言語だと扱える最大整数はどうなのだろう？

*多倍長整数の実装の前に [#r4800738]
-実装しかけて、前回のCodeIQ、[[サルベジオン問題>CodeIQ/サルベジオン問題]]で四則演算のごく一部だけ実装したlargeNumberクラスを思い出す
-今回はフィボナッチ数でどうせ足し算しか使わないので、流用することに。
-実装コードは長いので[[こちら>http://ideone.com/ngG5Jk]]で公開

*感想 [#t662ef12]
-面白かった！
-今回は、
--フィボナッチ数の一般項
--多倍長整数型の実装
-と、過去の自分のWikiを再度活躍させる場面が2箇所もあり、CodeIQをやってて良かったなぁ、と思った。
-結城先生の模範解答ではRubyを使ってらして、Rubyでは自動的に多倍長整数が実装されているので、もしかしたら多倍長整数の実装は想定してなかった？
-以前のサルベジオン問題でもその当たりは解説で触れられてないので、もしかしたら想定されてなかったのかも。
-自前実装はいいアイディアでは無かったかも知れないけれど(車輪の再発明的に)、前回の自分の実装を再利用できたのは良かった。
-とうとう結城先生の問題でも自動採点のテストケース、つまり計算速度/計算量の制約が出てきて、エンジニアとして腕の見せ所が出てきたのは嬉しい。