Algoritmo para verificar se um número pertence à série de Fibonacci
Como verificar se um número pertence à série de Fibonacci
Neste artigo vamos criar um algoritmo que permite determinar se um número n fornecido por um usuário pertence à série de Fibonacci ou não.
O que é a sequência de Fibonacci
A sequência (ou série) de Fibonacci é uma sequência de números infinita na qual cada número é a soma dos dois números anteriores a ele.
Essa sequência se inicia com os números 0 e 1, e a partir deles, cada número seguinte é calculado efetuando a soma de seus dois antecessores.
Os dez primeiros números na sequência de Fibonacci são:
0, 1, 1, 2, 3, 5, 8, 13, 21 e 34
Podemos gerar a sequência de Fibonacci usando diversas técnicas distintas. Veja como gerar Fibonacci de forma recursiva e iterativa aqui.
Como saber se um número pertence à série de Fibonacci?
Para determinar se um valor está presente na sequência de Fibonacci, podemos empregar uma propriedade interessante, chamada de Fórmula de Binet, que é descrita a seguir:
“Um número é Fibonacci se e apenas se uma ou ambas as expressões 5*n2 + 4 ou 5*n2 – 4 retornarem um quadrado perfeito.”
Um quadrado perfeito é um número inteiro que pode ser expresso como o quadrado exato de outro número inteiro. Ou seja, é um número que pode ser obtido multiplicando um número por si mesmo.
Veja um algoritmo sugerido para determinação de quadrados perfeitos aqui.
Vamos agora aos algoritmos para determinar se um número qualquer é Fibonacci ou não.
Algoritmo em Português Estruturado
A seguir temos uma sugestão de algoritmo, usando o Portugol Studio, que permite saber se um número n fornecido pelo usuário pertence à série de Fibonacci ou não:
programa
{
inclua biblioteca Matematica --> m
inclua biblioteca Tipos --> t
real num
inteiro raiz
funcao inicio()
{
escreva("Descobrir se número é Fibonacci\n")
escreva("Entre com um número: ")
leia(num)
se (eFibonacci(num)) {
escreva(num + " pertence à série de Fibonacci.")
}
senao {
escreva(num + " não pertence à série de Fibonacci.")
}
}
// Função para determinar se número é quadrado perfeito
funcao logico quadradoPerfeito(real x) {
raiz = t.real_para_inteiro(m.raiz(x, 2.0))
retorne raiz * raiz == x
}
// Função para verificar se número pertence à série de Fibonacci
funcao logico eFibonacci(real n){
// n é Fibonacci se o resultado de 5*n² + 4 ou 5*n² - 4 (ou ambos) for quadrado perfeito.
retorne quadradoPerfeito(5*n*n + 4) ou quadradoPerfeito(5*n*n - 4)
}
}
Testando:
Descobrir se número é Fibonacci Entre com um número: 17711 17711.0 pertence à série de Fibonacci.
Descobrir se número é Fibonacci Entre com um número: 12290 12290.0 não pertence à série de Fibonacci.
Algoritmo em Python
E a seguir temos um algoritmo em Python que permite determinar se um número n fornecido pelo usuário pertence à série de Fibonacci ou não. Para este programa faremos usa da biblioteca padrão de funções matemáticas do Python, o módulo Math:
import math # Função que verifica se n é um quadrado perfeito. def quadradoPerfeito(x): raiz = int(math.sqrt(x)) return raiz*raiz == x # Verifica se número n pertence à série de Fibonacci # n é Fibonacci se o resultado de 5*n*n + 4 ou 5*n*n - 4 ou ambos # forem quadrados perfeitos. def eFibonacci(n): return quadradoPerfeito(5*n*n + 4) or quadradoPerfeito(5*n*n - 4) if __name__=='__main__': print("Verificar se número é Fibonacci") n = int(input('Digite um número qualquer, positivo: ')) if(eFibonacci(n)): print(f"{n} pertence à série de Fibonacci.") else: print(f"{n} não pertence à série de Fibonacci.")
O teste é similar ao do algoritmo anterior.
É isso aí! Nos próximos tutoriais vamos explorar mais algoritmos interessantes e curiosos, como a Torre de Hanoi e a construção de jogos, como o Jogo da Velha e outros.
Escreva um comentário