Rosetta Code

Fibonacci n-step number sequences: Difference between revisions

Page Discussion

Fibonacci n-step number sequences (view source)

Revision as of 18:01, 9 March 2015

645 bytes removed ,  9 years ago
→‎{{header|Racket}}: Much improved & shortened code; note that the two functions are nearly identical, which means that one is redundant.
m (→‎{{header|Racket}}: Minor improvements, mostly remove the no-longer-needed `local`)
(→‎{{header|Racket}}: Much improved & shortened code; note that the two functions are nearly identical, which means that one is redundant.)
Line 2,089:
{{incomplete|Racket|Lucas?}}
<lang Racket>#lang racket
;; fib-n : Nat x Nat -> [ListListof Nat]
;; Outputs the first xlen numbers in the n-step fibonacci sequence, n > 1
(define (fib-n n xlen)
(define lon
(cond [(= x 0) empty]
(if [(= xzero? 1len) '(1)]
[(=cons x1 2(build-list (min (sub1 len) n) '(1λ(i) 1(expt 2 i))))))]
(if (<= len n) lon
[(<= x (add1 n)) (list* 1 1 (build-list (- x 2) (λ (y) (expt 2 (add1 y)))))]
(reverse (accfor/fold ([lon (reverse lon) step))]))▼
[else (define first-values (list* 1 1 (build-list (- n 1) (λ (x) (expt 2 (add1 x))))))
(define[_ (addin-valuesrange lon(- ylen (add1 accn)))])
(condcons [(=for/sum y([m 0(in-list lon)] acc[_ (in-range n)]) m)
[else (add-values (rest lon) (sub1 y) (+ (first lon) acc))]))
(define (acc lon y)
(cond [(= y x) lon]
[else (acc (cons (add-values lon n 0) lon) (add1 y))]))
(reverse (acc (reverse first-values) (add1 n)))]))
 
;; fib-list : [ListListof Nat] x Nat -> [ListListof Nat]
;; Given a list of natural numbers, the length of the list becomes the
;; size of the step, and outputs the first xn numbers of the sequence,
;; (lenlength lon) > 1
(define (fib-list lon xn)
(define steplen (length lon))
(condif [(<= xn steplen) (take lon] n)
(reverse (for/fold [(<[lon x(reverse steplon)])
(define[_ (in-range (extract-values lonn ylen))])
(condcons [(=for/sum y([m 0(in-list lon)] empty[_ (in-range len)]) m)
[else (cons (first lon) (extract-values (rest lon) (sub1 y)))]))
(extract-values lon x)]
[else (define (add-values lon y acc)
(cond [(= y 0) acc]
[else (add-values (rest lon) (sub1 y) (+ (first lon) acc))]))
(define (acc lon y)
(cond [(= y x) lon]
[else (acc (cons (add-values lon step 0) lon) (add1 y))]))
▲ (reverse (acc (reverse lon) step))]))
 
;; Now compute the series:
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/215138"