letrecで繰り返す

Scheme

Project EulerのProblem3をやった。
問題は素因数分解で、最大の素数を求めるもの。
素数を求めて割り切れるか確かめていけばいいだけだ。実に簡単…、じゃなかった。
分解する数が600851475143と超でかい。intじゃ収まらない。と思ったら、Lisp系の言語は多倍長演算してくれるようなので問題なかった。

素因数分解の方法としては、小さい素数から順次割り切れるかどうか確かめていく。割り切れれば、その商を割る数にして処理を継続する。素数が商以上になれば終了。てな感じである。

letrecを覚えたので使ってみた。

; 素数か？
(define prime-number?
  (lambda (m)
    (if (< m 2)
	#f
	(letrec ((find-prime
		  (lambda (i n)
		    (if (< i 2)
			#t
			(if (= 0 (remainder n i))
			    #f
			    (find-prime (- i 1) n))))))
	  (find-prime (- m 1) m)))))

; x以下の素数を求める
(define prime-below-x
  (lambda (x)
    (letrec ((rec-func
	      (lambda (i)
		(if (< i 2)
		    2
		    (if (prime-number? i)
			i
			(rec-func (- i 1)))))))
      (rec-func x))))

; 問題を解く、素因数分解
(define problem3
  (lambda (x)
    (letrec ((rec-func
	      (lambda (i x)
		(let ((p (prime-below-x i)))
		  (if (<= x p)
		      p
		      (if (= 0 (remainder x p))
			  (rec-func (+ i 1) (/ x p))
			  (rec-func (+ i 1) x)))))))
      (rec-func 2 x))))

答えは6857
(prime-number? 6857)
は#tを返したので、確かに最大の素数のようだ。

頭の体操

Scheme

面白そうなサイトを見つけた。
Project Euler
http://odz.sakura.ne.jp/projecteuler/index.php?Project%20Euler

数学の問題をプログラムで解いていく、とういうものだ。言語は何でもいいのでSchemeで解くことにした。

初めの問題は、3と5の倍数で1000未満の数の和だそうで。

; x倍でn以上、m未満の数のリストを作る
(define x-fold-list
  (lambda (x n m)
    (if (<= m (* x n))
	'() ; empty
	(cons (* x n) (x-fold-list x (+ n 1) m)))))

; リストの合計
(define sum-list
  (lambda (lis)
    (if (null? lis)
	0
	(+ (car lis) (sum-list (cdr lis))))))

; 問題を解く
(define problem1
  (lambda (n)
    (- (+ (sum-list (x-fold-list 3 1 n))
	  (sum-list (x-fold-list 5 1 n)))
       (sum-list (x-fold-list 15 1 n)))))

コレは簡単だった。まあ、一問目だし。
答えは233168。

続いて二問目、フィボナッチ数列の4000000未満の数の和。

; リストを作成、再帰部
(define rec-fibonacci-list
  (lambda (a b m)
    (if (<= m (+ a b))
	'()
	(cons (+ a b) (rec-fibonacci-list b (+ a b) m)))))

; リストを作成、一つに纏め切れなかった
(define fibonacci-list
  (lambda (a b m)
    (cons a (cons b (rec-fibonacci-list a b m)))))

; リストの中から2の倍数の和を計算
(define sum-2-fold
  (lambda (lis)
    (if (null? lis)
	0
	(if (= 0 (remainder (car lis) 2))
	    (+ (car lis) (sum-2-fold (cdr lis)))
	    (sum-2-fold (cdr lis))))))

; 問題を解く
(define problem2
  (lambda ()
    (sum-2-fold (fibonacci-list 1 2 4000000))))

もっと綺麗に書けそうな気がするが、今の実力ではこれが限界。
答えは4613732。多分あってる。

Schemeで何を書こうか

Scheme

Schemeを習得するために本を読んだりネットの解説ページ見たりしてるんだけど、こんなので本当に使い物になるプログラムが書けるのか疑問だ。

しかし、構文とかばっかしやっててもつまらないので、何かゲームでも作りながら覚えたい。。
出来るだけシンプルなものがいいのでポーカーでも書いてみよう。

しょぼいけどカードを配る部分。
named letの理解は、まだちょっと怪しい。。

(use srfi-27) ; ランダムを使う

; リストにカードを加える
(define add-card
  (lambda (ls)
    (cons
     (+ 1 (random-integer 13))
     ls)))

; 五枚組みのカードを配る
(define deal-card
  (lambda ()
    (let loop((cards '()))
      (if (= 5 (length cards))
	  cards
	  (let ((c (add-card cards)))
	    (loop c))))))

Emacsのキーバインドにはまだ慣れないせいで、書くのが遅くなってしまう。

Scheme本買った

Scheme

ちょっとしたデータの操作とかをするのに毎回Cで書いてたんだけど、面倒になってきたのでサクっと処理できるようにスクリプトなんかやろうと思って買ってきた。


Cygwin+Gauche+Meadowの環境で動かしてる。Emacsなんて使ったことがなかったので現在奮闘中。導入するときに幾つか躓いたので書いておく。
Cygwinでgz解凍できない→WinRARでおｋ。解凍して出来たファイルはtarのようなので、リネームしてまた解凍。
Meadowでは設定ファイル.emacsはWindowの環境変数にHOMEの項目を作り、そこで指定したパスに置く。TZという項目も作成、値はJST-9。タイムゾーンらしい。。
Emacsの操作はネットに転がってるのでそちらを参照されたし。


仕事が忙しい？ので家でプログラム組む時間がない。。。

Expression Template 其の一

C++

早速、Expression Template(ET)を試してみることにした。
ずいぶん前に、買って置いたC++テンプレートテクニックを参考に実装してみる。
そのままでは詰まらないので、ベクトルの次元数を型情報としてテンプレート引数にとるようにしてみた。Traitsってやつか？
次元数を追い出したのはいいが、コンストラクタで初期化出来なくなってしまったので、Boostの真似をして代入用の演算子を定義しておいた。
が、、+=が使えなくなるので、シフト演算子あたりに変えようかな・・・。

以下、vector_types.h

#ifndef _vector_types_h_
#define _vector_types_h_

#include <assert.h>

namespace tml
{

typedef unsigned int    size_t;

// 型定義構造体
struct tagInt2 { typedef int Type; enum { Dim = 2 }; };
struct tagInt3 { typedef int Type; enum { Dim = 3 }; };
struct tagInt4 { typedef int Type; enum { Dim = 4 }; };
struct tagFloat2 { typedef float Type; enum { Dim = 2 }; };
struct tagFloat3 { typedef float Type; enum { Dim = 3 }; };
struct tagFloat4 { typedef float Type; enum { Dim = 4 }; };


// 本体
template<class _TypeTag>
struct Vector
{
    typedef typename _TypeTag::Type    Type;
    enum { Dim = _TypeTag::Dim };

    Type v[Dim];

    Vector()
    {
        for(int n = 0; n < Dim; n++) v[n] = 0.0f;
    }
    Vector(Type vv[])
    {
        for(int n = 0; n < Dim; n++) v[n] = vv[n];
    }

    // Expression Template用
    Type& operator[](size_t n) { return v[n]; }
    Type operator[](size_t n) const { return v[n]; }

    template<class _Expr>
    inline Vector<_TypeTag>& operator=(const _Expr &expr)
    {
        for(size_t i = 0; i < Dim; i++)
        {
            v[i] = expr[i];
        }

        return *this;
    }
};

// 代入簡略化
template<class _TypeTag, int N>
struct VectorAssigner
{
    Vector<_TypeTag> &v;

    VectorAssigner(Vector<_TypeTag> &vector) : v(vector) {}
    inline VectorAssigner<_TypeTag, N+1> operator,(typename _TypeTag::Type arg) // boostの真似
    {
        assert(N < _TypeTag::Dim); // 代入しすぎ

        v.v[N] = arg;
        return VectorAssigner<_TypeTag, N+1>(v);
    }
};

template<class _TypeTag>
inline VectorAssigner<_TypeTag, 1> operator+=(Vector<_TypeTag> &v, typename _TypeTag::Type arg)
{
    v.v[0] = arg;
    return VectorAssigner<_TypeTag, 1>(v);
}


} // namespace tml

#endif

Vector側に実装したのは代入演算子だけで、まだ、ETの部分は書いていない。
次はExpression Template本体をやる予定。。