Back-End

4 mar, 2019

C# – Calculando palavras Fibonacci

Publicidade

mostrei como calcular a sequência de Fibonacci usando o VB .NET. Porém, neste artigo vou mostrar uma forma de calcular e exibir as palavras Fibonacci usando C#.

Mas o que é isso?

  • Segundo a Wikipédia, uma palavra Fibonacci é uma sequência específica de dígitos binários. A palavra Fibonacci é formada por concatenação repetida da mesma forma que os números de Fibonacci são formados por adição repetida. É um exemplo paradigmático de uma palavra sturmiana e, especificamente, uma palavra mórfica.

Fonte: https://en.wikipedia.org/wiki/Fibonacci_word, acessado em outubro de 2018.

Podemos encontrar palavras de Fibonacci concatenando as palavras anteriores de Fibonacci, assim como calcular a seqüência de Fibonacci adicionando valores anteriores na sequência.

As duas primeiras palavras de Fibonacci, são:

S0 = 0
S1 = 01

Que podem ser obtidas pela fórmula: Sn = Sn-1 + Sn-2.

Como exemplo, temos a seguir uma lista que exibe as primeiras palavras de Fibonacci:

0
01
010
01001
01001010
0100101001001
010010100100101001010
0100101001001010010100100101001001
0100101001001010010100100101001001010010100100101001010

Dessa forma, a palavra Fibonacci é formada por concatenação repetida da mesma forma que os números de Fibonacci são formados por adição repetida, mas ao contrário do número de Fibonacci, a palavra Fibonacci tem seus dois primeiros termos diferentes um do outro.

Um código bem simples para retornar o n-ésimo termo da palavra Fibonacci pode ser feito da seguinte forma:

Para usar basta chamar o método informando o valor de n.

À título de exercícios, faremos o seguinte:

a) Calcular a palavra Fibonacci até n = 35
b) Exibir os primeiros valores de n
c) Para as palavras de 1 a 35 exibir o número de caracteres da palavra e a entropia da palavra

Nota: a entropia da palavra e a incerteza média está relacionada a um modelo de teoria da informação no centro da linguística quantitativa e computacional.

Criaremos um projeto do tipo Console Application usando o VS 2017 Community com o nome PalavrasFibonacci.

Os namespaces usados neste projeto, são:

using System;
using System.Collections.Generic;
using static System.Console;

No arquivo Program.cs temos o código definido da seguinte forma:

No método Main():

O método ImprimirCabecalho() que exibe no console o cabeçalho:

O método ImprimeLinha() que imprime o resultado:

O método GetEntropia() que calcula a entropia da palavra:

Pra que serve isso?

As construções baseadas em Fibonacci são usadas atualmente para modelar sistemas físicos com ordem aperiódica, como quasicristais.

Técnicas de crescimento de cristais têm sido usadas para cultivar cristais em camadas de Fibonacci e estudar suas propriedades de espalhamento de luz.

Executando o projeto iremos obter o resultado abaixo:

Pegue o projeto aqui: PalavrasFibonacci.zip.