[PYTHON] Thank you for the Fibonacci sequence.

Hello. I tried various ways of writing in my own way.

I would appreciate it if you could refer to it. The following description is a familiar one.

fib_1.py


def fib(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    else:
        return fib(n-1) +fib(n-2) 

I think there is also such a way of writing.

fib_2.py


def fib(n):
    if n == 1 or n == 2:
        return n-1
    return fib(n-1) +fib(n-2) 

I was happy to clap my hands because I was able to optimize it for a simple description, There are many duplicate calculations, so I want to optimize it somehow. Prepare a memo by referring to the advice of an expert, It seems that the calculation can be reduced by extracting from the applicable ones.

fib_3.py


class fib:
    def __init__(self):
        self.table ={}
    def cal(self,n):
        if n <= 2:
            return n-1
        
        if n in self.table:
            return self.table[n]
        
        self.table[n] = self.cal(n-2)+self.cal(n-1)
        return self.table[n]

fib_sequence = fib()

Recursive + memo, I see. You can also do this. I played with it a little.

fib_4.py


def fib(n):
    if n <= 2:
        return n-1
    
    if n in memo:
        return memo[n]
    memo[n] = fib(n-2)+fib(n-1)

    return memo[n]

memo = {}

There seems to be an approach called greedy algorithm other than simplifying with memos, It will be done again this time.

Imagine what you want to do It's fun to experiment with different approaches.

Coco also had a method using a for statement. Great!!

If you are in trouble because you can't get an image, lower the level to one rank and I think you should do a preparatory exercise in the article here. It's helpful, this was also a great article.

Recommended Posts

Thank you for the Fibonacci sequence.
Thank you for registering 100,000 paiza.
Sample program for finding Fibonacci sequence
Fibonacci sequence (I can't ask you again)
A shell program that displays the Fibonacci sequence
Fibonacci sequence using Python
[Python] A program for finding the Fibonacci sequence (recursive function, divide-and-conquer method, dynamic programming method)
Implementation of Fibonacci sequence
That ... can't you see the process you're running? The reason for
Django Make choices only for the facility you belong to
Kaggle for the first time (kaggle ①)
For the G test 2020 # 2 exam
Kaguru for the first time
What is the interface for ...
Can you delete the file?