2

私は現在、パスカルの三角形の行シーケンスを見つけることに取り組んでいます。行番号を入力し、その行までの一連の番号をリストに出力したかったのです。たとえば(Pascal 4)、結果が得られ(1 1 1 1 2 1 1 3 3 1)ます。

私が見つけたアルゴリズムを使用しようとしています。アルゴリズム自体は次のとおりです。

V c = V c-1 * ((r - c)/c)

rとcは行と列で、V 0 =1 とします。このアルゴリズムは、ウィキペディアのページの「計算と個々の行または対角線」というタイトルのセクションで具体的に見つけることができます。

これが私がこれまでに持っているコードです:

(define pascal n)
  (cond((zero? n) '())
       ((positive? n) (* pascal (- n 1) (/ (- n c)c))))

私はそれがほとんど何もないことを知っていますが、列の値を組み込むためにaletまたは aを使用して関数のスコープを見つけようとするのに苦労してきました。lambdaさらに、私は再帰にも苦労しています。ベースケースを確立する方法と次のステップに進む方法がよくわかりません。基本的に、私はどこでもかなり迷子になっています。これがあまり示されていないことはわかっていますが、正しい方向への一歩は大歓迎です。

4

2 に答える 2

3

私のブログでパスカルの三角形について話しました。

あなたの質問では、Vcの式は1行だけです。これは、次のようなコードに変換されます。

(define (row r)
  (let loop ((c 1) (row (list 1)))
    (if (= r c)
        row
        (loop (+ c 1) (cons (* (car row) (- r c) (/ c)) row)))))

次に、一連の行を組み合わせて三角形を作成します。

(define (rows r)
  (let loop ((r r) (rows (list)))
    (if (zero? r)
        rows
        (loop (- r 1) (append (row r) rows)))))

そして、これが出力です：

> (rows 4)
(1 1 1 1 2 1 1 3 3 1)

基本ケースは(= r c)、最初の関数と(zero? r)2番目の関数にあります。

下付き文字を明確に記述したい場合は、TeXで使用される表記法を採用できます。下付き文字はアンダースコアで、上付き文字はカレットで、1文字より大きいものは中かっこで囲みます。したがって、表記のVcはV_cになり、表記のVc-1はV_{c-1}になります。

于 2012-09-13T20:46:15.483 に答える
3

ウィキペディアのエントリをガイドとして使用すると、これはリンクで説明されているように、行と列が指定されたパスカル三角形の値を計算するためのアルゴリズムの簡単な実装です。

#lang racket

(define (pascal row column)
  (define (aux r c)
    (if (zero? c)
        1
        (* (/ (- r c) c)
           (aux r (sub1 c)))))
  (aux (add1 row) column))

たとえば、次の例では、最初の 4 行の値が返されます。行と列の両方がゼロから始まることに注意してください。

(pascal 0 0)

(pascal 1 0)
(pascal 1 1)

(pascal 2 0)
(pascal 2 1)
(pascal 2 2)

(pascal 3 0)
(pascal 3 1)
(pascal 3 2)
(pascal 3 3)

次に、目的の行まですべての値をまとめる手順が必要です。これはラケットで機能します：

(define (pascal-up-to-row n)
  (for*/list ((i (in-range n))
              (j (in-range (add1 i))))
    (pascal i j)))

結果は期待どおりです。

(pascal-up-to-row 4)
> '(1 1 1 1 2 1 1 3 3 1)
于 2012-09-13T20:43:41.463 に答える