Project Euler の 15 番目を Scheme で

Project Euler の 15 番目 (Problem 15) を Scheme で書いてみたのだけど、ぜんぜん処理が帰ってこない。
処理に無駄が多すぎるプログラムだってのはわかってるんだけどさ。

Project Euler

http://projecteuler.net/

(define f
  (lambda (x y)
    (if (or (zero? x) (zero? y))
      1
      (+ (f (- x 1) y) (f x (- y 1))))))

(display (f 20 20))

2x2 の grid の場合、(display (f 2 2)) ってやってあげると 6 と出るので間違ってはいないと思うんだけどな。

（厳密に言うと、「2x2 の grid だから (display (f 2 2))」と打つ、というのは説明が必要で、2x2 の grid の場合、格子点の数はスタート地点とゴール地点を含めて 3x3 の 9 個ある。で、その 9 個の点それぞれに対してゼロオリジンで座標を設定すると、左上が (0, 0)、右下が (2, 2) となる。関数 r に渡しているふたつの数値は、座標の x y なのである。）

考え方

ある格子点に到達するには、いっこ左の点から到達するか、いっこ上の点から到達するかしかない。

なので、ある格子点 P = (px, py) に到達する経路の数を f(P) とすると、f(P) は、きっとこんな風にあらわせる。

f(P) = f(px, py) = f(px-1, py) + f(px, py-1)

C 言語版

以下は C 言語版。

ある格子点に到達する経路の数を計算したら、次からは計算しなくていいように二次元配列に保存している。

二次元配列を上から下になめるように埋めていけば、再帰も使わなくてすむし速いんだけど、ここはわざと上の Scheme 版と同じように再帰を使っている。

#include <stdio.h>

static unsigned long long int g[21][21];

unsigned long long int f(int x, int y) {

    if (x==0 || y==0)
        return 1;

    if (g[y][x]>0)
        return g[y][x];

    g[y][x] = f(x-1, y) + f(x, y-1);
    return g[y][x];
}

int main(int argc, char **argv) {

    printf("%llu\n", f(20, 20));

    return 0;
}