Conversor de bases genérico

URL

https://www.thehuxley.com/problem/416

Descrição

Esse problema é bastante interessante para explorar a principal característica de uma pilha: First In Last Out.

O problema pede para recebermos um número inteiro na base decimal e convertê-lo para qualquer base menor ou igual a 16.

Vamos abordar esse problema com um exemplo de conversão da base 10 para a base 2.

Suponha o número 4 na base 10. A forma como aprendemos a transformar para a base 2 foi através de uma série de divisões sucessivas:

Nesse caso, dividimos 4 por 2 até encontrarmos o quociente igual a 0. Quando isso acontecer, o número em binário é a concatenação dos restos de cima pra baixo, conforme ilustrado na figura acima.

É importante entender a intuição por trás dessa raciocínio. No nosso sistema decimal, só temos 10 símbolos. Mas ainda assim, a gente consegue representar quantidades muito maiores que 10. Como fazemos isso? a gente concatena os símbolos que dispomos.

Suponha que você está contando feijão. Mas você só tem os dez símbolos: 0 1 2 3 4 5 6 7 8 9.

Então, você começa a contar:

1, 2, 3, 4, 5, 6, 7, 8, 9 .... opa ... acabaram os símbolos! E agora?

O que nós fazemos é concatenar os símbolos que tempos. Nesse caso a gente coloca o 1 na frente e repete os símbolos iniciais:

1 0

1 1

1 2

1 3

... e assim por diante.

Ou seja, usamos a concatenação para representar quantidades maiores que a quantidade de símbolos.

Quando a gente converte de decimal para binário, no fundo fazemos a mesma coisa. No sistema binário só temos dois símbolos: 0 1

Então você começa a contar:

0

1

... opa ... acabaram ... então vamos concatenar:

1 0

1 1

. .. e agora? acabou de novo ... não tem problema, vamos adicionar mais um símbolo e concatenar

1 0 0

.. e vamos repetir as concatenações que já fizemos

1 0 1

1 1 0

1 1 1

... acabou de novo? adicione mais um símbolo ... e assim por diante.

1 0 0 0

1 0 0 1

....

Essa divisão sucessiva serve exatamente para isso. Você vai mapeando para os símbolos da sua base e depois concatena.

Agora voltando para o nosso algoritmo de transformar de decimal para binário onde usávamos divisões sucessivas, a ideia dele é exatamente essa das concatenações de símbolos.

Quando realizamos a primeira divisão, o que estamos fazendo é: "ok, eu tenho um número mas preciso transformá-lo para outro número em um sistema de numeração que se tem dois símbolos. Ora, como são 2 símbolos e os símbolos são 0 e 1, se eu dividir esse número por 2 eu obtenho como resto 0 ou 1 e como quociente eu obtenho outro número para continuar dividindo. Só que agora esse novo número é menor que o primeiro. Logo, se eu fizer isso até não conseguir dividir mais, eu decompus o número inicial".

Essa mesma lógica a gente usa no dia a dia com os relógios de ponteiro. Quer ver? suponha que você queira representar 23 horas no relógio de ponteiro, que número você usaria?

11, correto?

Já reparou que 11 é exatamente igual ao resto de 23 por 12. Só que dessa vez, você transformou a hora que era 23 para a base 12, ao invés da base 2.

Para transformar de decimal para qualquer base, basta você usar esse mesmo algoritmo, e realizar divisões sucessivas pela base destino.

Agora você pode estar se perguntando: e a pilha?

Você já reparou que umas das principais aplicações da pilha é que ela permite que a gente vá guardando os resultados para imprimí-los da ordem inversa?

Por exemplo, se você realizar as seguintes operações em uma pilha:

push(1)

push(2)

push(3)

push(4)

cout << pop()

cout << pop()

cout << pop()

cout << pop()

a sua saída esperada será 4 3 2 1, justamente a ordem inversa da inserção. Primeiro a entrar, último a sair.

Percebeu agora como isso se relaciona com o nosso problema?

No nosso problema, os primeiros restos encontrados são justamente os últimos na composição do número resultante. Logo, parece que uma pilha para armazenar os restos é uma solução adequada.

Para testar o seu programa, você pode utilizar essa calculadora para conversão de bases: http://www.calculadoraonline.com.br/conversao-bases