Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como converter uma string composta por 1's e 0's no seu número equivalente (Binário->Decimal) recursivamente?

0 votos
51 visitas
perguntada Set 25 em Programação Computacional por bonfim_tiago (6 pontos)  
editado Set 25 por bonfim_tiago

Exercício 4.8 do Livro ”Introduction to Recursive Programming“ de Manuel Rubio-Sánchez, Capítulo 4 , página 130.

Compartilhe

1 Resposta

+1 voto
respondida Set 25 por bonfim_tiago (6 pontos)  
editado Set 25 por bonfim_tiago

Oi, pessoal, tudo bem com vocês?

O presente problema consiste em, a partir de uma string composta por 1's e 0's, apresentar o seu número equivalente, utilizando-se para tal, o sistema de representação binário.

Conforme todos devem saber, um sistema de representação decimal emprega de forma implícita potências de sua base, dez, que devem ser sucessivamente somadas de forma a se obter o número resultante que estamos representando. A título de exemplificação, podemos dizer que o número 531 consiste, na verdade, no seguinte número:
5 * 10^2 + 3 *10^1 + 1 *10^0

Esse sistema decimal, claramente, admite números que oscilam entre as possibilidades compreendidas no intervalo [0, 9] (dez possibilidades), tendo em vista que, caso admitíssemos o número dez, dever-se-ia, simplesmente, elevar em uma unidade a potência de dez subsequente do número.

De forma inteiramente análoga, funciona o sistema representativo binário que, como o próprio nome indica, emprega uma base dois como sua fundamentação. Com efeito, são admitidos números compreendidos no intervalo [0,1] nessa representação. Por exemplo, o número binário 10110 seria, na verdade:
1 *2^4 + 0 *2^3 + 1 *2^2 + 1 *2^1 + 0 *2^0 = 16 + 4 + 2 = 22 (em uma base decimal de representação).

Feita essa breve contextualização, nosso exercício consiste na conversão, de forma recursiva, de uma string constituída por 1's e 0's no seu número equivalente em uma base de representação decimal. Aliás, de forma exatamente igual ao que foi feito com a string "10110" acima, e que resultou no número 22.

O código elaborado para solucionar essa questão segue apresentado abaixo:

# @ Autor: Tiago da Silva Bonfim
# Data: 25/09/2021
#
# Aula 04 - Livro Introduction to recursive programming
# Exercise 4.8 — Define and code a function that, given a decimal number
# n whose digits are either zero or one, returns the number whose binary
# representation is precisely the sequence of zeros and ones in n. For
# example, if n = 1011010 the function returns 22, since 101102 = 22.

def binary_to_decimal_recursive_conversion(input_word:str, decimal_sum:int, letter_pointer:int):
    # função recursiva que converte uma string binária em seu respectivo decimal
    # Parâmetros de entrada:
    #   input_word (str): string de entrada contendo a sequência de 1's e 0's
    #   decimal_sum (int): variável inteira que armazena o resultado da soma a cada etapa da iteração
    #   letter_pointer (int): ponteiro que aponta para cada elemento da string a ser iterativamente processada 

    # move o ponteiro para o próximo elemento do vetor
    try:
        letter_pointer += 1
    except:
        print("Execução finalizada com erro devido a erro nos parâmetros de entrada")
        return -1        

    # verifica a condição de parada: o ponteiro se encontra, atualmente, direcionado para um elemento inexistente da string. Logo, todos os elementos já foram processados
    try:
        if letter_pointer == len(input_word) + 1:
            print("A sequência binária apresentada corresponde ao número decimal:",decimal_sum)
            # decimal_sum contém, nesse ponto, o valor total da soma dos bits
            return decimal_sum
    except TypeError: 
        print("Execução finalizada com erro devido a erro nos parâmetros de entrada")
        return -1

    # print auxiliar que escreve, a cada iteração, para qual elemento estamos tratando, sua posição no vetor e seu respectivo valor decimal 
    try:
        print("Letra:", input_word[len(input_word) - letter_pointer], 
            "Posição da Letra:", len(input_word) - letter_pointer,
            "Valor da posição:", 2**(letter_pointer - 1))    
    except TypeError: 
        print("Execução finalizada com erro devido a erro nos parâmetros de entrada")
        return -1

    # adiciona em decimal_sum o valor do elemento processado nessa iteração
    try:
        decimal_sum += int(input_word[len(input_word) - letter_pointer])*(2**(letter_pointer - 1))
    except TypeError:
        print("Execução finalizada com erro devido a erro nos parâmetros de entrada")
        return -1

    # chama novamente a função com os parâmetros atualizados (recursão)
    binary_to_decimal_recursive_conversion(input_word, decimal_sum, letter_pointer)

# chama a função recursiva com os parâmetros iniciais 
binary_to_decimal_recursive_conversion("10110", 0, 0)

Em que o resultado da compilação desse código apresenta como saída:

Letra: 0 Posição da Letra: 4 Valor da posição: 1
Letra: 1 Posição da Letra: 3 Valor da posição: 2
Letra: 1 Posição da Letra: 2 Valor da posição: 4
Letra: 0 Posição da Letra: 1 Valor da posição: 8
Letra: 1 Posição da Letra: 0 Valor da posição: 16
A sequência binária apresentada corresponde ao número decimal: 22

Bom, acredito que o único comentário não-trivial relacionado ao código que deve ser realizado diz respeito a necessidade do uso dos blocos try-except no código. Isso foi feito porque existe a possibilidade de termos um erro de tipo de variável se o usuário, por exemplo, não inserir a string de 1's e 0's corretamente.

Como deve ser de conhecimento da maioria, o Python é uma linguagem de tipagem fraca, de forma que esse tipo de coisa pode acontecer. Ao mesmo tempo, não se sabe se usuários totalmente leigos iriam executar esse código, penso que a intenção do exercício não seria essa. Como o código final acaba por ficar um pouquinho poluído, imagino que não faça sentido seguir com esse tipo de testagem em exercícios futuros; no entanto, fica aí a reflexão.

Até a próxima e aguardo pelos comentários!
Abs.,

comentou 4 dias atrás por Caio Oliveira Dantas (16 pontos)  
O uso dos blocos try-except foi muito bom por chamar atenção para um problema que faz parte do dia-a-dia dos programadores sobre o qual não costumamos refletir.  

Caso a questão não solicitasse explicitamente a implementação de uma função, mas apenas a conversão, poderia ser usada a função int() da seguinte forma:

 int(10110, 2)

A função int() converte de qualquer base para a decimal, bastando trocar o 2 pela base em questão.
...