1

行/列が三角形の対角線に沿うように回転させた、簡潔で怠惰なパスカルの三角形を Clojure で書こうとしています。つまり、次のような lazy-seq の lazy-seq を生成したいと考えています。

((1 1 1 1 ...)
 (1 2 3 4 ...)
 (1 3 6 10 ...)
 ...
 )

私が書いたコードは次のとおりです。

(def pascal
  (cons (repeat 1)
        (lazy-seq
          (map #(map + %1 %2)
               (map #(cons 0 %) (rest pascal)))
               pascal
          )))

各行は、それ自体の右シフトされたバージョンを前の行に追加することによって形成されます。問題は、最初の行(map #(cons 0 %) (rest pascal)))が空であるため、最初の行を通過しないことです。

=> (take 5 (map #(take 5 %) pascal))
((1 1 1 1 1))

これを解決する賢明な方法は何ですか？私は Clojure でのプログラミングにかなりの初心者であり、それに関連する問題について非常に異なる考え方をしているので、経験豊富な人からの提案を本当に感謝しています。

4

2 に答える 2

6

簡潔で怠惰

(def pascal (iterate (partial reductions +') (repeat 1)))

(map (partial take 5) (take 5 pascal))
;=> ((1 1 1 1 1) 
;    (1 2 3 4 5) 
;    (1 3 6 10 15) 
;    (1 4 10 20 35) 
;    (1 5 15 35 70))

しかし、あまりにも怠惰ですか？

(take 5 (nth pascal 10000))
;=> StackOverflowError

再試行

(take 5 (nth pascal 10000))
;=> (0)

ええと、最初からやり直して、もう一度試してください

(def pascal (iterate (partial reductions +') (repeat 1)))
(count (flatten (map (partial take 5) (take 100000 pascal))))
;=> 500000

これらはすべてあなたのヒープにあります

(take 5 (nth pascal 100000))
;=> (1 100001 5000150001 166676666850001 4167083347916875001)
于 2013-03-09T13:30:46.723 に答える
2

pascal は var ではなく、無限の seq を生成する関数であるべきです。

lazy-seq での使用方法については、この質問を確認してください

ところで、これを試してください：

(defn gennext [s sum]
  (let [newsum (+ (first s) sum)]
    (cons newsum
          (lazy-seq (gennext (rest s) newsum)))))

(defn pascal [s]
  (cons s
        (lazy-seq (pascal (gennext s 0)))))

ここに画像の説明を入力

(pascal (repeat 1)) は整数オーバーフロー例外を発生させますが、それは無限のシーケンスを生成することを意味します。+' を使用して、大きな整数を使用できます。

于 2013-03-09T15:53:04.133 に答える