読者です 読者をやめる 読者になる 読者になる

Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

『計算機プログラムの構造と解釈』のパスカルの三角形の問題をSchemeで解く

 今日「『計算機プログラムの構造と解釈』で面白い問題があるんですよ」というのを教えてもらった。それは問題1.12の「Pascalの三角形」に関する問題で、これは二項係数を出すときに使うやつということでぼんやりと覚えているんだけれども、既に忘れてしまっていた。

 ちなみに、Pascalの三角形というのは、下のような図のことを言う。

パスカルの三角形 - Wikipediaより引用。

 これらを再帰的プロセスの方法で、要素を計算する手続きを書く、という問題だ。これは、三角形の辺の上の数を1から始め、三角形の内部の数はその二つの数の和であるという風に、作成されていく三角形だ。で、制限として「配列(Lispなのでリストなのだけども)」を使わないこと、そして関数定義と条件分岐だけで要素を計算する、という条件があるっぽく、この二つの方法を封じられるとなかなか考えさせられる問題なので、改めて考えたいなと思ったのだった。

 で、この問題をどのように定義するのかは難しい。つまり「要素」の単位の最小限を何処に持っていくのか、という話になる。単純にパスカルの三角形の、ある段までの和を求めることであるならば、簡単にできる。というのも、これは、単に上の段の「二つの配列」が重なったものでしかないからだ。図にするとこのようになる。

 このように、前の段を配列の要素だと考え、先頭に0を追加した配列と、後者に0を追加した配列を作る。それをお互いに足し会わせることで、次の段が出来るように出来ている。さらに、このように分解すると解るように、2段目以降は、n2で表現できることに気がつく。つまり、1, 2, (22), (23) ... という形で表現できる。これをSchemeで書くと、恐らく下のようになるだろう。

(define (sum-pascal x)
  (sum-pascal-process x 1))

(define (sum-pascal-process time num)
  (cond ((= time 0) 0)
        (else (+ num 
                 (sum-pascal-process 
                   (- time 1) (* num 2))))))

 確かに、これ自体で簡単に書くことができるのだが律儀に要素を生成するとするならば、もう少し工夫が必要だろう。配列は作れないわけだから、要素を生成しながら、それらを足していく過程が必要になる。上記の重なっている部分、つまり(1, 2, 1)であったり、あるいは(1, 3, 3, 1)という部分というのは、結局のところ、最初に分裂した1の集合でしかないとも言える。つまり、重ねずに冗長にかくならば、下のようになるとも言える。

1
1 1
1 1 1 1
1 1 1 1 1 1 1 1

 とするならば、これは単なる木構造再帰としても表現できる。これをSchemeで書くと下のようになる。

(define (tree-pascall time) 
  (- (tree-pascall-process time) 1))

(define (tree-pascall-process time) 
    (cond ((= time 0) 1)
        (else  
        (+ 
            (tree-pascall-process (- time 1))
            (tree-pascall-process (- time 1))))))

 これは二倍ずつ1を足していくプロセスだから、最初の段を表現するために1を消さなければならない。これは変な感じかもしれないが、パスカルの三角形の一つの特徴を示している。それは、パスカルの三角形は、四角形の道順の数をあらわしているとも捉えられるからだ(参考)。つまり、この場合は、そこに到達するための道筋を馬鹿正直に数えている、という言い方もできそう。

 とはいえ、じゃあちゃんと要素を数える方法はないのか、という話にもなるのだが、どうやらwikipediaによれば、n段のk番目にnCkを配置した形として表現できるということらしい。nCkは、式になおすと、n(n-1)(n-2)……(n-r+1) / k(k -1)(k - 2)…1 となる。では、この式を愚直になおすと次のようになるだろう。

(define 
    (my-factorial x) 
    (cond ((<= x 1) 1)
        (else (* x (my-factorial (- x 1))))))

(define (my-p x y) 
    (my-p-process x y 0))

(define (my-p-process n r time)
    (cond ((= r (+ time 1)) (- n time))
          (else 
            (* (- n time) (my-p-process n r (+ time 1))))))

(define (my-combination n r)
    (/ (my-p n r) (my-factorial r)))

(define (pascall-n-sum n)
    (+ (pascall-n-process n 1) 1))

(define (pascall-n-process n time)
    (cond ((= n time) 1)
          (else (+ 
            (my-combination n time)
            (pascall-n-process n (+ time 1))))))

(define (pascall n) 
    (pascall-n-process n 1))

(define (pascall-n-process n time)
    (cond ((< n time) 0)
          ((= time 1) (+ 1 (pascall-n-process n (+ time 1))))
          (else (+ (pascall-n-sum (- time 1)) (pascall-n-process n (+ time 1))))))

 このあたりに関しては、教科書を引っ張り出して書いてみたものの、そういう風になる理由がわからなかったりする。

 ちなみに、パスカルの三角形のエッセイに関しては、日能研がよくまとまっている。