Collatz予想step数の最大値

LL c++

キミならどう書く 2.0 ROUND 2 が出題された。なんか、Rubyの回答は 割と綺麗な実装 がもう出ちゃってるね。

そこで、Ruby以外でってことで、私のお気に入りの某関数型言語で書いてみた。

g++ 3.3.5で通ったよ。まともな処理系ならキャッシュしてくれるから速いはず。

#include <iostream>

template <bool cond, unsigned x, unsigned y>
struct choice
{
  enum { value = x };
};
template <unsigned x, unsigned y>
struct choice<false, x, y>
{
  enum { value = y };
};

template <unsigned n, bool is_odd = n%2>
struct g
{
  enum { value = g<3*n+1>::value + 1 };
};
template <unsigned n>
struct g<n, false>
{
  enum { value = g<n/2>::value + 1 };
};

template <>
struct g<1>
{
  enum { value = 1 };
};


template <unsigned n>
struct h
{
  enum {
    value =
      choice<
        (unsigned(g<n>::value) > unsigned(g<h<n-1>::value>::value)), 
        n,
        h<n-1>::value
      >::value
  };
};
template <>
struct h<1>
{
  enum { value = 1 };
};

using namespace std;

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

Perl覚えるまで私ゃ日々のスクリプトを全部これで書いてたんだから、断固としてこれはLLです。