Fibonacci numbers, with an one-liner in Python 3?
fib = lambda n:reduce(lambda x,n:[x[1],x[0]+x[1]], range(n),[0,1])[0]
(this maintains a tuple mapped from [a,b] to [b,a+b], initialized to [0,1], iterated N times, then takes the first tuple element)
>>> fib(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875L
(note that in this numbering, fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, etc.)
(also note: reduce
is a builtin in Python 2.7 but not in Python 3; you'd need to execute from functools import reduce
in Python 3.)
Fibonacci One-Liner
Inspired on Alex's answer:
# Ruby 1.8.7
f = lambda { |x| x < 2 ? x : f.call(x-1) + f.call(x-2) }
puts f.call(6) #=> 8
# Ruby 1.9.2
f = ->(x){ x < 2 ? x : f[x-1] + f[x-2] }
puts f[6] #=> 8
Fibonacci numbers, with an one-liner in Java?
With stream api this is very easy
Fibonacci series: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.... The first two numbers
of the series are 0 and 1, and each subsequent number is the sum of the previous two.
The series of Fibonacci tuples is similar; you have a sequence of a number and its successor in
the series: (0, 1), (1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 13), (13, 21)....
iterate needs a lambda to specify the successor element. In the case of the
tuple (3, 5) the successor is (5, 3+5) = (5, 8). The next one is (8, 5+8). Can you see the pattern?
Given a tuple, the successor is (t[1], t[0] + t[1]). This is what the following lambda specifies: t ->
new int[]{t[1],t[0] + t[1]}. By running this code you’ll get the series (0, 1), (1, 1), (1, 2), (2, 3), (3,
5), (5, 8), (8, 13), (13, 21).... Note that if you just wanted to print the normal Fibonacci series,
you could use a map to extract only the first element of each tuple:
Stream.iterate(new long[]{0, 1}, t -> new long[]{t[1], t[0] + t[1]})
.limit(10)
.map(t -> t[0])
.forEach(System.out::println);
this is the stream api : https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html
Fibonacci one-liner in Swift
You don't need to actually construct an Array
. You can use the sequence
function to generate the Fibonaccis one at a time:
sequence(first: (0, 1)) { a, b in (b, a + b) }
.prefix(10)
.forEach { a, _ in print(a) }
Output:
0
1
1
2
3
5
8
13
21
34
If you want to know more about the theoretical underpinnings of sequence
, read about anamorphisms.
Why is this Perl one-liner of Fibonacci working?
If we put some space in to make it more readable:
print $f += $z = $f - $z ,$/ for --$z .. 8
Let’s extract the different parts into normal code. First, use a regular for
loop.
for (--$z .. 8) {
print $f += $z = $f - $z ,$/
}
The prefix --
auto-decrement operator will take the uninitialized variable $z
, cast it to 0, subtract 1, and return -1
. This is basically the same as assigning -1
to $z
.
We loop from -1 to 8. These numbers are irrelevant, since they are assigned to $_
, which is never used. Basically we just loop 10 steps. The variable used in this step is irrelevant. It can be any variable that can be assigned to, which is why $!
-- the OS error variable works as well.
We can simplify the statement to
$z = -1;
for (0 .. 9)
The print statement basically prints two things:
$f += $z = $f - $z
and
$/
Two statements separated by a comma ,
, meaning it is a list. The predefined variable $/
is the input record separator; it is a newline by default (OS dependent). print
takes a list of arguments, which is how this is meant to work. print
with automatic newline is the same as say
. So we can exchange that and simplify the code to:
say $f += $z = $f - $z
Let’s untangle that assignment. It is basically two statements, done in sequence from right to left, ending with a print:
$z = $f - $z
$f += $z
say $f
If we put it together, we get:
$z = -1;
for (0 .. 9) { # loop 10 times
$z = $f - $z; # calculate increment
$f += $z; # increment value
say $f; # print value
}
It works like this:
We know that $z
initially is -1
from the for loop. And since $f
is never used, it will be undefined (which will be cast to 0 when used in subtraction context). So we get:
$z = $f - $z = undef - (-1) = 0 + 1 = 1
$f += $z = 1 => $f = $f + 1 => $f = 1
So the first loop iteration prints 1. Next turn
$z = $f - $z = 1 - 1 = 0
$f += $z = 0 => $f = $f + 0 = 1 + 0 = 1
Next print is 1 too. Next turn
$z = $f - $z = 1 - 0 = 1
$f += $z = 1 => $f = $f + 1 = 1 + 1 = 2
And so on.
Fibonacci sequence with numbers in 1 line and without using list or array
To calculate the next Fibonacci number simply add together the two previous values. You can do this in a for loop using variables declared outside the loop to hold the previous two values.
Use this statement within your loop
print (value, end = '')
This will print the sequence all on one line with each value separated by a space.
n = int(input())
fib0 = 0
fib1 = 1
for x in range(0, n):
nextFib = fib0 + fib1
fib0 = fib1
fib1 = nextFib
print(fib0 , end = ' ')
How to write the Fibonacci Sequence?
There is lots of information about the Fibonacci Sequence on wikipedia and on wolfram. A lot more than you may need. Anyway it is a good thing to learn how to use these resources to find (quickly if possible) what you need.
Write Fib sequence formula to infinite
In math, it's given in a recursive form:
In programming, infinite doesn't exist. You can use a recursive form translating the math form directly in your language, for example in Python it becomes:
def F(n):
if n == 0: return 0
elif n == 1: return 1
else: return F(n-1)+F(n-2)
Try it in your favourite language and see that this form requires a lot of time as n gets bigger. In fact, this is O(2n) in time.
Go on on the sites I linked to you and will see this (on wolfram):
This one is pretty easy to implement and very, very fast to compute, in Python:
from math import sqrt
def F(n):
return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))
An other way to do it is following the definition (from wikipedia):
The first number of the sequence is 0,
the second number is 1, and each
subsequent number is equal to the sum
of the previous two numbers of the
sequence itself, yielding the sequence
0, 1, 1, 2, 3, 5, 8, etc.
If your language supports iterators you may do something like:
def F():
a,b = 0,1
while True:
yield a
a, b = b, a + b
Display startNumber to endNumber only from Fib sequence.
Once you know how to generate Fibonacci Numbers you just have to cycle trough the numbers and check if they verify the given conditions.
Suppose now you wrote a f(n) that returns the n-th term of the Fibonacci Sequence (like the one with sqrt(5) )
In most languages you can do something like:
def SubFib(startNumber, endNumber):
n = 0
cur = f(n)
while cur <= endNumber:
if startNumber <= cur:
print cur
n += 1
cur = f(n)
In python I'd use the iterator form and go for:
def SubFib(startNumber, endNumber):
for cur in F():
if cur > endNumber: return
if cur >= startNumber:
yield cur
for i in SubFib(10, 200):
print i
My hint is to learn to read what you need. Project Euler (google for it) will train you to do so :P
Good luck and have fun!
Fibonacci sequence in Ruby (recursion)
Try this
def fibonacci( n )
return n if ( 0..1 ).include? n
( fibonacci( n - 1 ) + fibonacci( n - 2 ) )
end
puts fibonacci( 5 )
# => 5
check this post too Fibonacci One-Liner
and more .. https://web.archive.org/web/20120427224512/http://en.literateprograms.org/Fibonacci_numbers_(Ruby)
You have now been bombarded with many solutions :)
regarding problem in ur solution
you should return n
if its 0
or 1
and add
last two numbers not last and next
New Modified version
def fibonacci( n )
return n if n <= 1
fibonacci( n - 1 ) + fibonacci( n - 2 )
end
puts fibonacci( 10 )
# => 55
One liner
def fibonacci(n)
n <= 1 ? n : fibonacci( n - 1 ) + fibonacci( n - 2 )
end
puts fibonacci( 10 )
# => 55
Related Topics
Best Ruby Idiom for "Nil or Zero"
Finding the Session Id in Rails 3
Rails Migration Changing Column to Use Postgres Arrays
How to Validate Members of an Array Field
Maintaining Cookies Between Mechanize Requests
What Is the "Equals Greater Than" Operator => in Ruby
How to Change "Devise: Password Reset Instruction Email's Subject"
Getting Viewable Text Words via Nokogiri
Rendering a Partial from a Controller in Rails
Parse CSV File with Header Fields as Attributes for Each Row
How to Spawn a Child Process in Ruby
Multiple Sinatra Apps Using Rack-Mount
Ruby Dsl (Domain Specific Language) Repositories, Examples
Ruby: Compare 2 Arrays for Matches, and Count the Number of Match Instances