Python Fibonacci

by Cristina | Aug 17, 2021 | Python

In this lesson we will analyze some algorithmsin Python to check if a number belongs to the Fibonacci sequence.

In the previous lesson we studied how to print a Fibonacci sequence of variable length, each time decided by the user.

We have both an iterative and a recursive solution, using functions as well.

In this lesson instead ask the user to enter an integer and the program in Python will be able to tell if it is a Fibonacci number or not.

We will develop different solutions and analyze them.

Python Fibonacci – check if a number is Fibonacci

We study a first approach to a possible solution to the proposed problem.

The first thing that comes to mind, without knowing any rules, is to generate the Fibonacci numbers up to the input entered by the user and check if this number is contained in it.

We develop the solution using an iterative solution that will stop when the condition is satisfied, in our case when the entered number is found or numbers not greater than it are generated.

We create a sentinel variable, which we will call found for example, and set it to False. After that, this variable will change its value, becoming True only if the value is included in the sequence.

Here is a possible solution:

def check_fib(num):
    found = False
    a = 1
    b = 1
    c = a + b
    print(a,  end=' ')
    print(b,  end=' ')
    while(c <= num):
        print(c, end=' ')
        a = b
        b = c
        c = a + b        
        if(c == num):
            found = True
    if(found):
        print('Found')
    else:
        print('Not Found')
        
n = int(input('Insert a number: ' ))
check_fib(n)

Python Fibonacci - check if a number is Fibonacci - second solution

In this second solution we apply the well-known mathematical rules instead.

In particular, it is said that N is a Fibonacci number if and only if 5 N ^ 2 + 4 or 5 N ^ 2 - 4 is a square number.

We therefore develop an algorithm that satisfies these conditions by importing the math module in order to be able to use the square root (sqrt) function. If the square root is an integer then it means that it is a square number and therefore belongs to the sequence, otherwise it does not belong to it.

def check_fib(n):
    import math
    a = (5 * (n**2)) + 4
    b = (5 * (n**2)) - 4
    return (math.sqrt(a)).is_integer() or (math.sqrt(b)).is_integer()

n = int(input('Insert a number: ' ))
result = check_fib(n)
if (result):
    print('The number is Fibonacci')
else:
    print('The number is not Fibonacci')

Conclusion

In this lesson we learned how to check, in Python, if a number belongs to the Fibonacci sequence or not. In the next few lessons we will talk about lists in Python.

Some useful links

Python lambda function

Use Python dictionaries

Python readline()

Python max()

Break Python

Insertion Sort

Merge Sort

Fibonacci sequence in Python

by Cristina | Aug 17, 2021 | Python

Fibonacci sequence in Python can have different implementation algorithms.

Recall that the Fibonacci sequence is a sequence of positive integers in which each number starting from the third is the sum of the previous two except the first two which are 1, 1.

For example, if N = 9, the terms of the sequence are: 1, 1, 2, 3, 5, 8, 13, 21, 34.

Fibonacci sequence in Python algorithm

So let’s create an algorithm that represents the Fibonacci sequence.

Take a number N as input and display the N terms of the Fibonacci sequence.

To implement this algorithm, first of all we take two variables a and b and assign the value 1 to both. We thus create the first two terms of the Fibonacci sequence that we will immediately print.

Then, we make a for loop to display the N terms with an index i ranging from 0 to N-1. After, within the cycle we calculate the third term c and then exchange a with b and b with c. Finally we print c.

Here is a possible solution:

n = int(input('How many numbers?: ' ))
a,b = 1,1
print(a)
print(b)

for i in range(n):
    c = a+b
    a = b
    b = c
    print(c, end=' ')

Once we understand the procedure, we rewrite the algorithm in a more elegant way, avoiding some instructions, such as the initial prints, and we carry out the exchange in a single line.

Here is the solution:

n = int(input('How many numbers?: ' ))
    
a,b = 1,1

for i in range(n):
    print(a, end=' ')
    a,b = b,a+b
    print()

Fibonacci sequence in Python algorithm – with a function

We can also use a function to solve the algorithm.

def print_fibonacci(length):

    a = 1
    b = 1

    for i in range (length):
        print(a, end=" ")
        a,b=b,a+b

n = int(input('How many numbers?: ' ))
print_fibonacci(n)

We can also add a control input. If a user insert a negative number the program can be request a new number.

def print_fibonacci(length):

    a = 1
    b = 1

    for i in range (length):
        print(a, end=" ")
        a,b=b,a+b

n = int(input('How many numbers?: ' ))
while(n < 0):
    n = int(input('How many numbers? Insert a positive number: ' ))
print_fibonacci(n)

Fibonacci sequence in Python algorithm – recursive solution

Here is the recursive solution to the algorithm. Remember that recursion is when you have a call directly to the function itself. In our case, in fact, we call the function rec_fib within the same function rec_fib.

def rec_fib(n):
    if n > 1:
        return rec_fib(n-1) + rec_fib(n-2)
    return n

n = int(input('How many numbers?: ' ))

for i in range(1,n+1):
    print(rec_fib(i))

Conclusion

In this lesson we studied how to develop a Fibonacci sequence algorithm in Python, in the next lesson we will see how to understand if a number is part of the sequence.

Some useful links

Python lambda function

Use Python dictionaries

Python readline()

Python max()

Break Python

Insertion Sort

Merge Sort

How to generate random numbers in Python

by Cristina | Aug 17, 2021 | Python

How to generate random numbers in Python?

Random numbers are used for many purposes, let’s take some examples to better understand how are work.

First example about how to generate random numbers in Python

Write a program that generates n random numbers in an interval set by the user and displays them in output.

So, first of all, let’s import the random module.

Then we ask you to enter the interval values ​​that we store in two variables, for example named x and y.

We also ask you to enter the amount of random numbers to be generated.

import random

x = int(input('Insert the first number : '))
y = int(input('Insert the first number : '))

n = int(input('How many numbers? : '))

Now we can generate the random numbers with the for loop, using randint in the interval (x, y).

import random

x = int(input('Insert the first number : '))
y = int(input('Insert the first number : '))

n = int(input('How many numbers? : '))

for i in range(n):
  random_number = random.randint(x,y)
  print(random_number,end=' ')

But be careful if the user enters the value of y smaller than x?

The program returns an error at the randint point (x, y) because the value of x must be less than the value of y.

Therefore, we can check the data entered by requesting the user to re-enter the data. Or you can also swap the two variables.

By exchanging the variables we therefore have:

import random

x = int(input('Insert the first number : '))
y = int(input('Insert the first number : '))

if x > y:
    x,y = y,x

n = int(input('How many numbers? : '))

for i in range(n):
  random_number = random.randint(x,y)
  print(random_number,end=' ')

With an input check we could instead write like this:

import random

x = int(input('Insert the first number : '))
y = int(input('Insert the second number : '))

while x > y:
    print('The first number must be smaller than second!')
    x = int(input('Insert the first number : '))
    y = int(input('Insert the second number : '))

n = int(input('How many numbers? : '))

for i in range(n):
  random_number = random.randint(x,y)
  print(random_number,end=' ')

Second example about how to generate random numbers in Python

Generate 100 random numbers from 1 to 200 in steps of 2, sum them and make the average.

In steps of 2 from 1 to 200-1, it means that only odd numbers from 1 to 199 are generated.

So let’s use the randrange function for this purpose which, unlike randint, also allows us to indicate the step.

Here, then, is the complete code of the algorithm on random numbers in Python:

import random

n = 100
sum = 0

for i in range(n):
  random_number = random.randrange(1,200,2)
  print(random_number,end=' ')
  sum += random_number

average= sum / n

print('Average: ', average)

Clearly the calculation of the average is carried out as we have done many times with non-random numbers.

Conclusion

In this lesson we have developed some simple exercises on how to generate random numbers in Python, in the next lessons we will continue to practice again.

Useful links

Python tutorial

Introduzione al linguaggio Python

Create Python matrix

Python lambda function

Python test Lambda Function

Python random number

by Cristina | Aug 17, 2021 | Python

In this lesson we study ho to generate a Python random number.

Random numbers in Python, i.e. pseudorandom numbers, are used by first importing the random module. Then we just put in the script: import random.

If you also try to type help (‘random’) in interactive mode, you will see the specifications of this module, with the functions you can use in your scripts.

After importing the module then we can use all methods to generate the random numbers.

Python random number – random()

The random method generates a random decimal number between 0 and 1.

random.random()

Consequently, numbers with a comma between 0 and 1 are generated.

Python random number – Importing module

In Python it is possible to call only some elements of a module, thus avoiding to call an entire module.

For example, we can import only the functions we need using the keyword from followed by the name of the module, the import and the name of the method you want to import.

Here is a possible example:

from random import random
print(random())

As you can see, in this way it is no longer necessary to indicate random.random(), as in the previous example, but just random() is enough.

It is also possible to import all methods in this way as well:

from random import *

print(random())

print(randint(1,10))

Thus it is possible to use all methods without repeating random every time, but using only the name.

Python random number – randint()

The randint() method generates a random integer in a range specified in parentheses.

random.randint(1, 10)

In this example, random numbers between 1 and 10 are generated.

Python random number – randrange()

The randrange() method generates a random integer, in a range of values ​​such as randint, but the step can be specified.

For example:

random.randrange(1, 10, 2)

In this case, only the odd numbers from 1 to 10 can be generated, therefore: 1, 3, 5, 7, 9.

The step is however optional, in the sense that it can also be indicated only:

random.randrange(1, 10)

And in this case the integers from 1 to 10 can be generated.

So, to generate a Python random number we can use also randrange().

seed()

With this method you can initialize the random number generator.

So let’s take an example:

random.randint(1, 100)

If we run this script we will get a different random number each time.

If instead we first set the seed:

random.seed(10)

random.randint(1, 100)

You will always get the same random number, in this case 74. Now try to change the value of the seed.

Conclusion

These are just some of the random number methods in Python, in the next lesson I will introduce some other methods.

Useful links

Python tutorial

Introduzione al linguaggio Python

Create Python matrix

Python lambda function

Python test Lambda Function