Anteriormente, apresentamos uma definição recursiva para o conjunto dos números naturais, N. Outra maneira de representar o conjunto N é 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 l in List B, retorne o número natural n in N correspondente ao número binário l na base 10 .

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:
1 times 2^2 + 0 times 2^1 + 1 times 2^0 = 4 + 0 + 1 = 5
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:
  1. Caso Base: Se a lista estiver vazia, significa que não há mais bits para processar, então o número é 0.
  2. 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:
f éá
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 [1, 0, 1]:
  1. $ n = 3 $, primeiro bit $ b = 1 $, potência $ 2^{2} = 4 $
  2. $ 1 \times 4 = 4 $
  3. Chama a função com n = 3 :
    • $ n = 2 $, primeiro bit $ b = 0 $, potência $ 2^{1} = 2 $
    • $ 0 \times 2 = 0 $
    • Chama a função com b = 1 :
      • $ 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 $
  4. Soma total: $ 0 + 1 = 1 $
  5. Soma final: $ 4 + 1 = 5 $
Então, 2^2 = 4 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 é:
f(l) = 0 & se l é vazia b times 2^n-1 + f(l') & caso contrário éá
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.

Exercícios relacionados