CodeIQ/マヨイドーロ問題
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
このページでは[[CodeIQ>https://codeiq.jp/]]¬e{codeiq-o...
*マヨイドーロ [#m63c03c6]
-マヨイドーロ問題の詳細は[[こちら>https://codeiq.jp/q/254...
-結城浩先生のCodeIQのページは[[こちら>http://www.hyuki.co...
*幾つか手で動かしてみる [#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|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);なのに対し、...
-なので、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)+simpleFibonacciN...
break;
}
return retValue;
}
}}
-このsimpleFibonacciNumber関数は、nを渡すと、n番目のフィ...
-問題では、&mimetex(n<N);となるような、偶数のnの、フィボ...
**単純な実装の限界 [#n14751bd]
-しかし、この実装方法だと、計算時間が指数時間で増加し、爆...
-後述するが、フィボナッチ数は指数関数的に増え、そのフィボ...
-今回の自動採点は、1秒以内に計算が終了しないと、不正解扱...
*一般項を用いた実装 [#r388184f]
-[[行列のべき乗とフィボナッチ数列]]でも説明したが、フィボ...
-&mimetex(p_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqr...
-で、前述の単純な再帰の実装では計算時間がフィボナッチ数同...
-なので、フィボナッチ数と比例して増えることになり、計算時...
-ここで一般項を用いることで再帰しない実装方法を試す
-以下が実装例
-&mimetex(\sqrt{5}); や&mimetex(\frac{1}{\sqrt{5}});など...
#geshi(C++,number){{
#include <cmath>
const double positivleHalfRoot5 = 1.618033988749894848204...
const double negativeHalfRoot5 = -0.618033988749894848204...
const double inverseRoot5 = 0.447213595499957939281834733...
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%B...
-&mimetex(53\log_{10}(2)\approx 15.9545897701);であり、10...
|n |73 |74 |75 ...
|べき乗で求めた結果|806515533049393 |1304969544928657|211...
|足し算で求めた結果|806515533049393 |1304969544928657|211...
|桁数(10進数) |15桁|16桁|16桁|16桁|16桁|16桁|17桁|
| | | |こ...
-C++の規約にはないものの、コンパイラ次第では128bit/80bit...
--Visual Studio 2012。無し。long doubleも8バイト長
--gcc。long doubleは12バイト長。でも実体は80bit。指数部15...
-80bitのfloatを使ったとしても仮数部は64bitしかなく、&mime...
-どうやっても浮動小数点ではテストケースをパスできない
*計算速度と精度を考慮した実装 [#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 in...
{
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));だが、これ...
-計算時間的にはこれでも一瞬で終わる
-が、再度オーバーフローの問題が現れる。
**計算速度と精度を考慮した実装での限界 [#sc1788da]
-整数型に戻しても、64bitの壁が存在する
N フィボナッチ数 フィボナッチ数の16進数表現
89 1779979416004714189 0x18B3C1D91E77DECD
90 2880067194370816120 0x27F80DDAA1BA7878
91 4660046610375530309 0x40ABCFB3C0325745
92 7540113804746346429 0x68A3DD8E61ECCFBD
93 12200160415121876738 0xA94FAD42221F2702 ←ここでMSBが...
94 1293530146158671551 0x111F38AD0840BF6BF ←オーバーフ...
-テストケースでは最大N=2015の結果を求められる
-というわけで、残念ながら、どうしても多倍長整数の実装が必...
-今回はC++で挑戦したが、他の言語だと扱える最大整数はどう...
*多倍長整数の実装の前に [#r4800738]
-実装しかけて、前回のCodeIQ、[[サルベジオン問題>CodeIQ/サ...
-今回はフィボナッチ数でどうせ足し算しか使わないので、流用...
-実装コードは長いので[[こちら>http://ideone.com/ngG5Jk]]...
*感想 [#t662ef12]
-面白かった!
-今回は、
--フィボナッチ数の一般項
--多倍長整数型の実装
-と、過去の自分のWikiを再度活躍させる場面が2箇所もあり、C...
-結城先生の模範解答ではRubyを使ってらして、Rubyでは自動的...
-以前のサルベジオン問題でもその当たりは解説で触れられてな...
-自前実装はいいアイディアでは無かったかも知れないけれど(...
-とうとう結城先生の問題でも自動採点のテストケース、つまり...
終了行:
このページでは[[CodeIQ>https://codeiq.jp/]]¬e{codeiq-o...
*マヨイドーロ [#m63c03c6]
-マヨイドーロ問題の詳細は[[こちら>https://codeiq.jp/q/254...
-結城浩先生のCodeIQのページは[[こちら>http://www.hyuki.co...
*幾つか手で動かしてみる [#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|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);なのに対し、...
-なので、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)+simpleFibonacciN...
break;
}
return retValue;
}
}}
-このsimpleFibonacciNumber関数は、nを渡すと、n番目のフィ...
-問題では、&mimetex(n<N);となるような、偶数のnの、フィボ...
**単純な実装の限界 [#n14751bd]
-しかし、この実装方法だと、計算時間が指数時間で増加し、爆...
-後述するが、フィボナッチ数は指数関数的に増え、そのフィボ...
-今回の自動採点は、1秒以内に計算が終了しないと、不正解扱...
*一般項を用いた実装 [#r388184f]
-[[行列のべき乗とフィボナッチ数列]]でも説明したが、フィボ...
-&mimetex(p_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqr...
-で、前述の単純な再帰の実装では計算時間がフィボナッチ数同...
-なので、フィボナッチ数と比例して増えることになり、計算時...
-ここで一般項を用いることで再帰しない実装方法を試す
-以下が実装例
-&mimetex(\sqrt{5}); や&mimetex(\frac{1}{\sqrt{5}});など...
#geshi(C++,number){{
#include <cmath>
const double positivleHalfRoot5 = 1.618033988749894848204...
const double negativeHalfRoot5 = -0.618033988749894848204...
const double inverseRoot5 = 0.447213595499957939281834733...
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%B...
-&mimetex(53\log_{10}(2)\approx 15.9545897701);であり、10...
|n |73 |74 |75 ...
|べき乗で求めた結果|806515533049393 |1304969544928657|211...
|足し算で求めた結果|806515533049393 |1304969544928657|211...
|桁数(10進数) |15桁|16桁|16桁|16桁|16桁|16桁|17桁|
| | | |こ...
-C++の規約にはないものの、コンパイラ次第では128bit/80bit...
--Visual Studio 2012。無し。long doubleも8バイト長
--gcc。long doubleは12バイト長。でも実体は80bit。指数部15...
-80bitのfloatを使ったとしても仮数部は64bitしかなく、&mime...
-どうやっても浮動小数点ではテストケースをパスできない
*計算速度と精度を考慮した実装 [#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 in...
{
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));だが、これ...
-計算時間的にはこれでも一瞬で終わる
-が、再度オーバーフローの問題が現れる。
**計算速度と精度を考慮した実装での限界 [#sc1788da]
-整数型に戻しても、64bitの壁が存在する
N フィボナッチ数 フィボナッチ数の16進数表現
89 1779979416004714189 0x18B3C1D91E77DECD
90 2880067194370816120 0x27F80DDAA1BA7878
91 4660046610375530309 0x40ABCFB3C0325745
92 7540113804746346429 0x68A3DD8E61ECCFBD
93 12200160415121876738 0xA94FAD42221F2702 ←ここでMSBが...
94 1293530146158671551 0x111F38AD0840BF6BF ←オーバーフ...
-テストケースでは最大N=2015の結果を求められる
-というわけで、残念ながら、どうしても多倍長整数の実装が必...
-今回はC++で挑戦したが、他の言語だと扱える最大整数はどう...
*多倍長整数の実装の前に [#r4800738]
-実装しかけて、前回のCodeIQ、[[サルベジオン問題>CodeIQ/サ...
-今回はフィボナッチ数でどうせ足し算しか使わないので、流用...
-実装コードは長いので[[こちら>http://ideone.com/ngG5Jk]]...
*感想 [#t662ef12]
-面白かった!
-今回は、
--フィボナッチ数の一般項
--多倍長整数型の実装
-と、過去の自分のWikiを再度活躍させる場面が2箇所もあり、C...
-結城先生の模範解答ではRubyを使ってらして、Rubyでは自動的...
-以前のサルベジオン問題でもその当たりは解説で触れられてな...
-自前実装はいいアイディアでは無かったかも知れないけれど(...
-とうとう結城先生の問題でも自動採点のテストケース、つまり...
ページ名: