■

さて、Mr.ExceptionのすずきさんがさっそうとProject EulerのProblem36を解いたらしいので、
僕も対抗心を燃やさせてください＞＜。

Problem36、
最初に例。585 = 1001001001(binary)
このように10進数と2進数でともに回文になる数を1,000,000以下の整数の中から求めよ。

それぞれの桁をA(n),A(n-1),A(n-2),...,A(2),A(1),A(0)と表せば、
585はA(2)=5, A(1)=8, A(0)=5
1001001001はA(9)=1, A(8)=0,...,A(1)=0,A(0)=1と表せますね。

そして、回文であると言うことは
最上位桁の仮数と、最下位桁の仮数、
最上位桁-1の仮数と、最下位桁+1の仮数
最上位桁-2の仮数と、最下位桁+2の仮数
がそれぞれ等しいということです。

式で書くと、(10進数の場合)

floor( A(n)/10^n ) % 10 == floor( A(0) ) % 10
floor( A((n-1))/10^(n-1) ) % 10 == floor( A(1)/10^1 ) % 10
floor( A((n-2))/10^(n-2) ) % 10 == floor( A(2)/10^2 ) % 10
...

と、最上位桁と最下位桁から両方1つずつ歩み寄っていくわけです
2進数の場合も基数を変えるだけです。

偶数桁なら丁度半分まで進みますし、
奇数桁なら中心の仮数は無視できるので、
floor(n/2)回の操作になります。

source.

template<int RADIX>
int power(int N)
{
	if( N >= 1 )		{ return RADIX * power<RADIX>(N-1); }
	else if( N == 0 )	{ return 1; }
	else			{ assert(false); return -1; }
}

template<int RADIX>
bool mirror_cmp(int figure, int num)
{
	using namespace pstade::oven;

	PSTADE_OVEN_FOREACH(i, counting(0,figure/2)) {
		if( (num / power<RADIX>(figure-i-1)) % RADIX != (num / power<RADIX>(i)) % RADIX ) { return false; }
	}
	return true;
}

桁数nがsource中ではfigureになっている点に注意.
powerは見ての通り、再帰ですね。

桁数を求める部分です

template<int RADIX>
int get_figure(int num)
{
	assert(num > 0);
	int count = 0;
	while( (num = num / RADIX) ) { ++count; }

	return ++count;
}

これは、対数なりなんなりを使った方が早いのかもしれません。。。ただし実際に桁の上昇に大して
この関数の計算量も対数時間でしか増えませんのでね。

メイン関数です

int main()
{
	using namespace pstade::oven;
	const int MAX_NUM = 1000000; //1,000,000 [1million]

	int sum = 0;
	PSTADE_OVEN_FOREACH(n, 	counting(1, MAX_NUM)) {
		if( 
			mirror_cmp<10>( get_figure<10>(n), n ) &&
			mirror_cmp<2>( get_figure<2>(n), n ) )
		{ sum += n; }
	}

	std::cout << sum << std::endl;
	return 0;
}

使ったヘッダ

#include <iostream>
#include <pstade/oven/foreach.hpp>
#include <pstade/oven/counting.hpp>
#include <cassert>
#include <vector>

visual studio2008 SP1で確認
次回、ちょっと不満がある点を直しましょう。