Utilizando uma pilha, escreva uma função que receba um número inteiro positivo no formato decimal e converta este número para o formato binário. Exemplos: 5->101, 13->1101,1->1. O método retorna uma lista encadeada com os dígitos que fazem parte do número em binário

Passo 1

O que o enunciado pede e o que ele dá.
  • Pede: escrever uma função que, utilizando uma pilha, receba um número inteiro positivo em formato decimal e converta esse número para binário. O método deve retornar uma lista encadeada com os dígitos do número em binário (um nó por dígito, na ordem do mais significativo para o menos significativo).
  • Exemplos dados: 5 \to 101, 13 \to 1101, 1 \to 1.
  • Informações relevantes:
    • A entrada é um inteiro positivo (por exemplo 13, 5, 1). Pode haver o caso especial 0 — vou tratar também.
    • A pilha deve ser usada para armazenar os restos da divisão sucessiva por 2 (essa é a ideia clássica).
    • A saída é uma lista encadeada (singly linked list) contendo os dígitos binários em ordem do mais significativo para o menos significativo (por exemplo para 13 deve-se retornar uma lista 1 \to 1 \to 0 \to 1).

Passo 2

Entendendo a ideia principal (sem ainda programar): por que usar pilha?
  • Quando convertemos um número decimal para binário pelo método de divisões sucessivas por 2, fazemos repetidamente:
    • calcular o resto r = n \bmod 2;
    • dividir n por 2 (inteiro) para obter o próximo n.
  • Esses restos aparecem do menos significativo para o mais significativo. Exemplo com 13:
    • 13 \bmod 2 = 1 (resto 1) → menos significativo.
    • 6 \bmod 2 = 0 (resto 0).
    • 3 \bmod 2 = 1 (resto 1).
    • 1 \bmod 2 = 1 (resto 1) → mais significativo.
  • Os restos, nessa ordem, formam 1,0,1,1. Mas a representação binária correta é o inverso: 1,1,0,1.
  • A pilha (LIFO) é perfeita: empilha os restos à medida que são gerados, depois desempilha para obter a sequência do mais significativo ao menos significativo.

Passo 3

Estrutura da lista encadeada que vamos retornar e operações básicas da pilha — conceito e implementação simples.
  • Lista encadeada (singly):
    • Cada nó tem um campo \text{valor} (que será 0 ou 1) e um campo \text{prox} (ponteiro para o próximo nó).
    • A função retornará o ponteiro para o primeiro nó (cabeça) da lista, ou None se preferirmos indicar lista vazia (mas aqui vamos garantir que haja pelo menos um nó, mesmo para n=0).
  • Pilha:
    • Operações essenciais: \text{push}(x) insere elemento no topo; \text{pop}() remove e retorna o elemento do topo; \text{isEmpty}() verifica se está vazia.
    • Em muitas linguagens, uma lista/array dinâmico funciona como pilha: \text{append} = \text{push} e \text{pop} = \text{pop} sem índice.

Passo 4

Algoritmo passo a passo (alto nível) — versão textual antes do código.
  1. Se n = 0, criar um nó com valor 0 e retornar essa lista (caso especial).
  2. Criar uma pilha vazia.
  3. Enquanto n > 0:
    • Calcular r = n \bmod 2.
    • \text{push}(r) na pilha.
    • Atualizar n \leftarrow \lfloor n / 2 \rfloor (divisão inteira).
  4. Agora a pilha contém os dígitos binários do menos significativo (embaixo) ao mais significativo (topo). Para obter a lista encadeada na ordem correta:
    • Inicializar ponteiro \text{head} \leftarrow None e \text{tail} \leftarrow None.
    • Enquanto a pilha não estiver vazia:
      • d \leftarrow \text{pop}().
      • Criar um novo nó com \text{valor} = d e \text{prox} = None.
      • Se \text{head} for None: \text{head} \leftarrow novo nó e \text{tail} \leftarrow novo nó.
      • Caso contrário: \text{tail.prox} \leftarrow novo nó; \text{tail} \leftarrow novo nó.
  5. Retornar \text{head} (ponteiro para a lista encadeada com os dígitos binários na ordem correta).

Passo 5

Vou explicar cada parte do algoritmo com detalhes que você pode reproduzir na prova, incluindo por que cada passo é necessário.
  • Por que checar n = 0? Porque o laço "enquanto n>0" nunca executaria e a pilha ficaria vazia; a convenção prática é representar 0 como binário 0 com um único nó contendo 0.
  • No laço de divisão:
    • O resto r = n \bmod 2 é um dígito binário (ou 0 ou 1).
    • Empilhamos r porque o primeiro resto é o bit menos significativo; precisamos inverter a ordem depois.
    • Atualizar n \leftarrow \lfloor n/2 \rfloor aproxima-nos do próximo bit.
  • Na fase de desempilha:
    • Cada \text{pop} retorna o próximo bit do mais significativo para o menos significativo, exatamente a ordem desejada para a lista de saída.
    • Mantemos \text{tail} para anexar em tempo constante cada novo nó (se não, teríamos que percorrer a lista até o final a cada anexação).
  • Complexidade:
    • Tempo: O(\log_2 n) operações, pois o número de bits em n é aproximadamente \lfloor \log_2 n \rfloor + 1.
    • Espaço extra: O(\log_2 n) para a pilha e O(\log_2 n) para a lista de saída (os nós).

Passo 6

Implementação (pseudocódigo e explicação linha a linha). Vou mostrar uma implementação em estilo Python (clara e fácil de traduzir para outras linguagens). Comentários explicam cada linha.
def Node:
# Nó de lista encadeada com campos ‘valor’ e ‘prox’
def init(self, valor):
self.valor = valor # aqui ‘valor’ será 0 ou 1
self.prox = None
def decimal_to_binary_linked_list(n):
# Recebe um inteiro positivo n e retorna a lista encadeada com os dígitos binários
if n == 0:
return Node(0) # caso especial: 0 -> lista com único nó 0
pilha = []                   # usamos uma lista como pilha: append = push, pop = pop
# fase 1: empilhar restos
while n > 0:
    resto = n % 2            # resto é 0 ou 1
    pilha.append(resto)     # empilha o resto
    n = n // 2              # divisão inteira, atualiza n

# fase 2: desempilhar e construir lista encadeada na ordem correta
head = None
tail = None
while pilha:
    digito = pilha.pop()    # desempilha: obtém próximo bit mais significativo
    novo_no = Node(digito)
    if head is None:
        head = novo_no
        tail = novo_no
    else:
        tail.prox = novo_no
        tail = novo_no

return head
  • Explicação das partes do código:
    • A função \text{Node} define um nó simples com campos \text{valor} e \text{prox}.
    • Em \text{decimal\_to\_binary\_linked\_list}, o teste inicial trata n=0.
    • \text{pilha} é iniciada vazia; no laço \text{while } n>0 calculamos \text{resto}=n\bmod 2 e empilhamos.
    • Após terminar, desempilhamos com \text{pop}() e criamos nós na ordem correta; \text{tail} permite anexar em O(1).
    • Por fim retornamos \text{head}.

Passo 7

Exemplos práticos passo a passo (para você ver como o empilhamento e desempilhamento funcionam na prática).
Exemplo n = 13:
  • Inicial: n = 13, pilha = [].
  • Iteração 1: 13 \bmod 2 = 1 → pilha = [1]; n \leftarrow 6.
  • Iteração 2: 6 \bmod 2 = 0 → pilha = [1,0]; n \leftarrow 3.
  • Iteração 3: 3 \bmod 2 = 1 → pilha = [1,0,1]; n \leftarrow 1.
  • Iteração 4: 1 \bmod 2 = 1 → pilha = [1,0,1,1]; n \leftarrow 0. Laço termina.
  • Desempilhar e criar lista:
    • pop() → 1 → lista: 1
    • pop() → 1 → lista: 1 \to 1
    • pop() → 0 → lista: 1 \to 1 \to 0
    • pop() → 1 → lista: 1 \to 1 \to 0 \to 1
  • Resultado: representa 1101, que é binário de 13.
Exemplo n = 5:
  • Resto sequencial: 1,0,1 (empilhados nessa ordem) → desempilhando gera 1 \to 0 \to 1 que é 101.
Exemplo n = 1:
  • Resto único 1 → lista apenas 1.
Exemplo n = 0 (caso tratado):
  • Retorna lista com nó 0.

Passo 8

Dicas para a prova (o que escrever e o que justificar rapidamente):
  • Explique a ideia: “usar divisões por 2 para obter restos e empilhar os restos; depois desempilhar para obter a ordem correta”.
  • Mostre corretamente um exemplo curto, por exemplo 13, com os restos empilhados e o resultado final.
  • Indique complexidades O(\log_2 n) tempo e espaço.
  • Implementação pode ser em pseudocódigo ou em uma linguagem concreta; em qualquer caso, deixe claro o papel da pilha e da lista encadeada.

Resposta

def Node:
def init(self, valor):
self.valor = valor
self.prox = None
def decimal_to_binary_linked_list(n):
if n == 0:
return Node(0)
pilha = []
while n > 0:
    resto = n % 2
    pilha.append(resto)
    n = n // 2

head = None
tail = None
while pilha:
    digito = pilha.pop()
    novo_no = Node(digito)
    if head is None:
        head = novo_no
        tail = novo_no
    else:
        tail.prox = novo_no
        tail = novo_no

return head

Exercícios relacionados