キミならどう書く

さて、LightweightLanguageRingからのお題、「キミならどう書く」が話題になっているので載ってみることに。今回はコラッツ予想に関連した問題だが、特に数学的な知識が必要なわけではない。
問題文はこちら。
http://ll.jus.or.jp/2006/blog/doukaku2
まずはHaskellでそのまんま書いてみた。Haskellについてはまだかなり拙いものしか書けないことを自覚してげんなり。

h n = foldl max 0 $ map (f 1) [1..n]
    where
      f c n
        | 1==n = c
        | even n = f (c+1) (div n 2)
        | otherwise = f (c+1) (3*n+1)

main = print $ h 100

1に収束するまでのカウントと漸化式が癒着しているのが美しくない。それとリストの中から最大値を求めるのにわざわざfoldlを使ってるのは単に基本関数をあまり把握してないから。そんな基本的なのが用意されてないはずはないと思っていたのだけれど、とりあえず知っている限りで書いた。(ところで、SKKでもMS-IMEでも「漸化式」が出てこなかったんだが、標準の辞書ってのはその程度のもんなのか？)
その後、他の人のを参考にしてHaskellっポイかんじになるように修正したのが以下。意味もなくポイントフリースタイルだのセクションだのを導入してみた。いろいろやってみたい年頃なんです。

h n = maximum $ map g [1..n]
    where
      g = (1+) .length .takeWhile (1/=) .iterate f
      f n | 1==n      = 1
          | even n    = div n 2
          | otherwise = 3*n+1

main = print $ h 100

ずいぶんスッキリとしたカンジになったと思う。iterate関数は漸化式との組合せでいろいろ使えそうだ。foldlをちょっと特殊にしたようなものと理解。
で、実際に実行してみたのだが、デカい値を渡すとやたらと遅い。他の解を見るとStateモナドを使ってメモ化したりして工夫しているようだ。しかし、Haskellについてそこまで充分に理解が及んでいない私はとりあえずC++でメモ化版を作ってみる。

#include <map>
#include <iostream>
using namespace std;

class collatz {
private:
  static map<int, int> memo;
  int n;
  int g(int n, int depth);
public:
  collatz(int n);
  int step(void);
};

map<int, int> collatz::memo;
collatz::collatz(int n) : n(n) {}
int collatz::step(void){return g(n,1);}

int collatz::g(int n, int depth) {
  int result=memo[n];

  if(n==1) result=depth;
  else if(!result) {
    result=g(n%2==0 ? n/2 : 3*n+1, 1+depth);
    memo[n]=result-depth+1;
  } else {
    result+=depth-1;
  }
  return result;
}

int h(int n) {
  int maxStep=0;

  for(int i=1;
      i<=n;
      maxStep=max(maxStep, collatz(i++).step()));

  return maxStep;
}

int main(void) {
  cout << h(100);
  return 0;
}

C/C++だと多倍長演算が標準に含まれないのでこういうネタのときには向かないな。ちょっと数値を増やすとすぐ溢れやがる。
Document ID: e32a187ac9ecbfb8c7e52323bd08bbf5