Collatz予想

キミならどう書く 2.0 - ROUND 2 -
http://ll.jus.or.jp/2006/blog/doukaku2

Collatz予想のステップ数を求めるコードを書こうかと思いましたが、私の気になる言語Scheme, Io, Ocamlは既に先を越されているようで無念至極、諦めかけたところC++で記述してる例を見かけました。
C++はLLではないとの見方が優勢なのだと思っていましたが、特に誰も気にしてないようなので、私もこっそりC++で書いてみることにします。
(ロクにC++使ったことも無いくせに・・・)
ただし、こちらは以下のルールを勝手に設けてみました。

• ループを使わない(for, whileなど)
• 関数の再帰呼び出しを行わない
• ifや3項演算子による分岐を行わない

要するにtemplateで解を得ましょうという話です。
まず、ステップ数の計算は以下のようなtemplate展開から求められます

#include 

template 
struct _f{
	enum{value = 0};
};

/* even */
template 
struct _f<0, n>{
	enum{value = 1 + _f<(n / 2) % 2, n / 2>::value};
};

/* odd */
template 
struct _f<1, n>{
	enum{value = 1 + _f<(n * 3 + 1) % 2, n * 3 + 1>::value};
};

template <>
struct _f<1, 1>{
	enum{value = 1};
};

template 
struct f{
	enum{value = _f::value};
};




int main(){
	std::cout << f<3>::value << std::endl;
	return 0;
}

パラメータ「3」を与えている上記のコードをコンパイル、実行してみると、ステップ数である「8」が出力されます。
では、お題は1から100までのなかから、最大のステップ数となる数を求めるとのことなので、そのように展開されるtemplateを定義してみましょう。

#include 

const int max = 100;



template 
struct _f{
	enum{value = 0};
};

/* even */
template 
struct _f<0, n>{
	enum{value = 1 + _f<(n / 2) % 2, n / 2>::value};
};

/* odd */
template 
struct _f<1, n>{
	enum{value = 1 + _f<(n * 3 + 1) % 2, n * 3 + 1>::value};
};

template <>
struct _f<1, 1>{
	enum{value = 1};
};

template 
struct f{
	enum{value = _f::value};
};



template 
struct _Compare{
	enum{value = 0};
	enum{index = 0};
};

template 
struct _Compare<1, x, y, xi, yi>{
	enum{value = x};
	enum{index = xi};
};

template 
struct _Compare<0, x, y, xi, yi>{
	enum{value = y};
	enum{index = yi};
};

template 
struct Compare{
	enum{value = _Compare= y, x, y, xi, yi>::value};
	enum{index = _Compare= y, x, y, xi, yi>::index};
};






template 
struct Loop{
	enum{value = 0};
	enum{index = 0};
};

/* last */
template 
struct Loop<1, current, max>{
	enum{value = f::value};
	enum{index = current};
};

template 
struct Loop<0, current, max>{
	enum{value = Compare<
		f::value,
		Loop::value,
		current,
		Loop::index
		>::value
		};
	enum{index = Compare<
		f::value,
		Loop::value,
		current,
		Loop::index
		>::index
		};
};

/* main loop */
template 
struct h{
	enum{value = Loop<0, 1, max>::index};
};



int main(){
	std::cout << h::value << std::endl;
	std::cout << f< h::value >::value << std::endl;
	return 0;
}

このコードをコンパイル、実行した結果、「97」と「119」が出力されるはずです。
前者が解で、後者はそのステップ数となります。
上記のコードは無駄が散見されるものですが、サンプルということでお目汚しのほどご勘弁を。

以上、ループも関数の再帰呼び出しも行わないC++の例でした。