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:
,
. 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:
, , . - Informações relevantes:
- A entrada é um inteiro positivo (por exemplo
, , ). Pode haver o caso especial — vou tratar também. - A pilha deve ser usada para armazenar os restos da divisão sucessiva por
(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
deve-se retornar uma lista ).
- A entrada é um inteiro positivo (por exemplo
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
, fazemos repetidamente: - calcular o resto
; - dividir
por (inteiro) para obter o próximo .
- calcular o resto
- Esses restos aparecem do menos significativo para o mais significativo. Exemplo com
: -
(resto ) → menos significativo. -
(resto ). -
(resto ). -
(resto ) → mais significativo.
-
- Os restos, nessa ordem, formam
. Mas a representação binária correta é o inverso: . - 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
(que será ou ) e um campo (ponteiro para o próximo nó). - A função retornará o ponteiro para o primeiro nó (cabeça) da lista, ou
se preferirmos indicar lista vazia (mas aqui vamos garantir que haja pelo menos um nó, mesmo para ).
- Cada nó tem um campo
- Pilha:
- Operações essenciais:
insere elemento no topo; remove e retorna o elemento do topo; verifica se está vazia. - Em muitas linguagens, uma lista/array dinâmico funciona como pilha:
= e = sem índice.
- Operações essenciais:
Passo 4
Algoritmo passo a passo (alto nível) — versão textual antes do código.
- Se
, criar um nó com valor e retornar essa lista (caso especial). - Criar uma pilha vazia.
- Enquanto
: - Calcular
. -
na pilha. - Atualizar
(divisão inteira).
- Calcular
- 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
e . - Enquanto a pilha não estiver vazia:
-
. - Criar um novo nó com
e . - Se
for : novo nó e novo nó. - Caso contrário:
novo nó; novo nó.
-
- Inicializar ponteiro
- Retornar
(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
? Porque o laço "enquanto " nunca executaria e a pilha ficaria vazia; a convenção prática é representar como binário com um único nó contendo . - No laço de divisão:
- O resto
é um dígito binário (ou ou ). - Empilhamos
porque o primeiro resto é o bit menos significativo; precisamos inverter a ordem depois. - Atualizar
aproxima-nos do próximo bit.
- O resto
- Na fase de desempilha:
- Cada
retorna o próximo bit do mais significativo para o menos significativo, exatamente a ordem desejada para a lista de saída. - Mantemos
para anexar em tempo constante cada novo nó (se não, teríamos que percorrer a lista até o final a cada anexação).
- Cada
- Complexidade:
- Tempo:
operações, pois o número de bits em é aproximadamente . - Espaço extra:
para a pilha e para a lista de saída (os nós).
- Tempo:
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
# 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
# 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
define um nó simples com campos e . - Em
, o teste inicial trata . -
é iniciada vazia; no laço calculamos e empilhamos. - Após terminar, desempilhamos com
e criamos nós na ordem correta; permite anexar em . - Por fim retornamos
.
- A função
Passo 7
Exemplos práticos passo a passo (para você ver como o empilhamento e desempilhamento funcionam na prática).
Exemplo
:
- Inicial:
, pilha = . - Iteração 1:
→ pilha = ; . - Iteração 2:
→ pilha = ; . - Iteração 3:
→ pilha = ; . - Iteração 4:
→ pilha = ; . Laço termina. - Desempilhar e criar lista:
- pop() →
→ lista: - pop() →
→ lista: - pop() →
→ lista: - pop() →
→ lista:
- pop() →
- Resultado: representa
, que é binário de .
Exemplo
:
- Resto sequencial:
(empilhados nessa ordem) → desempilhando gera que é .
Exemplo
:
- Resto único
→ lista apenas .
Exemplo
(caso tratado):
- Retorna lista com nó
.
Passo 8
Dicas para a prova (o que escrever e o que justificar rapidamente):
- Explique a ideia: “usar divisões por
para obter restos e empilhar os restos; depois desempilhar para obter a ordem correta”. - Mostre corretamente um exemplo curto, por exemplo
, com os restos empilhados e o resultado final. - Indique complexidades
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 init(self, valor):
self.valor = valor
self.prox = None
def decimal_to_binary_linked_list(n):
if n == 0:
return Node(0)
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