Implementação e análise de algoritmos, ordenação e busca em arrays, otimização de funções, complexidade de tempo com notação Big O, manipulação de listas e dicionários, estruturas de dados (pilhas e filas) e simulação de máquinas e processos.
Big-O é a linguagem que usamos para falar sobre como o “custo” de um algoritmo cresce quando a entrada aumenta. Em geral, medimos dois custos: tempo (quantas operações) e espaço (quanta memória extra). Ignoramos detalhes de hardware e constantes, focando no crescimento assintótico: como o custo escala quando N vai ficando muito grande.
# Exemplos rápidos (tempo e espaço)
# O(1) tempo, O(1) espaço
def pega_central(a):
return a[len(a)//2] if a else None
# O(N) tempo, O(1) espaço (retorno antecipado ajuda no melhor/médio caso)
def tem_x(s):
for c in s:
if c == 'X':
return True
return False
# O(N log N) tempo (ordenação), O(N) espaço (implementação típica do sort)
def ordenar(a):
return sorted(a)
# O(N^2) tempo, O(1) espaço
def tem_par_igual(a):
for i in range(len(a)):
for j in range(i+1, len(a)):
if a[i] == a[j]:
return True
return False
# Mesmo tempo O(N), mas espaços diferentes:
# O(1) espaço (sem lista auxiliar)
def soma_dobrada_inplace(a):
s = 0
for x in a:
s += 2*x
return s
# O(N) espaço (cria lista auxiliar)
def copia_e_dobra(a):
b = [2*x for x in a]
return sum(b)Use Big-O como mapa para projetar e comparar soluções, e combine com medições para decidir o que entregar em produção. Com essa bússola, os exercícios a seguir ganham contexto e propósito.
Dada a lista ordenada crescentemente abaixo, implemente uma função que retorne a mediana em O(1). Para N ímpar, retorne o elemento central; para N par, a média dos dois centrais; se vazia, retorne None.
def mediana(lista_ord):
soma = 0
cont = 0
for i in range(len(lista_ord)):
if i == len(lista_ord) // 2 or (len(lista_ord) % 2 == 0 and i == len(lista_ord) // 2 - 1):
soma += lista_ord[i]
cont += 1
return soma / contdef mediana_otimizada(lista_ord):
n = len(lista_ord)
if n == 0:
return None
k = n // 2
if n % 2 == 1:
return lista_ord[k]
return (lista_ord[k-1] + lista_ord[k]) / 2
# Exemplos
print(mediana_otimizada([10, 20, 30, 40, 50])) # 30
print(mediana_otimizada([10, 20, 30, 40, 50, 60])) # 35.0Dada uma lista de candidatos (dicionários com ni, nome, idade, pontos), ordene-a alfabeticamente por nome (A→Z) utilizando Selection Sort e retorne a lista ordenada.
def selection_sort_por_nome(cands):
n = len(cands)
for i in range(n):
idx_min = i
for j in range(i+1, n):
if cands[j]["nome"] < cands[idx_min]["nome"]:
idx_min = j
cands[i], cands[idx_min] = cands[idx_min], cands[i]
return cands
print(selection_sort_por_nome(exemplo))
[{'ni': 3, 'nome': 'André', 'idade': 22, 'pontos': 90},
{'ni': 4, 'nome': 'Bruna', 'idade': 38, 'pontos': 95},
{'ni': 1, 'nome': 'José', 'idade': 28, 'pontos': 97},
{'ni': 2, 'nome': 'Márcia','idade': 36, 'pontos': 95}]Considerando as mesmas definições da questão acima, ordene os candidatos por pontos em ordem decrescente e, em caso de empate, por idade também em ordem decrescente, utilizando Insertion Sort (estável).
def insertion_sort_por_pontos_idade(cands):
for i in range(1, len(cands)):
atual = cands[i]
j = i - 1
while j >= 0:
a, b = atual, cands[j]
melhor = (a["pontos"] > b["pontos"]) or (
a["pontos"] == b["pontos"] and a["idade"] > b["idade"]
)
if melhor:
cands[j+1] = cands[j]
j -= 1
else:
break
cands[j+1] = atual
return cands
exemplo = [
{"ni": 1, "nome": "José", "idade": 28, "pontos": 97},
{"ni": 2, "nome": "Márcia","idade": 36, "pontos": 95},
{"ni": 3, "nome": "André", "idade": 22, "pontos": 90},
{"ni": 4, "nome": "Bruna", "idade": 38, "pontos": 95},
]
print(insertion_sort_por_pontos_idade(exemplo))Analise a complexidade temporal da função soma_100 que verifica pares simétricos somando 100. Determine a ordem assintótica e justifique.
def soma_100(lista):
esq, dir = 0, len(lista)-1
while esq < len(lista) // 2:
if lista[esq] + lista[dir] != 100:
return False
esq += 1
dir -= 1
return True1. A Estratégia da Função: "Ponteiros que se Encontram"
Imagine que a lista é uma rua, e você quer verificar casas que ficam em posições espelhadas (a primeira com a última, a segunda com a penúltima, etc.). A função usa dois "ponteiros" (as variáveis esq e dir) que funcionam como dois carteiros:
esq começa no início da rua (posição 0).dir começa no final da rua (posição N-1).A cada iteração do laço os carteiros dão um passo em direção ao outro e verificam os números das casas onde pararam. O objetivo deles é se encontrar no meio da rua.
2. Onde Está o "Trabalho" do Algoritmo? No laço!
O principal trabalho acontece dentro do laço while. Para saber a complexidade, nos perguntamos:
esq < len(lista) // 2. Como esq avança um passo de cada vez, ele dará exatamente N/2 passos para chegar ao meio, onde N é o tamanho da lista.3. Calculando a Complexidade Total (Pior Caso)
O "pior caso" é quando a lista é perfeitamente simétrica (todos os pares somam 100) e o algoritmo precisa percorrer todo o caminho até o meio para confirmar. Nesse caso:
4. A Simplificação da Notação Big O
Como a análise de complexidade se preocupa com a escala do problema, queremos saber como o tempo de execução cresce à medida que a lista fica enormemente grande. Como podemos deduzir, o tempo de execução cresce de forma diretamente proporcional ao tamanho da lista. Portanto, dizemos que o crescimento é linear.
Logo, como na notação Big O ignoramos constantes (como o "dividido por 2"), já que elas não alteram a natureza do crescimento, crescer a uma taxa de N ou N/2 é, em essência, a mesma "coisa". Por isso, simplificamos O(N/2) para O(N).
“Na prática, se a lista tiver 1 milhão de elementos, o algoritmo vai precisar de aproximadamente 500 mil passos. Mas, em análise assintótica, tanto 500 mil quanto 1 milhão são tratados como O(N), pois o que importa é que o tempo cresce proporcionalmente ao tamanho da lista.”
Considere a função abaixo procura o maior produto entre três elementos distintos usando três laços aninhados. Qual a complexidade temporal dela, no pior caso? Justifique.
def maior_produto(lista):
maior = lista[0] * lista[1] * lista[2]
n = len(lista)
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
prod = lista[i]*lista[j]*lista[k]
if prod > maior:
maior = prod
return maiorC(n, 3) = n! / (3! × (n-3)!)! indica fatorial, que é o produto de todos os números inteiros positivos até aquele número.
Por exemplo:3! × (n-3)!?
A B C D E
A B C E D
B A C D E
C B A E D
Como esses arranjos extras **não alteram o trio escolhido**, dividimos por (n-3)! = 2! = 2, para contar cada trio distinto **uma única vez**.
(a, b, c)
(a, c, b)
(b, a, c)
(b, c, a)
(c, a, b)
(c, b, a)
Como resta evidente, todas essas combinações representam o mesmo trio {a, b, c}. É por isso que dividimos por 6 (3!), para contar apenas uma vez. Capisce?C(n,3), n não é 3.
n é o **tamanho da lista**, que pode ser grande. O número 3 é apenas a quantidade de elementos que queremos escolher. Sendo assim, se a lista tiver 5 elementos, n = 5:
C(5,3) = (5 × 4 × 3) / 6 = 10
Se a lista tiver 10 elementos, n = 10:
C(10,3) = (10 × 9 × 8) / 6 = 120
Como são 3 elementos, no primeiro caso, dos 5 elementos, o fatorial vai atá a quantidade de elemetnos: 5, 4, 3. Sacaram? No segundo caso, com 10 elementos, mesma coisa: 10, 9, 8. O resto do fatorial (2, 1) é eliminado na divisão.n(n-1)(n-2)/6,
que é da ordem de N³ em notação Big-O.maior1 × maior2 × maior3 com menor1 × menor2 × maior1.
def maior_produto_eficiente(lista):
# Inicializa os três maiores e os dois menores
maior1 = maior2 = maior3 = float('-inf')
menor1 = menor2 = float('inf')
for x in lista:
# Atualiza os três maiores valores
if x > maior1:
maior3 = maior2
maior2 = maior1
maior1 = x
elif x > maior2:
maior3 = maior2
maior2 = x
elif x > maior3:
maior3 = x
# Atualiza os dois menores valores
if x < menor1:
menor2 = menor1
menor1 = x
elif x < menor2:
menor2 = x
# Calcula os dois possíveis maiores produtos
produto_maior = maior1 * maior2 * maior3
produto_misturado = maior1 * menor1 * menor2 # Considera dois negativos
# Retorna o maior produto possível
return max(produto_maior, produto_misturado)
# Exemplo de uso
lista = [-10, -10, 5, 2, 3]
print(maior_produto_eficiente(lista)) # Saída: 500
A função abaixo retorna a soma de todos os números de um array dobrados. Use a notação Big O para descrever a complexidade da função, justificando sua resposta.
def dobra_e_soma(array):
array_dobrado = []
for num in array:
array_dobrado.append(num * 2)
soma = 0
for num in array_dobrado:
soma += num
return soma
Complexidade temporal: O(N). A função percorre o array original uma vez para dobrar os valores e depois percorre o array resultante para somá-los. Cada operação é O(1), então somando os percursos lineares temos O(N + N) = O(N).
Complexidade espacial: O(N), devido à criação do array auxiliar array_dobrado, que armazena N elementos.
É possível otimizar essa função de modo que ela realize a mesma tarefa, mas tenha uma complexidade de ordem menor? Se a resposta for sim, explique como. Se for não, justifique.
Sim, é possível otimizar a função, mas apenas em termos de espaço, não de tempo. A complexidade temporal já é O(N), que é mínima para percorrer todos os elementos de um array. Podemos evitar a criação do array auxiliar array_dobrado e calcular a soma diretamente, como mostrado abaixo:
def dobra_e_soma(array):
soma = 0
for num in array:
soma += num * 2
return somaÉ possível otimizar essa função de modo que ela realize a mesma tarefa, mas com uma quantidade total de passos menor? Se a resposta for sim, explique como. Se for não, justifique.
Sim, é possível reduzir a quantidade total de passos da função, embora a complexidade temporal permaneça O(N), combinando os dois laços em um só, como demonstramos acima.
Por fim, apesar da Complexidade temporal continuar O(N), já que cada elemento ainda precisa ser processado, a Complexidade espacial, entretanto, foi reduzida para O(1), haja vista a inexistência de array auxiliar.
Essa abordagem mantém a mesma ordem de complexidade, mas diminui o número total de operações realizadas, tornando a função mais eficiente na prática.
A função abaixo itera sobre um array de números e, para cada nº cujo índice é par, imprime a soma daquele nº com cada nº do array. Use a notação Big O para descrever a complexidade da função, justificando sua resposta.
def soma_louca(array):
for i in range(len(array)):
if i % 2 == 0:
for num in array:
print(array[i] + num)Resposta: Tempo: O(n^2); Espaço: O(1).
Justificativa: o laço externo percorre n índices e, para aproximadamente n/2 índices pares, o laço interno percorre n elementos. Total ≈ (n/2) × n = n^2/2 ⇒ O(n^2). A checagem i % 2 só reduz por constante, ignorada em Big O.
É possível otimizar essa função de modo que ela realize a mesma tarefa, mas tenha uma complexidade de ordem menor? Se a resposta for sim, explique como. Se for não, justifique.
Não. A tarefa exige imprimir ~N²/2 resultados (um por par com índice par), o que impõe limite inferior Ω(N²) apenas para produzir a saída. Reduzir a ordem exigiria mudar o problema (por exemplo, sumarizar em vez de imprimir cada soma).
É possível otimizar essa função de modo que ela realize a mesma tarefa, mas com uma quantidade total de passos menor? Se a resposta for sim, explique como. Se for não, justifique.
Sim, é possível reduzir o número de passos/overhead mantendo O(N²): percorra apenas índices pares (sem if), evite buscas repetidas e minimize chamadas de I/O.
import sys
def soma_louca_otimizada(array):
pr = sys.stdout.write
nl = '\n'
arr = array # alias local para evitar lookup global
for i in range(0, len(arr), 2): # sem teste de paridade por iteração
base = arr[i]
# escreve um bloco por linha de i, reduzindo chamadas de I/O
pr(nl.join(str(base + x) for x in arr) + nl)A função abaixo verifica se um “X” maiúsculo está presente em uma string ou não. Use a notação Big O para descrever a complexidade da função, justificando sua resposta.
def contem_x(string):
encontrou_x = False
for c in string:
if c == 'X':
encontrou_x = True
return encontrou_xResposta: Tempo: O(N); Espaço: O(1).
Justificativa: percorre todos os N caracteres fazendo comparações O(1) e sem estruturas auxiliares. Como não há retorno antecipado, mesmo se 'X' aparecer cedo o laço segue até o fim; portanto melhor, médio e pior casos são O(N). O uso de uma variável booleana não altera a ordem e mantém o espaço constante.
É possível otimizar essa função de modo que ela realize a mesma tarefa, mas tenha uma complexidade de ordem menor no pior caso? Se a resposta for sim, explique como. Se for não, justifique.
Não. No pior caso (quando não há 'X'), é necessário inspecionar todos os N caracteres para concluir a ausência, impondo limite inferior Ω(N). Só é possível reduzir constantes (retorno antecipado, I/O menor), não a ordem. Em cenários com múltiplas consultas sobre a mesma string, dá para pré-processar em O(N) e responder cada consulta em O(1), mas a primeira passagem permanece O(N).
É possível otimizar essa função de modo que ela realize uma quantidade total de passos menor em alguns casos? Se a resposta for sim, explique como. Se for não, justifique.
def contem_x_otimizado(string):
for c in string:
if c == 'X':
return True
return FalseO código abaixo define uma função que verifica se um array de números contém um par de números cuja soma é 10. Esta implementação da função tem complexidade O(N²). Otimize o código de modo que a função realize a mesma tarefa, mas com complexidade O(N).
def soma_10(array):
for i in range(len(array)):
for j in range(len(array)):
if i != j and array[i] + array[j] == 10:
return True
return FalseSolução O(N) usando um set:
def soma_10_otimizado(array):
vistos = set()
for x in array:
if 10 - x in vistos:
return True
vistos.add(x)
return False
print(soma_10_otimizado([1,2,3,9])) # True (1+9)
print(soma_10_otimizado([1,2,3,4,5])) # False
Escreva uma função que retorna a interseção de dois arrays.
A interseção é um terceiro array que contém todos os valores contidos ao mesmo tempo em ambos os arrays de entrada.
Por exemplo, a interseção de [1, 2, 3, 4, 5] e [0, 2, 4, 6, 8] é [2, 4].
Sua função deve ter complexidade O(N), onde N é o comprimento do maior array.
def intersecao(a, b):
if len(a) < len(b):
s, arr = set(a), b
else:
s, arr = set(b), a
res = []
for x in arr:
if x in s:
res.append(x)
s.discard(x) # evita duplicar no resultado
return res
print(intersecao([1,2,3,4,5], [0,2,4,6,8])) # [2, 4]
O(1)).
Em seguida, percorre apenas o array maior, checando interseções de forma eficiente.
Além disso, o uso de discard() evita elementos repetidos no resultado,
mantendo a resposta correta mesmo quando há duplicatas nas entradas.
Dada uma lista de inteiros, retorne o primeiro valor que aparece duas vezes ao percorrer da esquerda para a direita; caso contrário, retorne None.
def primeiro_duplicado(arr):
vistos = set()
for x in arr:
if x in vistos:
return x
vistos.add(x)
return None
print(primeiro_duplicado([1,2,3,4,5,0,2,4,6,8])) # 2Dada uma string, devolva o primeiro caractere não repetido. Se todos repetirem, retorne None. Faça em O(N) com duas passagens.
def primeiro_nao_duplicado(s):
freq = {}
for ch in s:
freq[ch] = freq.get(ch, 0) + 1
for ch in s:
if freq[ch] == 1:
return ch
return None
print(primeiro_nao_duplicado("minimamente")) # 'a'Inverta uma string usando uma pilha implementada por você. Não utilize atalhos como [::-1] ou reversed.
class Pilha:
def __init__(self):
self._d = []
def push(self, x):
self._d.append(x)
def pop(self):
return self._d.pop() if self._d else None
def is_empty(self):
return len(self._d) == 0
def inverter_com_pilha(s):
p = Pilha()
for ch in s:
p.push(ch)
out = []
while not p.is_empty():
out.append(p.pop())
return ''.join(out)
print(inverter_com_pilha("abcde")) # edcbaUma pilha é uma estrutura de dados simples e poderosa. Ela segue a regra LIFO (Last In, First Out), ou seja: o último elemento a entrar é o primeiro a sair. Pense numa pilha de pratos: você coloca sempre por cima (push) e retira sempre por cima (pop).
pilha (stack), como temos em JAVA, C++, C# (.NET) ou Ruby, entre outras linguagens. Para o bem ou para o mal, o "Guido van Rossum, desenvolveu o Python para ser uma linguagem mais simples, legível e poderosa. Talvez por isso: dada a semelhança entre listas e pilhas, não criou uma estrutura própria para a última, apenas adaptando a primeira (lista) para tal fim. Ou ele estava com preguiça de escrever. Vai saber. kkk. Mas o que importa, pelo menos aqui, é o seguinte:
append()pop()insert()remove()sort()reverse()lista[2:5])
pilha = []
pilha.append(10) # push
pilha.append(20)
pilha.append(30)
print(pilha) # [10, 20, 30]
pilha.pop() # pop → remove 30
print(pilha) # [10, 20]
Fica a dica: implementar uma classe (limitando os métodos) ajuda a treinar o raciocínio e enxergar a pilha como entidade independente. Veja:
class Pilha:
def __init__(self):
self._d = []
def push(self, x):
self._d.append(x)
def pop(self):
return self._d.pop() if self._d else None
def is_empty(self):
return len(self._d) == 0
s[::-1], usar a pilha tem valor pedagógico: ela mostra como uma estrutura de dados simples resolve problemas de forma natural e generalizável, como na análise de expressões, verificação de parênteses ou histórico de ações em editores.
Se você chegou até aqui e ainda se questiona sobre a importância das pilhas, esta é a resposta:deque, conhecer pilhas ajuda a entender e usar estruturas nativas em outras linguagens (Java, C++, C#) de forma correta.Em resumo: a pilha não é apenas uma lista com outro nome. É uma forma de organizar o pensamento e resolver problemas de maneira elegante e generalizável.
| Comando | Descrição |
|---|---|
push <val> |
Empilha um valor constante. Ex: push 20 (empilha o valor 20). |
push R<pos> |
Empilha um valor que está na memória RAM. Ex: push R2 (empilha o valor da célula 2 da RAM). |
pop R<pos> |
Consome o valor do topo da pilha e armazena na RAM. Ex: pop R1 (remove o topo e salva na célula 1). |
add |
Consome dois valores da pilha, soma e empilha o resultado. |
mul |
Consome dois valores da pilha, multiplica e empilha o resultado. |
div |
Consome dois valores da pilha, divide o elemento que está abaixo do topo pelo elemento do topo, e empilha o resultado (divisão inteira). |
sub |
Consome dois valores da pilha, subtrai o elemento que está no topo do elemento abaixo do topo, e empilha o resultado. |
print |
Consome um valor da pilha e o imprime em uma linha. |
Entrada: Seu programa deverá receber (como argumento de linha de comando) o caminho de um arquivo contendo o código a ser executado. Cada linha do arquivo deve conter um dos comandos descritos acima.
Saída: Seu programa deverá emular a execução do código contido no arquivo de entrada, utilizando 2 estruturas: uma pilha de dados e uma lista simulando a memória RAM de 64 células. Sempre que um comando print for encontrado no código, o valor no topo da pilha deverá ser consumido e impresso no console. Esta será a saída do seu programa.
Exemplos:
push 10
push 20
add
printpush 10
push 20
add
pop R0
push 3
push 5
mul
pop R1
push 44
push R0
push R1
div
sub
printimport sys
class Pilha:
def __init__(self):
self._d = []
def push(self, x):
self._d.append(x)
def pop(self):
return self._d.pop() if self._d else None
def emular(caminho):
p = Pilha()
ram = [0]*64
with open(caminho) as f:
for linha in f:
partes = linha.strip().split()
if not partes: continue
op = partes[0].lower()
if op == 'push':
v = partes[1]
if v.upper().startswith('R'):
idx = int(v[1:])
p.push(ram[idx])
else:
p.push(int(v))
elif op == 'pop':
dest = partes[1]
idx = int(dest[1:])
ram[idx] = p.pop()
elif op in ('add','sub','mul','div'):
b, a = p.pop(), p.pop()
if op == 'add': p.push(a+b)
if op == 'sub': p.push(a-b)
if op == 'mul': p.push(a*b)
if op == 'div': p.push(a//b)
elif op == 'print':
print(p.pop())
if __name__ == '__main__':
if len(sys.argv) != 2:
print('Uso: python emulador.py ')
else:
emular(sys.argv[1]) Pilha permite empilhar valores (push) e desempilhá-los (pop), seguindo a lógica LIFO.ram com 64 posições armazena valores nos registradores R0..R63.push, pop, add, sub, mul, div e print. O código lê linha a linha e executa a operação correspondente.R0..R63).div usa **divisão inteira** (//), garantindo que o resultado seja um número inteiro.Lembre-se: essa abordagem permite entender na prática como a pilha e a memória interagem, tornando conceitos abstratos mais concretos (ou tentando). O uso de divisão inteira e índices de registradores são "detalhes" da simulação que garantem consistência e evitam erros.
Diferentemente das Pilhas, as Filas são frequentemente usadas para simular o fluxo de pessoas, carros, aviões, transações e assim por diante. Lembre-se: Filas utilizam o sistema FIFO (First In, First Out), ou seja, o primeiro a entrar é o primeiro a sair, como as filas de um supermercado, onde os clientes chegam e se alinham para pagar suas compras. Cada caixa possui sua própria fila, e os clientes são atendidos na ordem em que chegaram.
E é justamente isso que faremos aqui. A ideia é escrever um programa que modele as filas de caixas de um supermercado usando estruturas de dados do tipo fila. O sistema deve modelar 4 filas, inicialmente vazias, para os caixas A, B, C e D. Para facilitar, usaremos uma string para modelar os eventos de entrada em uma fila e conclusão do pagamento. Uma letra minúscula indicará um novo cliente entrando em uma das filas, e uma letra maiúscula indicará um cliente concluindo o pagamento na fila correspondente. Por exemplo, a string aababbAbA representa 3 pessoas entrando na fila do caixa A com 2 delas concluindo o pagamento, e 4 pessoas entrando na fila do caixa B.
Cada cliente será representado pela letra C seguida de um número único. Esta string deverá ser adicionada na fila em que o cliente entrar. Por exemplo, ao processar a string aabdcb, teríamos a seguinte sequência de entradas: os clientes “C1” e “C2” entram na fila A, “C3” na B, “C4” na D, “C5” na C, e “C6” na B. Além disso, o caractere “,” será usado na string para sinalizar que o conteúdo atual de cada uma das filas deve ser impresso. Confuso? Pera lá! Veja:
Exemplo: aababbAbA
Evt | Fila A | Fila B | Ação
-----+-------------------+-------------------+-----------------------------
a | [C1] | [] | entra C1 em A
a | [C1, C2] | [] | entra C2 em A
b | [C1, C2] | [C3] | entra C3 em B
a | [C1, C2, C4] | [C3] | entra C4 em A
b | [C1, C2, C4] | [C3, C5] | entra C5 em B
b | [C1, C2, C4] | [C3, C5, C6] | entra C6 em B
A | [C2, C4] | [C3, C5, C6] | paga C1 em A
b | [C2, C4] | [C3, C5, C6, C7] | entra C7 em B
A | [C4] | [C3, C5, C6, C7] | paga C2 em A
Resumo final:
A: [C4]
B: [C3, C5, C6, C7]
1. Entrada de clientes:
Cada letra minúscula representa um cliente entrando na fila de um caixa.
A string aaaa, indica que quatro clientes entram na fila A na ordem de chegada:
2. Conclusão do pagamento:
Cada letra maiúscula representa um cliente que concluiu o pagamento na fila correspondente.
- A fila segue a lógica FIFO (First In, First Out), ou seja, o cliente que entrou primeiro paga primeiro.
- Assim, a sequência AA informa que os dois primeiros cliente da fila A pagaram e saíram:
- Os clientes restantes na fila A agora são: C3 e C4.
Lembre-se: a letra maiúscula não pula clientes: ela sempre remove o próximo cliente que entrou na fila.
Dito isso, vamos então implementar a função que simula isso. Atenção para as entradas e saídas:
Entrada: o programa deverá receber (como argumento de linha de comando) uma string representando a sequência de eventos a ser simulada, conforme especificado acima.
Saída: o programa deverá simular os eventos listados na string de entrada. Sempre que uma vírgula for encontrada na string, o estado atual das filas deverá ser impresso no console (imprima uma quebra de linha adicional no final para facilitar a visualização, conforme exemplo abaixo). Esta será a saída do seu programa. Exemplos:
String de eventos
aaaa,AAbcd,String de eventos
abababcabc,Adb,Adb,Ca,
class Fila:
def __init__(self):
self._d = []
def enqueue(self, x):
self._d.append(x)
def dequeue(self):
return self._d.pop(0) if self._d else None
def __repr__(self):
return str(self._d)
def simular(eventos):
filas = {c: Fila() for c in 'ABCD'}
cid = 0
for ev in eventos:
if ev in 'abcd':
cid += 1
filas[ev.upper()].enqueue(f'C{cid}')
elif ev in 'ABCD':
filas[ev].dequeue()
elif ev == ',':
print(f"A: {filas['A']}")
print(f"B: {filas['B']}")
print(f"C: {filas['C']}")
print(f"D: {filas['D']}\n")
simular("aaaa,AAbcd,")Cada letra minúscula adiciona um cliente à fila correspondente, numerando-o sequencialmente como C1, C2, C3..., cada letra maiúscula remove o cliente que está no início da fila (FIFO), representando o pagamento concluído e a vírgula , serve para imprimir o estado atual de todas as filas no console. Por fim, a simulação acima mmostra as entradas, saídas e o estado a qualquer momento, conforme solicitado.
Uma abordagem alternativa adotada para caixas em alguns estabelecimentos comerciais é o sistema de fila única. Neste sistema, todos os clientes são organizados em uma única fila. Sempre que um caixa fica livre, o 1º cliente da fila é alocado para ser atendido no caixa disponível. Suponha agora que você trabalhará em um projeto para desenvolver outro simulador que modela um sistema de fila única com o objetivo de estimar quanto tempo levará para que todos os clientes sejam atendidos em cada cenário simulado.
Para este exercicio, vamos considerar que o estabelecimento tem N funcionários que trabalham nos caixas, identificados por números de 1 a N. Cada funcionário i leva um determinado tempo v_i (em segundos) para processar um item de um cliente. Ou seja, se um cliente j tem c_j itens em sua cesta, o funcionário i levaria v_i * c_j segundos para processar todos os itens deste cliente. Facinho, né?
Quando um cliente entra na fila para ser atendido, ele espera até que um funcionário esteja livre para atendê-lo. Se mais de um funcionário estiver livre ao mesmo tempo, o cliente será atendido pelo funcionário de menor número de identificação. Tal funcionário só estará livre novamente após processar todos os itens deste cliente.
Neste modelo de simulação simplificado, não consideraremos o tempo gasto para recebimento dos pagamentos nem os intervalos entre a finalização de um atendimento e o início de outro no mesmo caixa. Poderíamos adicionar algumas constantes para isso, mas como não é o caso, deixa para lá!
Para esta simulação, contamos apennas com os funcionários dos caixas e M clientes que estão na fila para serem atendidos, cada um com um determinado número de itens na sua cesta. A partir disso, o programa deve descobrir quanto tempo levará para que todos os clientes sejam atendidos. Simples assim! Mas fique atento à Entrada e à Saída exigidas:
Entrada: o programa deverá receber (como argumento de linha de comando) o caminho de um arquivo contendo os dados do cenário a ser simulado, no formato descrito a seguir. A primeira linha do arquivo conterá dois inteiros positivos N e M, indicando o número de funcionários nos caixas e o número de clientes, respectivamente. Em seguida haverá uma linha com N inteiros positivos v_i, indicando quantos segundos leva para o funcionário i processar um item. Em seguida haverá uma linha com M inteiros positivos c_j, indicando quantos itens o cliente j tem em sua cesta.
Saída: o programa deverá imprimir uma linha contendo um inteiro, indicando quanto tempo (em segundos) levará para que todos os clientes sejam atendidos de acordo com a simulação do cenário descrito no arquivo de entrada.
Exemplos:
Arquivo de entrada:
1 1
30
6Arquivo de entrada:
1 2
10
5 3Arquivo de entrada:
2 3
10 20
10 5 3
import sys
class Fila:
def __init__(self, dados=None):
self._d = list(dados or [])
def dequeue(self):
return self._d.pop(0) if self._d else None
def is_empty(self):
return not self._d
def simular_fila_unica(caminho):
with open(caminho) as f:
n, m = map(int, f.readline().split())
v = list(map(int, f.readline().split()))
itens = list(map(int, f.readline().split()))
fila = Fila(itens)
livre = [0]*n # tempo em que cada caixa estará livre
while not fila.is_empty():
c = fila.dequeue()
i_min = min(range(n), key=lambda i: (livre[i], i))
livre[i_min] += v[i_min]*c
print(max(livre))
if __name__ == '__main__':
if len(sys.argv) == 2:
simular_fila_unica(sys.argv[1])
else:
print('Uso: python fila_unica.py ') Como de costume,vamos com calma para conseguirmos organizar mentalmente a simulação do sistema de fila única acima. O supermercado tem vários caixas, mas apenas uma fila para todos os clientes, blá, blá, blá... Cada cliente tem sua cesta ou carrinho de compras com um certo número de itens, e cada caixa tem seu próprio ritmo: alguns são mais rápidos, outros mais lentos. Aff... Às vezes, bem lentos. kkkk!
A regra principal é simples:
v_i * c_j, ou seja, o ritmo do caixa multiplicado pelo número de itens do cliente.No código, simulamos isso mantendo:
livre que indica em que instante cada caixa estará disponível.A cada passo, visualizamos mentalmente:
Por fim, o tempo total para atender todos os clientes é o instante em que o último caixa termina de processar o cliente final, que corresponde ao valor máximo da lista livre.
Dessa forma, conseguimos simular de forma clara e precisa o funcionamento de uma fila única com múltiplos caixas e ritmos diferentes, sem complicação! Não falei que era fácinho?