Go to the first, previous, next, last section, table of contents.


プログラミング 練習問題11 解答「再帰によるスターリング数」

(再帰なので)まずダミーのプログラムを定義して z s キーに割付けます。 本当の z s の動作は、 スタックから値を 2個取って 1個返すことになっていますから、 ダミー定義に DEL を使ってスタックが正しく出るようにしておきましょう。

2:  4          1:  4                         2:  4
1:  2              .                         1:  2
    .                                            .

  4 RET 2       C-x ( DEL C-x )  Z K s RET       2

最後の 2 は、ダミーの z s コマンドを定義するうちに失われた 2 を置きなおしています。 さて、本当の定義に取りかかりましょう。 漸化式は次のように少し書きなおす必要があります。
s(n,m) = s(n-1,m-1) - (n-1) s(n-1,m)

(この定義は長いので、最後にまとめたものを付けておきます。 学習者はそれを M-# m で読込むことができます。)

2:  4        4:  4       3:  4       2:  4
1:  2        3:  2       2:  2       1:  2
    .        2:  4       1:  0           .
             1:  2           .
                 .

  C-x (       M-2 RET        a =         Z [  DEL DEL 1  Z :

4:  4       2:  4                     2:  3      4:  3    4:  3    3:  3
3:  2       1:  2                     1:  2      3:  2    3:  2    2:  2
2:  2           .                         .      2:  3    2:  3    1:  3
1:  0                                            1:  2    1:  1        .
    .                                                .        .

  RET 0   a = Z [  DEL DEL 0  Z :  TAB 1 - TAB   M-2 RET     1 -      z s

(ダミーの z s が返した値 3 は正しくないので注意してください。 今は単なる場所取りでかまいません。)

3:  3               4:  3           3:  3       2:  3      1:  -6
2:  3               3:  3           2:  3       1:  9          .
1:  2               2:  3           1:  3           .
    .               1:  2               .
                        .

 M-TAB M-TAB     TAB RET M-TAB         z s          *          -
(ESC TAB ESC TAB)       (ESC TAB)

1:  -6                          2:  4          1:  11      2:  11
    .                           1:  2              .       1:  11
                                    .                          .

  Z ] Z ] C-x )   Z K s RET      DEL 4 RET 2       z s      M-RET k s

たとえ定義中に得られた答がひどいインチキでも、 ひとたび定義が完成すれば z s コマンドは正しい答を得るようになります。

プログラム全体をここにもう一度まとめます。

C-x (  M-2 RET a =
       Z [  DEL DEL 1
       Z :  RET 0 a =
            Z [  DEL DEL 0
            Z :  TAB 1 - TAB M-2 RET 1 - z s
                 M-TAB M-TAB TAB RET M-TAB z s * -
            Z ]
       Z ]
C-x )

この定義を M-# m (read-kbd-macro) を使って読込み、 そのあと Z K s とすることで、事前のダミーなしに定義することができます。 なぜなら read-kbd-macro は読込んだ定義を実行することなく覚えるからです。 この点で、 しばしば M-# m は Calc において再帰的プログラムを作る最も簡単な方法です。


Go to the first, previous, next, last section, table of contents.     利用度数