Anteriormente, apresentamos uma definição recursiva para o conjunto dos números naturais,
. Outra maneira de representar o conjunto
é utilizando sequências finitas (listas) de bits. Tal representação consiste na conversão de números de base 10 para base 2 e vice-versa.
Apresente uma função recursiva que, a partir de uma lista de valores booleanos
List
, retorne o número natural
correspondente ao número binário
na base 10 .
Apresente uma função recursiva que, a partir de uma lista de valores booleanos
Passo 1
Beleza, vamos lá! A questão pede para a gente criar uma função recursiva que pega uma lista de valores booleanos (que representam bits, ou seja, 0s e 1s) e converte essa lista em um número natural na base 10. A matéria envolvida aqui é a conversão de números de base 2 (binário) para base 10 (decimal). Para resolver isso, vamos precisar entender como os números binários funcionam e como aplicamos uma abordagem recursiva para fazer a conversão.
Passo 2
Primeiro, vamos lembrar como funciona a representação binária. Cada posição em um número binário representa uma potência de 2, começando da direita para a esquerda com 2⁰, 2¹, 2², e assim por diante. Por exemplo, o número binário 101 representa:
Então, para converter uma lista de bits em um número decimal, precisamos somar cada bit multiplicado pela potência de 2 correspondente à sua posição.
Passo 3
Agora, vamos pensar recursivamente. Uma função recursiva resolve um problema chamando a si mesma com um pedaço menor do problema até chegar a um caso base. No nosso caso, podemos quebrar a lista de bits em duas partes: o primeiro bit e o restante da lista. O valor do primeiro bit multiplicado por $ 2^{n-1} $ (onde $ n $ é o tamanho da lista) somado à conversão recursiva do resto da lista nos dará o número decimal correspondente.
Passo 4
Vamos definir nossa função passo a passo:
- Caso Base: Se a lista estiver vazia, significa que não há mais bits para processar, então o número é 0.
- Passo Recursivo: Se a lista não estiver vazia, pegamos o primeiro bit, calculamos seu valor em decimal multiplicando-o por $ 2^{n-1} $, onde $ n $ é o tamanho da lista. Em seguida, chamamos a função recursivamente para o restante da lista e somamos os resultados.
Passo 5
Para implementar isso, precisamos de uma função que:
- Receba uma lista de bits.
- Calcule o tamanho da lista para determinar a potência de 2 correta.
- Multiplique o primeiro bit pela potência de 2.
- Some com a chamada recursiva da função para o restante da lista.
Em termos matemáticos, a função $ f $ pode ser definida como:
Onde:
- $ b $ é o primeiro bit da lista.
- $ l’ $ é a lista sem o primeiro bit.
- $ n $ é o tamanho da lista original.
Passo 6
Vamos exemplificar com uma lista de bits. Suponha que temos a lista
:
- $ n = 3 $, primeiro bit $ b = 1 $, potência $ 2^{2} = 4 $
- $ 1 \times 4 = 4 $
- Chama a função com
: - $ n = 2 $, primeiro bit $ b = 0 $, potência $ 2^{1} = 2 $
- $ 0 \times 2 = 0 $
- Chama a função com
: - $ n = 1 $, primeiro bit $ b = 1 $, potência $ 2^{0} = 1 $
- $ 1 \times 1 = 1 $
- Chama a função com lista vazia, retorna 0
- Soma: $ 1 + 0 = 1 $
- Soma total: $ 0 + 1 = 1 $
- Soma final: $ 4 + 1 = 5 $
Então,
em binário é igual a 5 em decimal.
Resposta
A função recursiva para converter uma lista de bits em um número natural na base 10 é:
Onde:
- $ b $ é o primeiro bit da lista $ l $.
- $ n $ é o tamanho da lista $ l $.
- $ l’ $ é a lista sem o primeiro bit.
Essa função percorre cada bit da lista, calcula seu valor decimal com base na posição e soma tudo recursivamente, retornando assim o número natural correspondente na base 10.