Re: [Bug-apl] Fibonacci sequence

[Elias Mårtenson]

Thanks. Interesting solutions.

Frederick, AFAICT your solution has a time complexity of O(n²). Is there a one-line solution that (like David's) is O(n) but does not use an explicit loop?

Regards,

Elias

On 4 July 2014 09:12, Frederick H. Pitts <address@hidden> wrote:

Elias,

        While Jurgen's solution is correct for the problem as you stated it,
'Problem 3 - Tell a Fib' in
https://studentcompetitions-general.s3.amazonaws.com/testing-challenge/dyalog/2014%20PhaseI%20Problems.pdf
actually asks for the first n Fibonacci numbers, not the Fibonacci
sequence up to a given number.

        A GNU APL solution for the problem as stated in the challenge is:

F ← { ⍎ , ⊃ ((⍵>1) (⍵=1) (⍵=0)) / ( 'λ , + / ¯2 ↑ λ ← F ⍵−1' ) '1'
'0⍴0' }

This solution returns an empty vector for F 0, 1 for F 1 and
        1 1 2 3 5 8 13 21 34 55
for F 10.

Regards,

Fred
Retired Chemical Engineer

On Thu, 2014-07-03 at 22:12 +0800, Elias Mårtenson wrote:
> I was playing around with solving the Dyalog challenge, and I found
> them pretty easy with the exception of one.
>
>
> The goal was to write a lambda function that given a single integer,
> returns a list of the Fibonacci series up to that number.
>
>
> The only way I can think of solving it is by using a full function and
> a loop. That can't possibly be the easiest way.
>
>
> Any suggestions?
>
>
> Regards,
> Elias