プロジェクトオイラー
http://projecteuler.net/index.php
Q122.
べき乗の計算はバイナリ法を使うと速いが、それより掛け算の回数が少ない方法があることがある。例えば、15乗。200乗までの掛け算の回数の総和。
これは、以前に考えた。
http://d.hatena.ne.jp/inamori/20080330
ソースが見つからなかったので、コピペしたら、コンパイルエラーで、それらしきところを直して動かすと、結果が少しおかしい。これは「はてな記法」のせいだ。']'が重なっているとおかしくなる。ソースがどうしても見つからないので困っていると、「編集」をクリックすればいいことに気がついた。これを少し改変して答えが出た。
これ、うまくやるとメタプログラミングでべき乗の関数を作るときに速くなる。
#includeusing namespace std;
int optimize(int n, int nBin);
void initLimit(int *limit, int n, int nOpt);
void forward(int *pos, int& iturn);
bool next(int *pos, int& iturn);
int binary(int n);const int NBITS = 8;
const int N = 200;int main() {
int sum = 0;
for(int n = 2; n <= 200; n++) {
int nBin = binary(n);
int nOpt = optimize(n, nBin);
sum += nOpt;
cout << n << " : " << nOpt << endl;
}
cout << sum << endl;
return 0;
}int optimize(int n, int nBin) {
int nOpt = nBin;
int set_num[NBITS*2];
set_num[0] = 1;
int pos[NBITS*2];
for(int i = 0; i < NBITS*2; i++)
pos[i] = 0;
int iturn = 1;
int limit[NBITS*2];
initLimit(limit, n, nOpt);
while(true) {
set_num[iturn] = set_num[pos[iturn]] + set_num[iturn-1];
if(set_num[iturn] < limit[iturn]) {
if(!next(pos, iturn))
return nOpt; // 最後まで検索した
}
else if(set_num[iturn] > n) {
if(!next(pos, iturn))
return nOpt; // 最後まで検索した
}
else if(set_num[iturn] == n) { // 見つかった
cout << set_num[0];
for(int i = 1; i <= iturn; i++)
cout << " -> " << set_num[i];
cout << endl;
nOpt = iturn;
initLimit(limit, n, nOpt);
if(!next(pos, iturn))
return nOpt; // 最後まで検索した
}
else {
forward(pos, iturn);
}
}
}void initLimit(int *limit, int n, int nOpt) {
limit[nOpt-1] = n;
for(int i = nOpt - 2; i >= 0; i--)
limit[i] = (limit[i+1] + 1) / 2;
}bool next(int *pos, int& iturn) {
pos[iturn]++;
while(pos[iturn] == iturn) {
iturn--;
if(iturn == 0)
return false; // 最後まで検索した
pos[iturn]++;
}
return true;
}void forward(int *pos, int& iturn) {
iturn++;
pos[iturn] = 0;
}int binary(int n) {
int sum = 0;
for( ; n > 1; n >>= 1) {
if(n & 1)
sum += 2;
else
sum += 1;
}
return sum;
}
