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