2016-07-21 63 views
2

這是我建立一個斐波那契序列,其值的列表的方式不超過X直到謂詞滿足爲止建立列表的替代方法?

(define (fibs-upto x) 
    (for/list ([i (in-naturals)] 
      #:break (> (fib i) x)) 
      (fib i))) 

有另一種,這樣做不使用#:break的也許更清潔的方式,而不使用#lang lazy建設一個無限的懶惰列表?

回答

2

這是一個解決方案,其中(fib i)僅評估一次。

(define (fibs-upto x) 
    (for*/list ([i  (in-naturals)] 
       [fib-i (in-value (fib i))] 
       #:break (> fib-i x)) 
    fib-i)) 

但它可能是更容易讀懂的標準循環:

(define (fibs-upto x) 
    (define (loop i) 
    (define fib-i (fib i)) 
    (if (> fib-i x) 
     '() 
     (cons fib-i (loop (+ i 1))))) 
    (loop 0)) 

這就是說,它對於上述解決方案fib緩存先前計算值是O(n)是很重要的。

UPDATE

使用sequence-map一個版本:

(define (fibs-upto x) 
    (for/list ([y (sequence-map fib (in-naturals))] 
      #:break (> y x)) 
    y)) 
+0

我喜歡這種類型的標準循環。 –

+0

@bitrauser FWIW我使用'sequence-map'添加了一個版本。 – soegaard

0

是,你在球拍張貼這...這可能是解決問題的辦法,但我確實改變了它的一個部件,它是如果問題很容易解決。我希望這有助於

// I =開始在數量,X =數量要上去

(define (fibs-upto i x) 
    (cond 
    [(> (fib i) x) empty] 
    [else (cons (fib i)(fibs-upto (+ i 1) x))])) 

解決方法

(define (fibs-upto x) 
    (fibs-help 0 x)) 

(define (fibs-help i x) 
    (cond 
    [(> (fib i) x) empty] 
    [else (cons (fib i)(fibs-help (+ i 1) x))])) 
+0

您是否使用了返回過程的'fib'的奇怪實現?如果不是調用它像一個過程'(ans)'會停止程序... – Sylwester

+0

@Sylwester我補充說,最後一分鐘,沒有真正檢查它是否有效,我習慣於不被允許使用define或let/set .. – Javant

+0

您的新'fibs-upto'和'fibs-help'函數重新計算'(fib i)'。你應該把'(define ans(fib i))'局部定義放回去。你只需要寫'ans'而不是'(ans)'。 (請記住括號是指Racket中的函數應用) –

1

如果你只是想Fibonacci數列表,你可以例如

(define (fib-upto limit) 
    (let loop ([fibs '(1 1)]) 
    (let ((fn (+ (first fibs) (second fibs)))) 
     (if (> fn limit) 
      (reverse fibs) 
      (loop (cons fn fibs)))))) 
;; e.g.: 
(fib-upto 100) 
'(1 1 2 3 5 8 13 21 34 55 89) 

如果你想知道建設有停止條件列出的一些慣用的方式,看看展開(或打開右儘管你而要展開) - http://srfi.schemers.org/srfi-1/srfi-1.html#FoldUnfoldMap

相關問題