learning python teacher asked us to do fibonacci Q.Q

[Johanes]

so basically our teacher asked us to write a code that would calculate the fibonacci sequence

 

after failing the activity im now researching how to actually do the thing she is asking...

 

Spoiler

fibonacci_cache={}
def fibonacci(n):
    if n in fibonacci_cache:
        return fibonacci_cache[n]
    if n ==1:
        value=1
    elif n==2:
        value=1
    elif n>2:
        value=fibonacci(n-1)+fibonacci(n-2)

    fibonacci_cache[n]=value
    return value

for n in range(1,1001):
    print(n, ":", fibonacci(n))
 

 

that is the code i was able to learn from in the internet... now my question is.. how would i make it so i can have user input and then give the answer.

 

example

 

run code>What term are you looking for?>User gives int(100)

then code will run the program and JUST give the 100th term user is looking for.

 

i would just want to learn how to properly do it.

[Sauron]

def fib(n, p1, p2):
	if n <= 1:
		return p1 + p2
	return fib(n - 1, p2, p1+p2)

def fibonacci(n):
	if n < 2:
		return 1
	return fib(n - 2, 1, 1)

print(fibonacci(int(input("What term are you looking for? "))))

This is (arguably) a more elegant way of doing it, though if you want to print every term along the way it's much more efficient to do it within the function and only call it once:

 

def fib(n, p1, p2):
        print(p2)
        if n <= 1:
                return p1 + p2
        return fib(n - 1, p2, p1+p2)

def fibonacci(n):
        print(1)
        if n < 2:
                return 1
        return fib(n - 2, 1, 1)

fibonacci(int(input("What term are you looking for? ")))

 

[dado1209]

I haven't programmed in quite a while but here is a working code.

Spoiler

int main()
{
int n;
cin>>n;
int a=0;
int b=1;
int c;
int d;
int fib;
for(int i=0;i<n;i++)
{
    c=a;
    d=b;
    fib=c+d;
    a=b;
    b=fib;
}
cout<<fib<<endl;
}

You start of with setting 2 variables as the first 2 numbers of the fibonacci sequence,they are gonna be the numbers a and b here, then you enter the for loop that will be done n times. So the idea for the sequence is pretty simple, you first save the last 2 fibonacci numbers in the variables c and d and their sum will be next fibonacci number. After that you just update the previous 2 numbers and repeat. Hope it helps.

 

Edit: just noticed you asked for python lol. But I think you get the idea here.

[Johanes]

15 minutes ago, dado1209 said:

I haven't programmed in quite a while but here is a working code.

  Hide contents

int main()
{
int n;
cin>>n;
int a=0;
int b=1;
int c;
int d;
int fib;
for(int i=0;i<n;i++)
{
    c=a;
    d=b;
    fib=c+d;
    a=b;
    b=fib;
}
cout<<fib<<endl;
}

You start of with setting 2 variables as the first 2 numbers of the fibonacci sequence,they are gonna be the numbers a and b here, then you enter the for loop that will be done n times. So the idea for the sequence is pretty simple, you first save the last 2 fibonacci numbers in the variables c and d and their sum will be next fibonacci number. After that you just update the previous 2 numbers and repeat. Hope it helps.

 

Edit: just noticed you asked for python lol. But I think you get the idea here.

O_o is dat python code??

 

edit.. checkd it.. its not... is dat C?

[Johanes]

18 minutes ago, Sauron said:

def fib(n, p1, p2):
	if n <= 1:
		return p1 + p2
	return fib(n - 1, p2, p1+p2)

def fibonacci(n):
	if n < 2:
		return 1
	return fib(n - 2, 1, 1)

print(fibonacci(int(input("What term are you looking for? "))))

This is (arguably) a more elegant way of doing it, though if you want to print every term along the way it's much more efficient to do it within the function and only call it once:

 

def fib(n, p1, p2):
        print(p2)
        if n <= 1:
                return p1 + p2
        return fib(n - 1, p2, p1+p2)

def fibonacci(n):
        print(1)
        if n < 2:
                return 1
        return fib(n - 2, 1, 1)

fibonacci(int(input("What term are you looking for? ")))

 

thanks man... this is exactly what i was looking for.. ama start learning woooo

[dado1209]

Yup its C++. Didn't check which language you were asking for before I started.

[Beskamir]

Recursively you'll be waiting for a while before you get the 100th term. You should use a loop instead.

[vorticalbox]

1 hour ago, Beskamir said:

Recursively you'll be waiting for a while before you get the 100th term. You should use a loop instead.

We should do some benchmarking because I doubt there is much in it.

[Beskamir]

52 minutes ago, vorticalbox said:

We should do some benchmarking because I doubt there is much in it.

If memory serves me well, anything beyond 40 will take well over several minutes/hours to compute if you're recomputing everything instead of using some form of caching.

[vorticalbox]

22 minutes ago, Beskamir said:

If memory serves me well, anything beyond 40 will take well over several minutes/hours to compute if you're recomputing everything instead of using some form of caching.

This for recursive or loop?

[Beskamir]

1 hour ago, vorticalbox said:

This for recursive or loop?

The naive recursive implementation doesn't cache results and thus recomputes everything for each term. Thus you end up with O(2^n) which is exponential and thus after just a couple dozen terms you'll have so many computations that the universe will end before your program does. This covers it pretty well but it doesn't mention that you can use caching with recursion https://medium.com/@syedtousifahmed/fibonacci-iterative-vs-recursive-5182d7783055 (which I admittedly forgot about when I wrote my first comment here too)

[Johanes]

6 hours ago, Beskamir said:

The naive recursive implementation doesn't cache results and thus recomputes everything for each term. Thus you end up with O(2^n) which is exponential and thus after just a couple dozen terms you'll have so many computations that the universe will end before your program does. This covers it pretty well but it doesn't mention that you can use caching with recursion https://medium.com/@syedtousifahmed/fibonacci-iterative-vs-recursive-5182d7783055 (which I admittedly forgot about when I wrote my first comment here too)

well my earlier code did diz... 

 

[Beskamir]

14 hours ago, Johanes said:

well my earlier code did diz... 

 

Good job! You're storing the results and not recomputing everything as needed.

[Dat Guy]

On 9/3/2019 at 7:56 PM, dado1209 said:

Didn't check which language you were asking for before I started.

AFAICS no specific language was requested.

[vorticalbox]

1 hour ago, Dat Guy said:

AFAICS no specific language was requested.

titles says "python" so i would assume python but seeing as you;re technically correct incoming javascript

 

const fib = (n, p1, p2) => n <= 1 ? p1 + p2 : fib(n - 1, p2, p1 + p2);
const finonacci = (n) => n < 2 ? 1 : fib(n - 2, 1, 1);
console.log(finonacci(100));

 

[Dat Guy]

Incoming Common Lisp:

(defun fib (n &optional (x 0) (y 1))
  (if (zerop n) nil (cons x (fib (1- n) y (+ x y)))))
  
;; technically, it already "outputs" the row by calling the function...
;; you could use (write (fib 5)) though.
(fib 5)

I think that APL would even be more elegant though ...

[straight_stewie]

Since we are doing python, we get an easy understanding of the extremely elegant and fast algorithm called Fast Doubling.

def fibonacci_doubling(n):
  """ Still involves recursion, but has a complexity of only O(logn) """
    if n == 0:
        return (0, 1)
    else:
        a, b = fibonacci_doubling(n // 2)
        c = a * ((b * 2) - a)
        d = a * a + b * b
        if n % 2 == 0:
            return (d, c + d)
        else:
            return (c, d)


if __name__ == "__main__":
    for n in range(20):
        print(fibonacci_doubling(n))
    # As a demonstration of this algorithm's speed, here is a large n.
    print(fibonacci_doubling(10000))

 

[tobeornottobealttfan]

a, b = 0, 1
z = []
n = int(input('Fibonacci series upto: '))
while a <= n:
	z.append(a)
	k  = b
	b = a + b
	a = k
print(z)

Try this one....

[camjocotem]

>++++++++++>+>+[[+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[[-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>]<<<]

Here's some infinite fibonacci in brainfuck

[Johanes]

thanks for all the replies^_^

[Dragoby]

What I would recommend doing here is the following as it puts this into one function and is quite fast depending on how far you go

Note there are still more efficient ways to do this using generators but that is becoming quite complex

 

def getFibonacciNumber(requested, returnAll=False):
    '''
	This is used to collect a certain index of the fibonacci
    sequence.  If asked this can also return all numbers
    up to a certain position
    '''
    
    values = dict()
    for index in range(1, requested + 1):
        
        previousFirst = values.get(index - 2, 0)
        previousSecond = values.get(index -1, index)
        
        current = previousFirst + previousSecond
        values[index] = current

    if returnAll:
        return values.values()
    return values.get(requested)
    
# This will get you the 100th number
print getFibonacciNumber(100)

# This will get you all numbers up to the 100th
print getFibonacciNumber(100, returnAll=True)

Hope that can help

Cheers!