Nos problemas de contagem, o conhecimento dos termos e do comportamento de determinadas sequências numéricas é fundamental na identificação de padrões e propriedades dos elementos a serem contados. Abaixo são listadas algumas destas sequências.
A sequência de Fibonacci F(n) é definida pela recorrência abaixo:
F(0) = F(1) = 1
F(n) = F(n - 1) + F(n - 2), n >= 2
Os primeiros termos da sequência de Fibonacci são:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, ...
Como podemos observar, os valores da sequência crescem rapidamente, de modo que o número de termos que podem ser computados em tipos inteiros de C/C++ é bastante restrito: para variáveis de 32-bits, podemos calcular o valor exato de F(n) para n ≥ 46 (F(46) = 1836311903); para variáveis de 64-bits, temos n ≥ 92 (F(92) = 7540113804746346429. Para valores de n superiores a 92, é necessário ou trabalhar com aritmética estendida ou com aritmética modular.
Nesta seção trataremos do problema de se determinar o n-ésimo termo da sequência de Fibonacci. Uma abordagem inicial seria o uso de recursão:
long long recursive_fibonacci(long long n)
{
if (n == 0 or n == 1)
return n;
return recursive_fibonacci(n - 1) + recursive_fibonacci(n - 2);
}A implementação acima tem como vantagem a simplicidade, uma vez que mapeia diretamente a definição da sequência no código, mas tem complexidade assintótica de O(2^n). Em compiladores mais antigos tal código teria dificuldades de computar o valor de F(16), porém os compiladores modernos conseguem otimizar tais recursão (tail recursion optimization), o que permite usar tal implementação em casos menores. A título de curiosidade, em um teste realizado em um notebook com processador i7 e 8 GB de RAM, F(46) foi computado em 6,6 segundos.
Para melhorar o tempo de execução e reduzir a complexidade assintótica, podemos fazer uma implementação iterativa. Abaixo um exemplo de tal implementação em Python:
def iterative_fibonacci(n):
if n < 2:
return n
a = 0
b = 1
for x in xrange(n):
a, b = b, a + b
return aEsta nova versão tem complexidade assintótica igual a O(n). Um teste na mesma máquina permitiu o cálculo de F(46) em apenas 0,012s. Outra vantagem desta implementação é o fato da linguagem Python trabalhar nativamente com aritmética estendida.
Outra melhoria possível no código anterior é armazenar, em memória, os termos já computados, e retornar diretamente caso o valor já seja conhecido, e computar apenas os valores necessários para a resposta.
fib = [0, 1]
def fibonacci(n):
if n < len(fib):
return fib[n]
next = len(fib)
while next <= n:
fib.append(fib[next - 1] + fib[next - 2])
next += 1
return fib[n]É possível reduzir ainda mais a complexidade assintótica do problema, modelando o problema como uma equação de diferenças lineares. Considere u(n) um vetor cujas duas componentes são os números de Fibonacci F(n + 1) e F(n). Temos então a seguinte equação de diferenças:
u(n + 1) = Au(n)
onde
A = | 1 1 |
| 1 0 |
Podemos observar que u(1) = Au(0), u(2) = Au(1) = A²u(0), etc, e assim por diante, que nos leva a u(n) = A^nu(0)
e que o termo F(n) seria igual ao termo c (segunda linha, primeira coluna) da matriz.
Usando exponenciação rápida para computar a potência _n_ésima, temos um algoritmo com ordem de complexidade O(log n) para determinar o n-ésimo termo da sequência de Fibonacci.
#include <iostream>
using namespace std;
class Matrix {
long long _a, _b, _c, _d;
public:
Matrix(long long a = 1, long long b = 0, long long c = 0, long long d = 1)
: _a(a), _b(b), _c(c), _d(d) {}
Matrix operator*(const Matrix& m) const
{
auto a = _a * m._a + _b * m._c;
auto b = _a * m._b + _b * m._d;
auto c = _c * m._a + _d * m._c;
auto d = _c * m._b + _d * m._d;
return Matrix(a, b, c, d);
}
long long b() const { return _b; }
};
long long fast_fibonacci(long long n)
{
Matrix res, A(1, 1, 1, 0);
while (n)
{
if (n & 1)
res = res * A;
A = A * A;
n >>= 1;
}
return res.b();
}A sequência de Fibonacci tem várias propriedades interessantes:
- a razão entre dois termos consecutivos da série tende à razão áurea (1 + √5)/2;
- a soma dos n primeiros termos da sequência é igual a F(n + 2) - 1 (soma telescópica);
- a soma dos quadrados dos n primeiros termos da sequência é igual a F(n)F(n+1) (indução);
- para um m > 1 fixo, a sequência dos restos r(n) = F(n) % m é cíclica. O tamanho destes período é denominado Período de Pisano 𝜋(m). Alguns valores comuns:
- 𝜋(2) = 3
- 𝜋(10) = 60
- 𝜋(100) = 300
- 𝜋(10^k) = 15 * 10^{k - 1}, k ≥ 3
- Exceto para o caso m = 2, o período de Pisano é sempre par.
Os números de Catalan C(n) formam uma sequência de inteiros que contabilizam uma série de fatos notáveis. Os primeiros números de Catalan são 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ...
A primeira aplicação notável dos números de Catalan C(n) é a contagem do número de sequências corretas formadas por 2n pares de parêntesis. Para n = 0 temos uma única sequência (vazio), e o mesmo ocorre para n = 1. Para n = 2 temos C(2) = 2 duas sequências possíveis
()(), (())
Para n = 3 temos C(3) = 5 sequências:
()()(), (())(), ()(()), ((())), (()())
A segunda aplicação notável é a contagem de árvores binárias completas (isto é, cada nó tem ou dois filhos ou nenhum): há C(n) árvores binárias completas com n + 1 folhas. Para n = 3 temos C(2) = 2 árvores:
o
/ \
o x
/ \
x x
e
o
/ \
x o
/ \
x x
Uma terceira aplicação seria a contagem de triangularizações de um polígono convexo de n+2 lados: há C(n) triangularizações possíveis.
Além dessas, há mais de 60 outras aplicações possíveis para tais números.
Os números de Catalan surgem da recorrência
C(0) = 1
C(n + 1) = S{i=0,...,n} C(i)C(n - i), n >= 0
onde S{i=0,...,n} é o somatório de i variando de zero a n. Esta soma tem uma fórmula fechada:
C(n) = binom(2n, n)/(n + 1)
Outra recorrência decorre desta forma fechada:
C(0) = 1
C(n + 1) = [2(2n +1)C(n)]/(n + 2)
Esta última recorrência permite uma implementação eficaz dos números de Catalan, conforme apresentado no código abaixo:
long long C[MAX]; // MAX deve estar definido e todos os elementos de C deve ser inicializado
// com o valor -1
long long catalan(int n)
{
if (n == 0)
return 1;
if (C[n] != -1)
return C[n];
C[n] = (2*(2*n - 1)*catalan(n - 1))/(n + 1);
return C[n];
}Com variáveis do tipo long long é possível computar até o 33º número de Catalan sem
overflow.
- UVA
HALIM, Steve; HALIM, Felix. Competitive Programming 3, Lulu, 2013.
WOLFRAM Math World. Pisano Period. Acesso em 28/09/2017.
WIKIPEDIA. Catalan Numbers. Acesso em 05/10/2017.
WIKIPEDIA. Pisano Period. Acesso em 28/09/2017.
WIKIPEDIA. Sequência de Fibonacci. Acesso em 28/09/2017.