世界線航跡蔵

Mad web programmerのYuguiが技術ネタや日々のあれこれをお送りします。

2006年07月12日

Collatz予想step数の最大値

キミならどう書く 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です。

トラックバック

http://yugui.jp/articles/483/ping

現在のところトラックバックはありません

コメント

babie (2006年07月12日 05時56分54秒)
<p> 書いてた書いてたwRuby覚えるまで。私には重かったけど。</p>
blog comments powered by Disqus

ご案内

前の記事
次の記事

タグ一覧

過去ログ

  1. 2016年07月
  2. 2016年01月
  3. 2015年09月
  4. 2015年08月
  5. 過去ログ一覧

フィード

フィードとは

その他

Powered by "rhianolethe" the blog system