4.5. Convertendo um Inteiro para String em Qualquer Base¶

Suponha que você queira converter um inteiro para uma string em alguma base entre binário e hexadecimal. Por exemplo, converta o inteiro 10 em uma string contendo sua representação em decimal como "10", ou para sua representação em binário como "1010". Embora existam muitos algoritmos para resolver este problema, incluindo o algoritmo discutido na seção sobre pilha, a formulação recursiva do problema é muito elegante.

Vejamos um exemplo concreto usando a base 10 e o número 769. Suponha que tenhamos uma sequência de caracteres correspondente aos 10 primeiros dígitos, como tabelaConv = "0123456789". É fácil converter um número menor que 10 em uma string equivalente apenas olhando a tabela. Por exemplo, se o número for 9, a string será tabelaConv[9] ou "9". Se conseguirmos uma forma de quebrar o número 769 em seus três dígitos, 7, 6 e 9, a conversão para uma string é simples. Um número menor que 10 parece um bom caso base.

Saber qual é o nosso caso base sugere que o algoritmo geral envolve três componentes:

1. Reduza o número original para uma série de números de um dígito.

2. Converta o dígito em uma string usando a tabelaConv.

3. Concatene as strings dos dígitos para formar o resultado final.

O próximo passo é descobrir como mudar o estado e progredir em direção ao caso base. Como estamos trabalhando com um inteiro, vamos considerar quais operações matemáticas podem reduzir um número. Os candidatos mais prováveis ​​são divisão e subtração. Embora a subtração possa servir, não é claro o que devemos subtrair do que. A divisão inteira com resto nos dá uma direção clara. Vamos ver o que acontece se dividirmos um número pela base que estamos tentando converter.

Usando divisão inteira para dividir 769 por 10, obtemos 76 com um resto de 9. Isso nos dá dois bons resultados. Primeiro, o resto é um número menor que a nossa base que pode ser convertida em uma string imediatamente usando a tabela. Em segundo lugar, obtemos um número menor que o nosso original, o que nos move em direção ao caso base de ter um único número menor que a nossa base. Agora nosso trabalho é converter 76 em uma string. Novamente vamos usar a divisão inteira mais o resto para obter os resultados 7 e 6 respectivamente. Finalmente, reduzimos o problema para converter 7, o que podemos fazer facilmente, uma vez que satisfaz a condição do caso base \(n < base\), onde \(base = 10\). A série de operações que acabamos de realizar é ilustrada na Figura 3. Note que os números que queremos lembrar estão nas caixas com os restos ao lado direito do diagrama.

Figura 3: Convertendo um Inteiro em uma String na Base 10¶

ActiveCode 1 mostra o código Python que implementa o algoritmo descrito acima para qualquer base entre 2 e 16.

Note que na linha 3 verificamos o caso base onde n deve ser menor que a base para a qual estamos convertendo. Quando detectamos o caso base, terminamos a recursão e simplesmente retornamos a string na posição correspondente de convertString. Na linha 6, satisfazemos tanto a segunda quanto a terceira leis fazendo a chamada recursiva e reduzindo o tamanho do problema usando a divisão.

Vamos simular o algoritmo novamente; desta vez vamos converter o número 10 para uma representação string na base 2 ("1010").

Figura 4: Convertendo o Número 10 Para uma Representação String na Base 2¶

A Figura 4 mostra que obtemos o resultado esperado, mas parece que os dígitos estão na ordem errada. O algoritmo funciona corretamente porque fazemos a primeira chamada recursiva na linha 6 e então adicionamos a representação string do resto. Se invertéssemos a ordem da concatenação na linha 6, a string resultante seria invertida! Mas atrasando a concatenação até que a chamada recursiva tenha retornado, obtemos o resultado na ordem correta. Isso deve lembrá-lo da nossa discussão sobre pilhas no capítulo anterior.