2016-07-21 2 views
2

Вот мой способ построения последовательности Фибоначчи в виде списка, значения которых не превышает х:Альтернативный способ построения списка до тех пор, пока предикат не будет удовлетворен?

(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

Будучи, что вы отправили это рэкетом ... Это может быть решением проблемы, но я изменить одну часть, которая является если это проблема. Я надеюсь, что это помогает

// я = число начать с, х = число идти до

(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 Я добавил, что в последнюю минуту, на самом деле не проверял, работает ли она, я привык к тому, что мне не разрешают использовать определение или let/set .. – Javant

+0

Ваши новые функции 'fibs-upto' и' fibs-help' переучитывают '(fib i)'. Вы должны вернуть аргументы '(define ans (fib i))' local. Вам просто нужно было написать 'ans' вместо' (ans) '. (Помните, что круглые скобки означают функцию приложения в Racket) –

1

, если вы просто хотите получить список чисел Фибоначчи, вам может, например,

(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