Project EulerのProblem 31はおもしろい問題だと思う。
これは200ペンスをコインの組み合わせで表すとき何通りの方法があるかという問題です。
コンピュータにこれを数えさせるんですね。
これをそのまま解くとネタバレになりそうなので、これをちょっと改題して話題とする。
3800円を、2000円札・1000円札・500円玉・100円玉・50円玉・10円玉・5円玉・1円玉であらわす方法は何通りあるか、
という問題にする。まぁ基本的には一緒ですね。
これをC++で解いてみた。
#include <iostream>
class MakeYen{
private:
static int _yens[9];
long _FindWays(int yen,int step){
if(step==sizeof(MakeYen::_yens)/sizeof(*MakeYen::_yens)) return 1;
int curyen=yen;
int ways=0;
while(curyen>=0){
ways+=this->_FindWays( curyen,step+1 );
curyen-=MakeYen::_yens[step];
}
return ways;
}
public:
long FindWays(int yen){
return this->_FindWays(yen,1);
}
};
int MakeYen::_yens[]={10000,5000,2000,1000,500,100,50,10,5};
void main(void){
MakeYen maker;
std::cout << maker.FindWays(3800) << std::endl;
}
わざわざMakeYenクラスなんて用意してますが、これはこの先の話で使うから。
とりあえずFindWaysメソッドを使えば求まると。
まず貨幣の種類をMakeYen::_yensに収めてある。1円玉は抜けているけど、これは理由がある。
実際の計算をおこなう_FindWaysメソッドは、yenとstepという2つの引数を取るが、
yenは金額、stepは_yens[step]以下の貨幣を使って、その金額を表す通り数を返すと。
計算方法は例えば278円を100円以下の貨幣を使って表す通り数は、
278円を50円以下で表す通り数+178円を50円以下で表す通り数+78円を50円以下で表す通り数
として求めることができるんですね。確かにそうなんですよ。
これを再帰的に施していけば求まると。そういう寸法です。
そして最後に1円以下で表す通り数は必ず1通りです。だから1円玉がリストに入ってないの。
if(step==sizeof(MakeYen::_yens)/sizeof(*MakeYen::_yens)) return 1;なんて書いてあるけど、
これはMakeYen::_yensの長さとstepが等しくなったらという意味。
さて、とりあえずこれで求めてみようと。
するとすぐには出てこないで、1秒ぐらいかかって出てくる。
ネイティブなコードが生成されるからこの程度で済んでるけど、Perlで同じ事をやるとすごく時間がかかる。
まぁそういう問題です。
じゃあPerlで解けるのかというと解けます。
メモ化という手法を使ったんですけどね。
メモ化とは例えば、278円を100円以下の貨幣を使って表す通り数はなんぼか聞かれたら、
1回目はきちんと計算して、その結果をメモして、2回目以降はメモした値を言うと。
そういうことです。実はこの問題はこれでかなり計算時間が削減できます。
まさに二度あることは三度ある。というわけでこれにあわせて多少修正。
#include <map>
class MakeYen{
private:
std::map<std::pair<int,int>,long> _cache;
static int _yens[9];
long _FindWays(int yen,int step){
if(step==sizeof(MakeYen::_yens)/sizeof(*MakeYen::_yens)) return 1;
std::map<std::pair<int,int>,long>::iterator cur=this->_cache.find(std::pair<int,int>(yen,step));
if(cur!=this->_cache.end()) return cur->second;
int curyen=yen;
int ways=0;
while(curyen>=0){
ways+=this->_FindWays( curyen,step+1 );
curyen-=MakeYen::_yens[step];
}
this->_cache.insert(std::pair<std::pair<int,int>,long>(std::pair<int,int>(yen,step),ways));
return ways;
}
public:
long FindWays(int yen){
return this->_FindWays(yen,1);
}
};
std::map<std::pair<int,int>,long>なんて用意します。これはstd::pair<int,int>をキーとして、longの値を記録するもの。
ハッシュといいたいのだが、どうもハッシュじゃないらしいです。
まぁいいや。キーはstd::pair<int,int>ですが、これはintとintの組ということ。
まず、記録があるか確認する方法は、findメソッドを使います。キーを渡すとイテレータがもらえるんですね。
これがmapの末尾をさしていたらそのキーに対応する値はない。
そうじゃなければその得られたイテレータのさすキー・値ペアがfindで渡したキーに対応するものだと。
ちなみにキー・値ペアもstd::pairを使って表されています。紛らわしいですね。
これで見つかればこれを返して、そうじゃなければまじめに計算すると。
そして最後に引数をキーに求めた結果をセットすると。
insertメソッドにキー・値ペアを渡せばセットされます。
という調子です。いや、扱いにくい。
しかしこれを使えば本当に一瞬で出ます。効果絶大のようです。
しかしネイティブだとあまりに計算が速くてありがたみがないですけどね。
元々Perlでやってたときはこれよりは計算量の少ないProblem 31でもかなり時間を食ってたので、
メモ化してやっと実用的な時間で求まるというような調子でした。
それがネイティブなら力業でできるという情報を検証するためにやってみたんですけどね。
いや、確かに力業でできますわ。
しかしやっぱり一瞬ででないのは残念なので、わざわざメモ化を実装してみました。
けどC++は本当に強力だ。