Sequência de Fibonacci: diferenças entre revisões
+Texto de es:Sucesión de Fibonacci. +Síntese dos inúmeros exemplos repetidos: bastam só 3(!) em pseudocódigo. Ver Project:Esplanada/propostas/Mover "implementações de algoritmos" para o domínio "Anexo" (15abr2011) |
|||
Linha 56: | Linha 56: | ||
Note que a Sequência de Fibonacci esta no resultado de cada posição; |
Note que a Sequência de Fibonacci esta no resultado de cada posição; |
||
1,1,2,3,5,8 |
1, 1, 2, 3, 5, 8, ... |
||
== Representações alternativas == |
|||
== Fórmula explícita == |
|||
Para analizar a sequência de Fibonacci (e, em geral, quaisquer sequências) é conveniente obter outras maneiras de representá-la matematicamente. |
|||
=== Função geradora === |
|||
Uma função geradora para uma sequência qualquer <math>a_0,a_1,a_2,\dots</math> é a função <math>f(x) = a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+\cdots</math>, ou seja, uma [[série potências formais]] em que cada coeficiente é um elemento da sequência. Os números de Fibonacci possuem a seguinte função geradora |
|||
:<math>f\left(x\right)=\frac{x}{1-x-x^2}</math> |
|||
Quando se expande esta função em potências de <math>x\,</math>, os coeficientes são justamente os termos da sequência de Fibonacci: |
|||
:<math>\frac{x}{1-x-x^2}=0x^0+1x^1+1x^2+2x^3+3x^4+5x^5+8x^6+13x^7+\cdots</math> |
|||
=== Fórmula explícita === |
|||
Conforme mencionado por [[Johannes Kepler]], a taxa de crescimento dos números de Fibonacci, que é ''F''(''n'' + 1) /''F''(''n''), tende à [[Proporção áurea]], denominada φ. Esta é a raiz positiva da equação de segundo grau ''x''² − ''x'' − 1 = 0, então φ² = φ + 1. Se multiplicarmos ambos os lados por φ<sup>''n''</sup>, teremos φ<sup>''n''+2</sup> = φ<sup>''n''+1</sup> + φ<sup>''n''</sup>, então a função φ<sup>''n''</sup> é uma sequência de Fibonacci. É possível demonstrar que a raiz negativa da mesma equação, 1 − φ, tem as mesmas propriedades, então as duas funções φ<sup>''n''</sup> e (1 − φ)<sup>''n''</sup> formam outra base para o espaço. |
Conforme mencionado por [[Johannes Kepler]], a taxa de crescimento dos números de Fibonacci, que é ''F''(''n'' + 1) /''F''(''n''), tende à [[Proporção áurea]], denominada φ. Esta é a raiz positiva da equação de segundo grau ''x''² − ''x'' − 1 = 0, então φ² = φ + 1. Se multiplicarmos ambos os lados por φ<sup>''n''</sup>, teremos φ<sup>''n''+2</sup> = φ<sup>''n''+1</sup> + φ<sup>''n''</sup>, então a função φ<sup>''n''</sup> é uma sequência de Fibonacci. É possível demonstrar que a raiz negativa da mesma equação, 1 − φ, tem as mesmas propriedades, então as duas funções φ<sup>''n''</sup> e (1 − φ)<sup>''n''</sup> formam outra base para o espaço. |
||
Linha 71: | Linha 81: | ||
Quando ''n'' tende a infinito, o segundo termo tende a zero, e os números de Fibonacci tendem à exponencial φ<sup>''n''</sup>/√5. O segundo termo já começa pequeno o suficiente para que os números de Fibonacci possam ser obtidos usando somente o primeiro termo arredondado para o inteiro mais próximo. |
Quando ''n'' tende a infinito, o segundo termo tende a zero, e os números de Fibonacci tendem à exponencial φ<sup>''n''</sup>/√5. O segundo termo já começa pequeno o suficiente para que os números de Fibonacci possam ser obtidos usando somente o primeiro termo arredondado para o inteiro mais próximo. |
||
=== Forma matricial === |
|||
== Calculando números de Fibonacci == |
|||
Na prática não é conveniente calcular os números de Fibonacci usando potências da [[proporção áurea]], a não ser para valores pequenos de ''n'', já que os erros de arredondamento se acumulam e a precisão dos números de [[ponto flutuante]] normalmente não será suficiente. |
|||
Para argumentos muito grandes, quando utiliza-se um computador [[bignum]], é mais fácil{{carece de fontes}} calcular os números de Fibonacci usando a seguinte equação matricial: |
|||
A implementação direta da definição recursiva da sequência de Fibonacci também não é recomendável porque os mesmos valores são calculados muitas vezes (a não ser que a [[linguagem de programação]] guarde automaticamente os valores calculados nas chamadas anteriores da mesma função com o mesmo argumento). Por esse motivo, normalmente calcula-se os números de Fibonacci "de baixo para cima", começando com os dois valores 0 e 1, e depois repetidamente substituindo-se o primeiro número pelo segundo, e o segundo número pela soma dos dois anteriores. |
|||
Para argumentos muito grandes, quando utiliza-se um computador [[bignum]], é mais fácil calcular os números de Fibonacci usando a seguinte equação matricial: |
|||
:<math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = |
:<math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = |
||
Linha 85: | Linha 92: | ||
onde a potência de ''n'' é calculada elevando-se a matriz ao quadrado repetidas vezes. |
onde a potência de ''n'' é calculada elevando-se a matriz ao quadrado repetidas vezes. |
||
Um exemplo de aplicação desta expressão matricial é na demonstração do [[teorema de Lamé]] sobre o [[algoritmo de Euclides]] para o cálculo do [[MDC]]. Veja por exemplo o capítulo [[b:Teoria de números/Máximo divisor comum| |
Um exemplo de aplicação desta expressão matricial é na demonstração do [[teorema de Lamé]] sobre o [[algoritmo de Euclides]] para o cálculo do [[MDC]]. Veja por exemplo o capítulo sobre o [[b:Teoria de números/Máximo divisor comum|máximo divisor comum]] do [[Wikilivros|wikilivro]] de [[b:Teoria de números|Teoria de números]]. |
||
A seguir, um algoritmo desenvolvido em [[Java (linguagem de programação)|Java]], o qual imprime o número de termos da sequência, determinado pela variável "x". |
|||
[[Ficheiro:Fibonacci molle.JPG|thumb|Representação da Série de Fibonacci na Molle Antonelliana em Turim, Itália.]] |
[[Ficheiro:Fibonacci molle.JPG|thumb|Representação da Série de Fibonacci na Molle Antonelliana em Turim, Itália.]] |
||
== Tipos de algoritmos == |
|||
Há diversos [[algoritmo]]s (métodos) para calcular o <math>n</math>-ésimo elemento da sequência de Fibonacci, sendo que os mais comuns empregam um das seguintes abordagens: |
|||
[[Ficheiro:AlgoritmoFibonacci.png]] |
|||
* Recursiva |
|||
* Iterativa |
|||
=== Algoritmo Recursivo em Java === |
|||
* Dividir para conquistar |
|||
<source lang="java"> |
|||
//Classe java |
|||
public class Fibonacci { |
|||
public static int calcular(int n) { |
|||
if (n == 0 || n == 1) |
|||
return n; |
|||
else |
|||
return calcular(n - 1) + calcular(n - 2); |
|||
} |
|||
} |
|||
// Impressão |
|||
public class Main { |
|||
public static void main(String[] args) { |
|||
Fibonacci f = new Fibonacci(); |
|||
for (int x = 1; x < 10; x++) { |
|||
int y = f.calcular(x); |
|||
System.out.println("o Fibonacci de "+x+" é " + y); |
|||
} |
|||
} |
|||
} |
|||
</source> |
|||
=== Algoritmo recursivo eficiente em Java === |
|||
Função que exibe recursivamente a sequência f(n). |
|||
<source lang="java"> |
|||
{ |
|||
fibCalc(20, 0, 1); |
|||
} |
|||
int fibCalc(int n, int a, int b) { |
|||
System.out.println(a); |
|||
return (n == 0) ? a : fibCalc(--n, a + b, a); |
|||
} |
|||
</source> |
|||
=== Algoritmo em Java em apenas uma única linha === |
|||
Este algoritmo demonstra uma forma de calcular a seqüência de Fibonacci de forma interativa com o usuário. Antes de gerar ele irá dialogar para definir quantos itens da seqüencia deseja-se calcular. Este é um dos mais rápidos algoritmo disponíveis para Java para realizar esta operação, sendo muito vezes mais eficiente que a versão recursiva. |
|||
<source lang="java"> |
|||
for(int i=Integer.valueOf(("0"+System.out.printf("Digite o limite de itens da sequência: \n")).charAt(0))-48, n1=0, n2=1, limite=(new Scanner(System.in).nextInt()); i<limite;n1=n2-n1, System.out.print((i==0)?"0, 1":", "+(n2=n2+n1)), i++){}; |
|||
</source> |
|||
=== Algoritmo Recursivo em Scheme === |
|||
<source lang="Scheme"> |
|||
(define (fib n) |
|||
(cond ((= n 0) 0) |
|||
((= n 1) 1) |
|||
(else (+ (fib (- n 1)) (fib (- n 2)))))) |
|||
</source> |
|||
=== Algoritmo Iterativo em Scheme === |
|||
<source lang="Scheme"> |
|||
(define (fib n) |
|||
(define (iter i p r) |
|||
(if (= i n) |
|||
r |
|||
(iter (+ i 1) r (+ p r)))) |
|||
(cond ((= n 0) 0) |
|||
((= n 1) 1) |
|||
(else (iter 2 1 1)))) |
|||
</source> |
|||
=== Algoritmo em ECMAScript / JavaScript === |
|||
<source lang="javascript"> |
|||
/* Algoritmo Recursivo da Sequência Fibonacci */ |
|||
function fibonacci(i) { |
|||
return i < 2 ? i : fibonacci(i - 1) + fibonacci(i - 2); |
|||
} |
|||
/* Chamando … */ |
|||
for(i = 1; i < 10; i++) { |
|||
alert(fibonacci(i)); |
|||
} |
|||
</source> |
|||
=== Algoritmo recursivo em Python === |
|||
Solução clássica usando recursividade. |
|||
<source lang="Python"> |
|||
# Função recursiva |
|||
def fibo(n): |
|||
if n < 2: |
|||
return n |
|||
else: |
|||
return fibo(n-1) + fibo(n-2) |
|||
for i in range(10): |
|||
print fibo(i) |
|||
</source> |
|||
=== Algoritmo recursivo em R === |
|||
Solução clássica usando recursividade. |
|||
<source lang="Python"> |
|||
# Função recursiva |
|||
fibo = function(n){ |
|||
if(n == 0){ return(0) } #caso base |
|||
if(n == 1){ return(1) } |
|||
if(n>1){ |
|||
output = fibo(n-1) + fibo(n-2) |
|||
return(output) |
|||
} |
|||
if(n < 0){ print("Fibonacci não está definido para negativos") } |
|||
} |
|||
</source> |
|||
=== Algoritmo eficiente em Python === |
|||
Solução em tempo linear com o uso de generators. |
|||
<source lang="Python"> |
|||
# Generator |
|||
def fib(n): |
|||
c, n1, n2 = 0, 0, 1 |
|||
while c < n: |
|||
yield n1 |
|||
n1, n2 = n2, n1 + n2 |
|||
c += 1 |
|||
# Calcular os 10 primeiros termos |
|||
for x in fib(10): |
|||
print x |
|||
</source> |
|||
=== Algoritmo em PHP === |
|||
<source lang="PHP"> |
|||
<?php |
|||
/* Algoritmo Recursivo da Sequência Fibonacci */ |
|||
function fibonacci($i) { |
|||
return $i < 2 ? $i : fibonacci($i-1) + fibonacci($i-2); |
|||
} |
|||
/* Chamando … */ |
|||
for($i=1;$i<10;$i++) { |
|||
echo fibonacci($i)."\r\n"; |
|||
} |
|||
?> |
|||
</source> |
|||
Uma forma extremamente mais rápida |
|||
<source lang="PHP"> |
|||
<?php |
|||
function fibonacci ($number=10, $returnLast = false) |
|||
{ |
|||
$start = array(); |
|||
$start[1] = 1; |
|||
$start[2] = 1; |
|||
if ( $number == 1 ) { |
|||
unset($start[2]); |
|||
} |
|||
for ( $i = 3; $i <= $number; $i ++ ) { |
|||
array_push($start, $start[$i - 2] + $start[$i - 1]); |
|||
} |
|||
return $returnLast === true ? end($start) : $start; |
|||
} |
|||
/* Para utilizar … */ |
|||
echo "<pre>"; |
|||
print_r(fibonacci(10)); |
|||
// |
|||
echo "<pre>"; |
|||
print_r(fibonacci(10,true)); |
|||
?> |
|||
</source> |
|||
=== Algoritmo em Perl === |
|||
<source lang="PERL"> |
|||
# !/usr/bin/perl |
|||
use strict; |
|||
sub fibo { |
|||
return $_[0] < 2 ? $_[0] : fibo($_[0]-1) + fibo($_[0]-2); |
|||
} |
|||
for (1..10){ |
|||
print fibo($_)."\n"; |
|||
} |
|||
</source> |
|||
Modo mais eficiente : |
|||
<source lang="PERL"> |
|||
# !/usr/bin/perl |
|||
use strict; |
|||
my ($a,$b)=(1,2); |
|||
print "$a\n$b\n"; |
|||
for(1..100) { |
|||
($a,$b) = ($b,$a+$b); |
|||
print "$b\n" |
|||
} |
|||
</source> |
|||
=== Algoritmo em C === |
|||
<source lang="C"> |
|||
#include <stdio.h> |
|||
#include <stdlib.h> |
|||
// protótipo da função |
|||
int fibonacci(int x); |
|||
int main(int argc, char *argv[]) |
|||
{ |
|||
int a, i; |
|||
printf("Informe a Sequencia de Fibonacci Desejada: "); |
|||
scanf("%d", &a); |
|||
for(i=0; i<=a-1; i++){ |
|||
printf("O Fibonacci do Numero: %d e: %d\n", i+1, fibonacci(i+1)); |
|||
} |
|||
system("PAUSE"); |
|||
return 0; |
|||
} |
|||
// função com retorno e entrada de parametro por valores : o,1,4,9,6 |
|||
int fibonacci(int x){ |
|||
if ((x==1)||(x==2)){ |
|||
return 1; |
|||
}else{ |
|||
return fibonacci(x-1)+fibonacci(x-2); |
|||
} |
|||
} |
|||
</source> |
|||
Método Alternativo. |
|||
<source lang="C"> |
|||
#include <stdio.h> |
|||
#include <stdlib.h> |
|||
int main() { |
|||
int n_anterior1=0,n_anterior2=1,n=0; |
|||
for(int i = 0;i<15;i++){ |
|||
printf("%d ",n); |
|||
n = n_anterior1 + n_anterior2; |
|||
n_anterior2=n_anterior1; |
|||
n_anterior1=n; |
|||
} |
|||
printf("\n"); |
|||
system("PAUSE"); |
|||
return 0; |
|||
} |
|||
</source> |
|||
=== Algoritmo em Ruby === |
|||
<source lang="Ruby"> |
|||
# Algoritmo Recursivo da Sequência Fibonacci |
|||
def fib(n) |
|||
return n if n<2 |
|||
fib(n-1)+fib(n-2) |
|||
end |
|||
# Chamando… |
|||
for i in (1..10) |
|||
puts fib(i) |
|||
end |
|||
# Ou com memorização |
|||
fib = Hash.new{|hash, n| hash[n] = (n < 2) ? n : hash[n - 1] + hash[n - 2];}; |
|||
(1..100).each do |i| |
|||
puts fib[i] |
|||
end |
|||
</source> |
|||
=== Algoritmo em Ruby sem Recursividade === |
|||
<source lang="Ruby"> |
|||
#utiliza duas variáveis para compor a sequência |
|||
a,b = 0,1 |
|||
for i in (0..10) |
|||
puts a |
|||
a,b = b,a+b |
|||
end |
|||
</source> |
|||
=== Algoritmo em Erlang === |
|||
<source lang="Erlang"> |
|||
fib(0) -> 0 ; |
|||
fib(1) -> 1 ; |
|||
fib(N) when N > 0 -> fib(N-1) + fib(N-2). |
|||
%% Tail recursive |
|||
fibo3(N) -> |
|||
{Fib, _} = fibo3(N, {1, 1}, {0, 1}), |
|||
Fib. |
|||
fibo3(0, _, Pair) -> Pair; |
|||
fibo3(N, {Fib1, Fib2}, Pair) when N rem 2 == 0 -> |
|||
SquareFib1 = Fib1*Fib1, |
|||
fibo3(N div 2, {2*Fib1*Fib2 - SquareFib1, SquareFib1 + Fib2*Fib2}, Pair); |
|||
fibo3(N, {FibA1, FibA2}=Pair, {FibB1, FibB2}) -> |
|||
fibo3(N-1, Pair, {FibA1*FibB2 + FibB1*(FibA2 - FibA1), FibA1*FibB1 + FibA2*FibB2}). |
|||
</source> |
|||
=== Algoritmo em Shell Script (Zsh) === |
|||
<source lang="bash"> |
|||
fibonacci() { |
|||
local a c |
|||
local -F1 b |
|||
a=0 ; b=1 |
|||
print $a |
|||
repeat $1 |
|||
do |
|||
print "${b%.*}" |
|||
c=$a |
|||
a=$b |
|||
((b = c + b)) |
|||
done |
|||
} |
|||
# Chamando… |
|||
fibonacci 10 |
|||
</source> |
|||
=== Algoritmo em bc (comando Unix) === |
|||
<pre> |
|||
define void fibonacci(valor) |
|||
{ |
|||
auto x, y, z, i; |
|||
x = 0; |
|||
y = 1; |
|||
x; |
|||
while (i++ < valor) { |
|||
y; |
|||
z = x; |
|||
x = y; |
|||
y = z + y; |
|||
} |
|||
} |
|||
</pre> |
|||
=== Algoritmo em Pascal === |
|||
<source lang="pascal"> |
|||
program fibonacci (input,output); |
|||
var |
|||
i,n,ni,ni1,ni2:longint; |
|||
begin |
|||
writeln; |
|||
writeln ('NÚMEROS DE FIBONACCI'); |
|||
writeln; |
|||
write('Quantos termos de Fibonacci você quer calcular? '); |
|||
read(n); |
|||
ni:=0; |
|||
ni1:=1; |
|||
ni2:=1; |
|||
for i:=1 to n do |
|||
begin |
|||
write(ni,' '); |
|||
ni:=ni1+ni2; |
|||
ni2:=ni1; |
|||
ni1:=ni; |
|||
end; |
|||
end. |
|||
</source> |
|||
=== Algoritmo em MATLAB === |
|||
<source lang="matlab"> |
|||
a=0; |
|||
b=1; |
|||
c=a+b; |
|||
N=0; |
|||
while N⇐0 |
|||
N=input('Defina limite da sequência fibonacci: '); |
|||
end |
|||
while c⇐N |
|||
disp(num2str(c)) |
|||
a=b; |
|||
b=c; |
|||
c=a+b; |
|||
end |
|||
</source> |
|||
=== Algoritmo em Prompt Script (BAT) === |
|||
<source lang="winbatch"> |
|||
@echo off |
|||
setlocal ENABLEDELAYEDEXPANSION |
|||
set/an=-1 |
|||
set/af0=0 |
|||
set/af1=1 |
|||
:loop |
|||
set/an+=1 |
|||
set/am=%n%-1 |
|||
set/al=%m%-1 |
|||
set /a f%n%=!f%m%!+!f%l%! |
|||
echo F(%n%)=!f%n%! |
|||
pause&goto loop |
|||
</source> |
|||
=== Algoritmo em PROLOG === |
|||
<source lang="prolog"> |
|||
fib(1, 1). |
|||
fib(2, 1). |
|||
fib(X, Y):- X > 1, X1 is X - 1, X2 is X - 2, fib(X1, Z), fib(X2, W), Y is W + Z. |
|||
</source> |
|||
=== Algoritmo em PROLOF (com recursividade terminal) === |
|||
<source lang="prolog"> |
|||
fibT(0,0). |
|||
fibT(1,1). |
|||
fibT(N,Res):- N >1, fibT(N,Res,0,1,2). |
|||
fibT(N,Res,F1,F2,N):- Res is F1+F2. |
|||
fibT(N,Res,F1,F2,CN) :- |
|||
NF2 is F1+F2, |
|||
NCN is CN +1, |
|||
fibT(N,Res,F2,NF2,NCN). |
|||
(Nota: processamento mais eficiente.) |
|||
(Author: Marco Mendão PLR 2011) |
|||
</source> |
|||
=== Algoritmo em Tcl === |
|||
<source lang="Tcl"> |
|||
proc fib {n} { |
|||
if {$n < "2"} { |
|||
return $n |
|||
} |
|||
return [expr [fib [expr $n - 1]] + [fib [expr $n - 2]]] |
|||
} |
|||
# Chamando |
|||
fib 10 |
|||
</source> |
|||
=== Portugues estruturado === |
|||
algoritmo "série de fibonnacci" |
|||
// autor: marquin.freitas - undb -ma 1º período 2009 |
|||
// função: calcula a soma de todos os números da série de fibonacci e mostrando a série perfeitamente |
|||
var |
|||
fibo:inteiro |
|||
n0,n1,n2:inteiro |
|||
I:inteiro |
|||
soma:inteiro |
|||
aux: caracter |
|||
inicio |
|||
n0:=0 |
|||
enquanto n0<2 faca |
|||
escreva("quantos num.? [ n > 1 ]:") |
|||
leia(n0) |
|||
se n0<2 então |
|||
escreval(" digite novamente [pressione enter]") |
|||
leia(aux) |
|||
limpatela |
|||
fimse |
|||
fimenquanto |
|||
escreva("1º numero da seq.: ") |
|||
leia(n1) |
|||
escreva("2º numero da seq.: ") |
|||
leia(n2) |
|||
escreva(" ",n1," ",n2," ") // aqui ele vai mostrar os dois primeiros números que foram digitados |
|||
soma:=n1+n2 |
|||
para I de 1 ate n0 faca |
|||
fibo:=n1+n2 // o 3° número [fibo] é a soma dos dois primeiros |
|||
escreva(fibo," ") |
|||
soma:=soma+fibo// aqui vai acumular a soma de todos os números |
|||
// ele só escreverá o valor de 'fibo' a cada volta do para, por na sequencia de fibonacci |
|||
// não aparece valores repetidos apartir do 3 e sim um novo número resultante da soma dos dois últimos valores |
|||
//***** método da bolha ******* |
|||
// a partir do 3° é atribuído ao 1° número o valor do 2° |
|||
//e o 2° passa a ser o 3° tendo como seu valor, no caso, fibo. |
|||
n1:=n2 |
|||
n2:=fibo |
|||
fimpara |
|||
escreval |
|||
escreval("A soma de todos os números é igual a: ", soma) |
|||
fimalgoritmo |
|||
=== Algoritmo em COBOL === |
|||
<source lang="Cobol"> |
|||
*---------------------- |
|||
300-FIBONACCI SECTION. |
|||
*---------------------- |
|||
IF 999E-REG EQUAL 0 |
|||
MOVE PNULT TO FIB |
|||
ELSE |
|||
IF 999E-REG EQUAL 1 |
|||
MOVE ULT TO FIB |
|||
ELSE |
|||
MOVE 999E-REG TO GDA-POSICAO |
|||
PERFORM 400-CALCULA UNTIL GDA-POSICAO EQUAL 1. |
|||
*---------------------------------------------------------------* |
|||
* |
|||
*-------------------- |
|||
400-CALCULA SECTION. |
|||
*-------------------- |
|||
COMPUTE FIB = ULT + PNULT. |
|||
MOVE ULT TO PNULT. |
|||
MOVE FIB TO ULT. |
|||
SUBTRACT 1 FROM GDA-POSICAO. |
|||
*---------------------------------------------------------------* |
|||
</source> |
|||
=== Algoritmo em Visual Fox Pro === |
|||
<source lang="visualfoxpro"> |
|||
? Fibonacci(22) |
|||
FUNCTION Fibonacci (tnNumeros) |
|||
LOCAL lnNumero, lnNumero1, lnNumero2, lnI, lcRetorno |
|||
lnI = 1 |
|||
lcRetorno = "" |
|||
lnNumero = 1 |
|||
lnNumero1 = 1 |
|||
lnNumero2 = 0 |
|||
FOR lnI = 1 TO tnNumeros STEP 1 |
|||
lcRetorno = lcRetorno + " " + TRANSFORM(lnNumero) |
|||
lnNumero = lnNumero1 + lnNumero2 |
|||
lnNumero2 = lnNumero1 |
|||
lnNumero1 = lnNumero |
|||
ENDFOR |
|||
RETURN lcRetorno |
|||
ENDFUNC |
|||
</source> |
|||
=== Algoritmo em C# === |
|||
<source lang="csharp"> |
|||
public String Fibonacci(int numeros) |
|||
{ |
|||
String retorno = ""; |
|||
int numero = 1; |
|||
int numero1 = 1; |
|||
int numero2 = 0; |
|||
for(int i=0; i < numeros; i++) |
|||
{ |
|||
retorno = retorno + " " + numero.ToString(); |
|||
numero = numero1 + numero2; |
|||
numero2 = numero1; |
|||
numero1 = numero; |
|||
} |
|||
return retorno; |
|||
} |
|||
</source> |
|||
=== Algoritmo em C# (modo com caixa de texto) === |
|||
<source lang="csharp"> |
|||
namespace WindowsFormsApplication4 |
|||
{ |
|||
public partial class Form1 : Form |
|||
{ |
|||
public Form1() |
|||
{ |
|||
InitializeComponent(); |
|||
} |
|||
private void button1_Click(object sender, EventArgs e) |
|||
{ |
|||
if (label1.Text == "0" & label2.Text == "0") { label2.Text = "1"; } |
|||
else { |
|||
int numanterior = int.Parse(label2.Text); |
|||
string numateriorstring = string.Concat(numanterior); |
|||
int num_seguinte = int.Parse(label1.Text); |
|||
num_seguinte = num_seguinte + numanterior; |
|||
string num_seguintestring = string.Concat(num_seguinte); |
|||
label2.Text = num_seguintestring; |
|||
label1.Text = numateriorstring; |
|||
} |
|||
} |
|||
} |
|||
} |
|||
</source> |
|||
<source lang="cpp"> |
|||
=== Algoritmo em C++ === |
|||
<source lang="cpp"> |
|||
#include <iostream.h> |
|||
using namespace std; |
|||
int Fibonacci(int); |
|||
int main() |
|||
{ |
|||
int quantidade; |
|||
cout << "Deseja imprimir quantos numeros?"; |
|||
cin >> quantidade; |
|||
for(int x = 1; x <=quantidade; x++)\\By Regia R. Oliveira |
|||
cout << "O " << x << "# numero de Fibonacci é: " << Fibonacci(x) << "\n"; |
|||
} |
|||
A seguir é apresentado um exemplo de cada um destes tipos de algoritmos em [[pseudocódigo]] |
|||
int Fibonacci(int number){ |
|||
if(number == 0 || number == 1) |
|||
return number; |
|||
else |
|||
return Fibonacci(number - 1) + Fibonacci(number - 2); |
|||
} |
|||
</source> |
|||
=== |
=== Abordagem recursiva === |
||
<source lang="cpp"> |
|||
PROGRAM FIBONACCI |
|||
IMPLICIT NONE |
|||
INTEGER, DIMENSION (1:1000) :: FIB |
|||
INTEGER :: I,N |
|||
WRITE(*,*) "SEQUENCIA DE FIBONACCI COM N ELEMENTOS. INFORME N" |
|||
READ (*,*) N |
|||
FIB(1) = 1 |
|||
FIB(2) = 1 |
|||
WRITE(*,*) !pular linha |
|||
WRITE(*,*) FIB(1) |
|||
WRITE(*,*) FIB(2) |
|||
DO I = 3,N |
|||
FIB(I) = FIB(I-1) + FIB(I-2) |
|||
WRITE(*,*) FIB(I) |
|||
END DO |
|||
PAUSE |
|||
END PROGRAM FIBONACCI |
|||
</source> |
|||
A própria definição da sequência de Fibonacci pode ser tomada como base para implementar um [[algoritmo recursivo]] que gera os termos da sequência, como é mostrado a seguir: |
|||
=== Algoritmo em Haskell === |
|||
'''função''' <math>{\it fib}(n)\,</math> |
|||
''Versão mais lenta.'' |
|||
:'''se''' <math>n<2\,</math> '''então''' |
|||
<source lang="haskell"> |
|||
::'''retorne''' <math>n\,</math> |
|||
fib n |
|||
:'''caso contrário''' |
|||
|n==0 = 0 |
|||
::'''retorne''' <math>{\it fib}(n-1) + {\it fib}(n-2)\,</math> |
|||
|n==1 = 1 |
|||
|otherwise = fib(n-1) + fib(n-2) |
|||
</source> |
|||
''Versão mais rápida.'' |
|||
<source lang="haskell"> |
|||
fibs n = fibGen 0 1 n |
|||
fibGen a b n = for n of |
|||
0 -> a |
|||
n -> fibGen b (a + b) (n - 1) |
|||
</source> |
|||
Apesar de simples, essa estratégia não é recomendável porque os mesmos valores são calculados muitas vezes (a não ser que a [[linguagem de programação]] guarde automaticamente os valores calculados nas chamadas anteriores da mesma função com o mesmo argumento). Uma análise cuidadosa mostra que a complexidade computacional do algoritmo é <math>O(\varphi^n)\,</math>. Por esse motivo, normalmente calcula-se os números de Fibonacci "de baixo para cima",{{carece de fontes}} começando com os dois valores 0 e 1, e depois repetidamente substituindo-se o primeiro número pelo segundo, e o segundo número pela soma dos dois anteriores. |
|||
=== Algoritmo em Visualg 2.0 === |
|||
algoritmo "Sequenciador de Números Fibonacci" |
|||
// Função : Gerar sequências de Fibonacci |
|||
// Autor : Lucas Vinícius Santos da Costa |
|||
// Data : 02/10/2010 |
|||
var |
|||
N1:inteiro //Primeiro termo da série que interage com N2 na obtenção dos outros termos. |
|||
N2:inteiro //Segundo termo da série que interage com N1 na obtenção dos outros termos. |
|||
N:inteiro //resultado da interação entre N1 e N2. |
|||
T:inteiro //Permite ao usuário a definição da quantidade de termos da sequência. |
|||
C:inteiro //Contador que permite a exibição dos T termos requeridos pelo usuário. |
|||
S:inteiro //Efetua a soma dos T termos requeridos pelo usuário. |
|||
inicio |
|||
C<-0 |
|||
escreval("Entre com o número de termos desejados para a sequenciação") |
|||
leia(T) |
|||
N1<-0 |
|||
N2<-1 |
|||
S<-(N1+N2) |
|||
escreval(N1) |
|||
escreval(N2) |
|||
repita |
|||
N<-N1+N2 |
|||
N1<-N2 |
|||
N2<-N |
|||
escreval(N) |
|||
S<-(S+N) |
|||
C<-C+1 |
|||
ate C=(T-2) |
|||
fimrepita |
|||
escreval("Soma dos termos: ",S) |
|||
fimalgoritmo |
|||
Uma outra alternativa é fazer uso da fórmula apresentada na seção anterior, que envolve potências da [[proporção áurea]]. No entanto, isso pode não ser muito conveniente para valores grandes de ''n'', já que os erros de arredondamento se acumulam e a precisão dos números de [[ponto flutuante]] normalmente não será suficiente. |
|||
''===Dev-C++==='' |
|||
=== Abordagem iterativa === |
|||
//Autor: RenatoSantos - CEUMA - 3º período. |
|||
Com o uso de um algoritmo iterativo como o que é mostrado a seguir, é possível obter a sequência um pouco mais eficientemente: |
|||
#include <stdio.h> |
|||
#include <conio.h> |
|||
'''função''' <math>{\it fib}(n)\,</math> |
|||
int fib(int c) |
|||
:<math>i\gets 1</math> |
|||
{ |
|||
:<math>j\gets 0</math> |
|||
//1,1,2,3,5,8,13,21,... |
|||
:'''para''' <math>k\,</math> desde <math>1\,</math> até <math>n\,</math> '''faça''' |
|||
int resp; |
|||
::<math>t\gets i+j</math> |
|||
int a1,a2,t; |
|||
::<math>i\gets j</math> |
|||
a1=1; |
|||
::<math>j\gets t</math> |
|||
a2=1; |
|||
:'''retorne''' <math>j\,</math> |
|||
for(t=3;t<=c;t++) |
|||
{resp=a1+a2; |
|||
a1=a2; |
|||
a2=resp;} |
|||
return resp;} |
|||
main() |
|||
{ |
|||
int n,y; |
|||
printf("Digite um numero : "); |
|||
scanf("%d",&n); |
|||
y = fib(n); |
|||
printf("FIB = %d\n",y); |
|||
system ("pause");} |
|||
Neste caso, a complexidade computacional do algoritmo é <math>O(n)\,</math>. |
|||
=== Algoritmo em ASP === |
|||
Mostra todos os 75 primeiros resultados. |
|||
<source lang="asp"> |
|||
<% |
|||
DIM fibo |
|||
REDIM fibo(75) |
|||
=== Abordagem dividir para conquistar === |
|||
for f = 1 to 75 |
|||
if f = 1 then |
|||
fibo(f) = 0 |
|||
else |
|||
if f = 2 then |
|||
fibo(2) = 1 |
|||
else |
|||
fibo(f) = fibo(f-1) + fibo(f-2) |
|||
end if |
|||
end if |
|||
response.write f & ": " & fibo(f) & "<br />" |
|||
next |
|||
%> |
|||
</source> |
|||
O algoritmo abaixo é bem mais eficiente e baseia-se na representação matricial da sequência de Fibonacci. Sua complexidade computacional é <math>O(\log(n))\,</math>. |
|||
=== Fórmula Excel === |
|||
'''função''' <math>{\it fib}(n)\,</math> |
|||
Célula A1 =0 |
|||
:'''se''' <math>n\leq0</math> '''então''' |
|||
Célula B1 =1 |
|||
::'''retorne''' <math>0\,</math> |
|||
Célula C1 =A1+B1 |
|||
:<math>i\gets n-1</math> |
|||
Célula D1 =B1+C1 //arraste a célula para copiar a fórmula ao longo da linha |
|||
:<math>(a,b) \gets (1,0)</math> |
|||
:<math>(c,d) \gets (0,1)</math> |
|||
:'''enquanto''' <math>i > 0\,</math> '''faça''' |
|||
::'''se''' <math>i\,</math> é par '''então''' |
|||
:::<math>(a,b) \gets (db + ca, d(b + a) + cb)</math> |
|||
::<math>(c,d) \gets (c^2 + d^2, d(2c + d))</math> |
|||
::<math>i\gets i\div 2</math> |
|||
:'''retorne''' <math>a+b\,</math> |
|||
== Aplicações == |
== Aplicações == |
||
Linha 950: | Linha 269: | ||
* {{Link||2=http://www.engineering.sdstate.edu/~fib/ |3=The Fibonacci Quarterly}} — um jornal acadêmico voltado ao estudo dos números de Fibonacci |
* {{Link||2=http://www.engineering.sdstate.edu/~fib/ |3=The Fibonacci Quarterly}} — um jornal acadêmico voltado ao estudo dos números de Fibonacci |
||
* {{Link||2=http://algoritmo.110mb.com/index.php?p=artigo.php&a=Algoritmos/Numericos/fib-lgn.html |3=Algoritmo de Fibonacci em O(lg n)}} |
* {{Link||2=http://algoritmo.110mb.com/index.php?p=artigo.php&a=Algoritmos/Numericos/fib-lgn.html |3=Algoritmo de Fibonacci em O(lg n)}} |
||
* [http://rosettacode.org/wiki/Fibonacci_sequence?uselang=pt-br Implementações do algoritmo em diversas linguagens de programação no Rosetta Code] |
|||
{{DEFAULTSORT:Numero Fibonacci}} |
{{DEFAULTSORT:Numero Fibonacci}} |
Revisão das 22h43min de 21 de junho de 2011
Na matemática, os números de Fibonacci são uma sequência ou sucessão definida como recursiva pela fórmula abaixo:
O algoritmo recursivo que define a série aplica-se, na prática, conforme a regra sugere: começa-se a série com 0 e 1; a seguir, obtém-se o próximo número de Fibonacci somando-se os dois anteriores e, assim, sucessiva e infinitamente. Os primeiros números de Fibonacci (sequência A000045 na OEIS) para n = 0, 1,… são
Esta sequência foi descrita primeiramente por Leonardo de Pisa, também conhecido como Fibonacci, para descrever o crescimento de uma população de coelhos. Os números descrevem o número de casais em uma população de coelhos depois de n meses se for suposto que:
- no primeiro mês nasce apenas um casal,
- casais amadurecem sexualmente (e reproduzem-se) apenas após o segundo mês de vida,
- não há problemas genéticos no cruzamento consanguíneo,
- todos os meses, cada casal fértil dá a luz a um novo casal, e
- os coelhos nunca morrem.
Em seu livro Liber Abaci (1202), Fibonacci introduziu a sequência na matemática ocidental, embora ela já tivesse sido descrita por matemáticos indianos.
A sequência de Fibonacci tem inúmeras aplicações. É usada na análise de mercados financeiros, na ciência da computação e na teoria dos jogos. Também aparece em configurações biológicas, como, por exemplo, na disposição dos galhos das árvores ou das folhas em uma haste, [2] no arranjo do cone da alcachofra, do abacaxi,[3] ou no desenrolar da samambaia. .[4]
Mais genericamente, chama-se sequência de Fibonacci qualquer função g onde g(n + 2) = g(n) + g(n + 1). Essas funções são precisamente as de formato g(n) = aF(n) + bF(n + 1) para alguns números a e b, então as sequências de Fibonacci formam um espaço vetorial com as funções F(n) e F(n + 1) como base.
Em particular, a sequência de Fibonacci com F(1) = 1 e Ver artigo principal: Sequência de Fibonacci F(2) = 3 é conhecida como os números de Lucas. A importância dos números de Lucas L(n) reside no fato deles gerarem a Proporção áurea para as enésimas potências:
Os números de Lucas se relacionam com os de Fibonacci pela fórmula:
Com esta fórmula podemos montar a Sequência de Fibonacci e descobrir, por exemplo, quantos coelhos foram gerados no sexto mês, basta aplicar a fórmula descrita acima até chegar ao ponto inicial de 1 e 1.
Como mostra a figura abaixo;
Ou seja, no sexto mês foram gerados 8 coelhos
F(6) = (F(6) - 1) + (F(6) - 2) = 5 e 4 → 8 ( Soma do Resultado de F(5) e F(4) )
F(5) = (F(5) - 1) + (F(5) - 2) = 4 e 3 → 5 ( Soma do Resultado de F(4) e F(3) )
F(4) = (F(4) - 1) + (F(4) - 2) = 3 e 2 → 3 ( Soma do Resultado de F(3) e F(2) )
F(3) = (F(3) - 1) + (F(3) - 2) = 2 e 1 → 2
F(2) = (F(2) - 1) + (F(2) - 2) = 1 e 0 → 1
e a primeira posição 1.
Note que a Sequência de Fibonacci esta no resultado de cada posição; 1, 1, 2, 3, 5, 8, ...
Representações alternativas
Para analizar a sequência de Fibonacci (e, em geral, quaisquer sequências) é conveniente obter outras maneiras de representá-la matematicamente.
Função geradora
Uma função geradora para uma sequência qualquer é a função , ou seja, uma série potências formais em que cada coeficiente é um elemento da sequência. Os números de Fibonacci possuem a seguinte função geradora
Quando se expande esta função em potências de , os coeficientes são justamente os termos da sequência de Fibonacci:
Fórmula explícita
Conforme mencionado por Johannes Kepler, a taxa de crescimento dos números de Fibonacci, que é F(n + 1) /F(n), tende à Proporção áurea, denominada φ. Esta é a raiz positiva da equação de segundo grau x² − x − 1 = 0, então φ² = φ + 1. Se multiplicarmos ambos os lados por φn, teremos φn+2 = φn+1 + φn, então a função φn é uma sequência de Fibonacci. É possível demonstrar que a raiz negativa da mesma equação, 1 − φ, tem as mesmas propriedades, então as duas funções φn e (1 − φ)n formam outra base para o espaço.
Ajustando os coeficientes para obter os valores iniciais adequados F(0) = 0 e F(1) = 1, temos a fórmula de Binet
Este resultado também pode ser derivado utilizando-se a técnica de gerar funções, ou a técnica de resolver relações de multiplicação
Quando n tende a infinito, o segundo termo tende a zero, e os números de Fibonacci tendem à exponencial φn/√5. O segundo termo já começa pequeno o suficiente para que os números de Fibonacci possam ser obtidos usando somente o primeiro termo arredondado para o inteiro mais próximo.
Forma matricial
Para argumentos muito grandes, quando utiliza-se um computador bignum, é mais fácil[carece de fontes] calcular os números de Fibonacci usando a seguinte equação matricial:
onde a potência de n é calculada elevando-se a matriz ao quadrado repetidas vezes.
Um exemplo de aplicação desta expressão matricial é na demonstração do teorema de Lamé sobre o algoritmo de Euclides para o cálculo do MDC. Veja por exemplo o capítulo sobre o máximo divisor comum do wikilivro de Teoria de números.
Tipos de algoritmos
Há diversos algoritmos (métodos) para calcular o -ésimo elemento da sequência de Fibonacci, sendo que os mais comuns empregam um das seguintes abordagens:
- Recursiva
- Iterativa
- Dividir para conquistar
A seguir é apresentado um exemplo de cada um destes tipos de algoritmos em pseudocódigo
Abordagem recursiva
A própria definição da sequência de Fibonacci pode ser tomada como base para implementar um algoritmo recursivo que gera os termos da sequência, como é mostrado a seguir: função
- se então
- retorne
- caso contrário
- retorne
Apesar de simples, essa estratégia não é recomendável porque os mesmos valores são calculados muitas vezes (a não ser que a linguagem de programação guarde automaticamente os valores calculados nas chamadas anteriores da mesma função com o mesmo argumento). Uma análise cuidadosa mostra que a complexidade computacional do algoritmo é . Por esse motivo, normalmente calcula-se os números de Fibonacci "de baixo para cima",[carece de fontes] começando com os dois valores 0 e 1, e depois repetidamente substituindo-se o primeiro número pelo segundo, e o segundo número pela soma dos dois anteriores.
Uma outra alternativa é fazer uso da fórmula apresentada na seção anterior, que envolve potências da proporção áurea. No entanto, isso pode não ser muito conveniente para valores grandes de n, já que os erros de arredondamento se acumulam e a precisão dos números de ponto flutuante normalmente não será suficiente.
Abordagem iterativa
Com o uso de um algoritmo iterativo como o que é mostrado a seguir, é possível obter a sequência um pouco mais eficientemente:
função
- para desde até faça
- retorne
Neste caso, a complexidade computacional do algoritmo é .
Abordagem dividir para conquistar
O algoritmo abaixo é bem mais eficiente e baseia-se na representação matricial da sequência de Fibonacci. Sua complexidade computacional é .
função
- se então
- retorne
- enquanto faça
- se é par então
- se é par então
- retorne
Aplicações
Os números de Fibonacci são importantes para a análise em tempo real do algoritmo euclidiano, para determinar o máximo divisor comum de dois números inteiros.
Matiyasevich mostrou que os números de Fibonacci podem ser definidos por uma Equação diofantina, o que o levou à solução original do Décimo Problema de Hilbert.
Os números de Fibonacci aparecem na fórmula das diagonais de um triângulo de Pascal (veja coeficiente binomial).
Um uso interessante da sequência de Fibonacci é na conversão de milhas para quilômetros. Por exemplo, para saber aproximadamente a quantos quilômetros 5 milhas correspondem, pega-se o número de Fibonacci correspondendo ao número de milhas (5) e olha-se para o número seguinte (8). 5 milhas são aproximadamente 8 quilômetros. Esse método funciona porque, por coincidência, o fator de conversão entre milhas e quilômetros (1.609) é próximo de φ (1.618) (obviamente ele só é útil para aproximações bem grosseiras: além do factor de conversão ser diferente de φ, a série converge para φ).
Em música os números de Fibonacci são utilizados para a afinação, tal como nas artes visuais, determinar proporções entre elementos formais. Um exemplo é a Música para Cordas, Percussão e Celesta de Béla Bartók.
Le Corbusier usou a sequência de Fibonacci na construção do seu modulor, um sistema de proporções baseadas no corpo humano e aplicadas ao projeto de arquitetura.
Em The Wave Principal, Elliot defende a ideia que as flutuações do mercado seguem um padrão de crescimento e decrescimento que pode ser analisado segundo os números de Fibonacci, uma vez determinada a escala de observação. Defende que as relações entre picos e vales do gráfico da flutuação de bolsa tendem a seguir razões numéricas aproximadas das razões de dois números consecutivos da sequência de Fibonacci.
Teorias mais recentes, defendem que é possível encontrar relações “de ouro” entre os pontos de pico e os de vale, como no gráfico abaixo:
Se tomarmos o valor entre o início do ciclo e o primeiro pico, e o compararmos com o valor entre este pico e o pico máximo, encontraremos também o número de ouro. O ciclo, naturalmente, pode estar invertido, e os momentos de pico podem se tornar momentos de vale, e vice-versa.
Generalizações
Uma generalização da sequência de Fibonacci são as Sequências de Lucas. Um tipo pode ser definido assim:
- U(0) = 0
- U(1) = 1
- U(n+2) = PU(n+1) − QU(n)
onde a sequência normal de Fibonacci é o caso especial de P = 1 e Q = -1. Outro tipo de sequência de Lucas começa com V(0) = 2, V(1) = P. Tais sequências têm aplicações na Teoria de Números e na prova que um dado número é primo (primalidade).
Os polinômios de Fibonacci são outra generalização dos números de Fibonacci.
Identidades
- F(n + 1) = F(n) + F(n − 1)
- F(0) + F(1) + F(2) + … + F(n) = F(n + 2) − 1
- F(1) + 2 F(2) + 3 F(3) + … + n F(n) = n F(n + 2) − F(n + 3) + 2
Podemos provar essas identidades usando diferentes métodos. Mas, entretanto, nós queremos demonstrar uma elegante prova para cada um de seus usos aqui. Particularmente, F(n) podem ser interpretados como o número de formas de adicionar 1's e 2's até n − 1, convencionando-se que F(0) = 0, significando que nenhuma soma irá adicionar até -1, e que F(1) = 1, significando que a soma 0 será "adicionada" até 0. Aqui a ordem dos números importa. Por exemplo, 1 + 2 e 2 + 1 são consideradas duas diferentes somas e são contadas duas vezes.
Prova da primeira identidade
Sem perda de generalidade, podemos assumir n ≥ 1. Então F(n + 1) conta o número de formas de somar 1's e 2's até n.
Quando a primeira parcela é 1, há F(n) formas de completar a contagem para n − 1; quando a primeira parcela é 2, há F(n − 1) formas de completar a contagem para n − 2. Portanto, no total, há F(n) + F(n − 1) formas de completar a contagem para n.
ohlé?
Prova da segunda identidade
Contamos o número de formas de somar 1's e 2's até n + 1 de forma que pelo menos uma das parcelas é 2.
Como antes, há F(n + 2) formas de somar 1's e 2's até n + 1 quando n ≥ 0. Já que há apenas uma soma n + 1 que não usa nenhum 2, a saber 1 + … + 1 (n + 1 termos), subtraímos 1 de F(n + 2).
Equivalentemente, podemos considerar a primeira ocorrência de 2 como uma parcela.
Se, em uma soma, a primeira parcela é 2, então há F(n) formas de completar a contagem para n − 1. Se a segunda parcela é 2, mas a primeira é 1, então há F(n − 1) formas de completar a contagem para n − 2. Continuando este raciocínio iremos chegar à (n + 1)-ésima parcela. Se é 2, mas todas as n parcelas anteriores são 1's, então há F(0) formas de completar a contagem para 0. Se uma soma contém 2 como uma parcela, a primeira ocorrência de tal parcela deve tomar lugar entre a primeira e a (n + 1)-ésima posição. Portanto F(n) + F(n − 1) + … + F(0) dá a contagem desejada.
Prova da Terceira Identidade
Essa identidade pode ser estabelecida em duas fases. Primeiro, contamos o número de formas de somar 1's e 2's até -1, 0, …, ou n + 1 tal que pelo menos uma das parcelas seja 2.
Pela nossa primeira igualdade, há F(n + 2) − 1 formas de somar até n + 1; F(n + 1) − 1 formas de somar até n; …; e, finalmente, F(2) − 1 formas de somar até 1.
Como F(1) − 1 = F(0) = 0 , podemos adicionar todos as somas n + 1 e aplicar a segunda igualdade novamente para obter: [F(n + 2) − 1] + [F(n + 1) − 1] + … + [F(2) − 1]
- = [F(n + 2) − 1] + [F(n + 1) − 1] + … + [F(2) − 1] + [F(1) − 1] + F(0)
- = F(n + 2) + [F(n + 1) + … + F(1) + F(0)] − (n + 2)
- = F(n + 2) + F(n + 3) − (n + 2).
Por outro lado , observamos a partir da segunda igualdadee que existem
- F(0) + F(1) + … + F(n − 1) + F(n) meios somando com n + 1;
- F(0) + F(1) + … + F(n − 1) meios somando com n;
……
- F(0) meio somando com -1.
Somando todas as somas n + 1 , vemos que há
- (n + 1) F(0) + n F(1) + … + F(n) formas de somar até -1, 0, …, ou n + 1.
Já que os dois métodos de contagem se referem ao mesmo número , temos : (n + 1) F(0) + n F(1) + … + F(n) = F(n + 2) + F(n + 3) − (n + 2)
Finalmente, completamos a prova subtraindo a igualdade acima de n + 1 vezes a segunda igualdade.
Número Tribonacci
Um número Tribonacci assemelha-se a um número de Fibonacci, mas em vez de começarmos com dois termos pré-definidos, a sequência é iniciada com três termos pré-determinados, e cada termo posterior é a soma dos três termos precedentes. Os primeiros números de uma pequena sequência Tribonacci são:
1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, etc. [5]
A Espiral
Na espiral formada pela folha de uma bromélia, pode ser percebida a sequência de Fibonacci, através da composição de quadrados com arestas de medidas proporcionais aos elementos da sequência, por exemplo: 1, 1, 2, 3, 5, 8, 13… , tendentes à razão áurea. Este mesmo tipo de espiral também pode ser percebida na concha do Nautilus marinho.
Repfigits
Um repfigit ou número de Keith é um número inteiro, superior a 9, tal que os seus dígitos, ao começar uma sequência de Fibonacci, alcançam posteriormente o referido número. Um exemplo é 47, porque a sequência de Fibonacci que começa com 4 e 7 (4, 7, 11, 18, 29, 47) alcança o 47. Outro exemplo é 197: 1+9+7= 17, 9+7+17= 33, 7+17+33= 57, 17+33+57= 107, 33+57+107= 197.
Um repfigit pode ser uma sequência de Tribonacci se houver três dígitos no número, e de Tetranacci se o número tiver quatro dígitos, etc.
Alguns Números de Keith conhecidos: 14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909, 31331, 34285…
Referências
- ↑ http://www.quipus.it/english/Andean%20Calculators.pdf
- ↑ S. Douady and Y. Couder (1996). «Phyllotaxis as a Dynamical Self Organizing Process» (PDF). Journal of Theoretical Biology. 178 (178): 255–274. doi:10.1006/jtbi.1996.0026
- ↑ Jones, Judy; William Wilson (2006). «Science». An Incomplete Education. [S.l.]: Ballantine Books. p. 544. ISBN 978-0-7394-7582-9
- ↑ A. Brousseau (1969). «Fibonacci Statistics in Conifers». Fibonacci Quarterly (7): 525–532
- ↑ A000073 OEIS
Ligações externas
- «The Golden Section: Phi»
- «Computing Fibonacci numbers on a Turing Machine»
- «The Fibonacci Quarterly» — um jornal acadêmico voltado ao estudo dos números de Fibonacci
- «Algoritmo de Fibonacci em O(lg n)»
- Implementações do algoritmo em diversas linguagens de programação no Rosetta Code