EP5
EP5 - Barras de alumínio
Objetivos
Praticar o raciocínio recursivo para decompor um problema e exercitar a implementação de uma função recursivo.
Problema
Um revendedor de barras de alumínio possui um estoque de barras. Esse revendedor deseja atender uma lista de pedidos.
O estoque do revendedor é representado por uma lista de números inteiros positivos em que cada número corresponde ao comprimento de uma barra disponível no estoque.
Um pedido é um número inteiro positivo que representa o comprimento da barra desejada por um cliente. Todos os comprimentos são em centímetros.
Para atender a um pedido qualquer barra disponível no estoque pode ser cortada a fim de obter uma barra de comprimento exatamente igual ao do pedido. Barras não podem ser coladas a fim de atender a um pedido. Um pedido de 100 centímetros não pode ser atendido por duas barras de 50 centímetros, ou uma de 20 centímetros, outra de 50 centímetros e outra de 30 centímetros, etc.
O que você deve fazer
Neste EP5 você fará um programa que lê:
- uma lista de valores que representam o estoque, e
- uma lista de valores que representam os pedidos.
Não haverá atendimento parcial dos pedidos. Isto é, ou todos os pedidos são atendidos com as barras disponíveis no estoque ou nenhum é atendido.
O seu programa deve produzir mensagens indicando como cada barra deve ser cortadas a fim de atender a cada pedido da lista de pedidos. Além disso, o programa deve imprimir mensagens indicando o estado do estoque após atender os pedidos.
Caso não seja possível atender a todos os pedidos com as barras no estoque o programa imprime uma mensagem indicando esse fato.
Você deverá escrever duas funções:
main()
; eprocesse_pedidos()
.
A especificação de cada uma dessas funções está no doc-string da função no arquivo esqueleto_ep5.py
. A sua função processe_pedidos()
deverá ser recursiva.
Exemplos de execução do programa
As mensagens do seu programa devem ser exatamente iguais as dos exemplos a seguir. O que aparece em vermelho foi digitado pelo usuário. Note que há exemplos com mensagens de erro devido a entradas inválidas.
Exemplo 0
estoque >>> 100
Estoque possui 1 barras:
barra 0: 100 cm
pedidos >>> 50 15 30
Há 3 pedidos para serem atendidos:
pedido 0: 50 cm
pedido 1: 15 cm
pedido 2: 30 cm
Maneira para atender aos pedidos:
pedido 0: corte 50 cm da barra 0
pedido 1: corte 15 cm da barra 0
pedido 2: corte 30 cm da barra 0
Sobras no estoque:
barra 0: 5 cm
Exemplo 1
estoque >>> 100 150
Estoque possui 2 barras:
barra 0: 100 cm
barra 1: 150 cm
pedidos >>> 70 90 70
Há 3 pedidos para serem atendidos:
pedido 0: 70 cm
pedido 1: 90 cm
pedido 2: 70 cm
Maneira para atender aos pedidos:
pedido 0: corte 70 cm da barra 1
pedido 1: corte 90 cm da barra 0
pedido 2: corte 70 cm da barra 1
Sobras no estoque:
barra 0: 10 cm
barra 1: 10 cm
Exemplo 2
estoque >>> 150 100
Estoque possui 2 barras:
barra 0: 150 cm
barra 1: 100 cm
pedidos >>> 80 80 80
Há 3 pedidos para serem atendidos:
pedido 0: 80 cm
pedido 1: 80 cm
pedido 2: 80 cm
Pedido(s) não pode(m) ser atendido(s).
É necessário comprar mais barras.
Exemplo 3
estoque >>> 60 70 50
Estoque possui 3 barras:
barra 0: 60 cm
barra 1: 70 cm
barra 2: 50 cm
pedidos >>> 40 5 25 30 25 55
Há 6 pedidos para serem atendidos:
pedido 0: 40 cm
pedido 1: 5 cm
pedido 2: 25 cm
pedido 3: 30 cm
pedido 4: 25 cm
pedido 5: 55 cm
Maneira para atender aos pedidos:
pedido 0: corte 40 cm da barra 1
pedido 1: corte 5 cm da barra 0
pedido 2: corte 25 cm da barra 2
pedido 3: corte 30 cm da barra 1
pedido 4: corte 25 cm da barra 2
pedido 5: corte 55 cm da barra 0
Sobras no estoque:
barra 0: 0 cm
barra 1: 0 cm
barra 2: 0 cm
Exemplo 4
estoque >>> 60 70 50
Estoque possui 3 barras:
barra 0: 60 cm
barra 1: 70 cm
barra 2: 50 cm
pedidos >>> 60 25 35 10 35 15
Há 6 pedidos para serem atendidos:
pedido 0: 60 cm
pedido 1: 25 cm
pedido 2: 35 cm
pedido 3: 10 cm
pedido 4: 35 cm
pedido 5: 15 cm
Maneira para atender aos pedidos:
pedido 0: corte 60 cm da barra 1
pedido 1: corte 25 cm da barra 0
pedido 2: corte 35 cm da barra 2
pedido 3: corte 10 cm da barra 1
pedido 4: corte 35 cm da barra 0
pedido 5: corte 15 cm da barra 2
Sobras no estoque:
barra 0: 0 cm
barra 1: 0 cm
barra 2: 0 cm
Exemplo 5
estoque >>> 100 150 100
Estoque possui 3 barras:
barra 0: 100 cm
barra 1: 150 cm
barra 2: 100 cm
pedidos >>> 80 35 79 70 35 35
Há 6 pedidos para serem atendidos:
pedido 0: 80 cm
pedido 1: 35 cm
pedido 2: 79 cm
pedido 3: 70 cm
pedido 4: 35 cm
pedido 5: 35 cm
Pedido(s) não pode(m) ser atendido(s).
É necessário comprar mais barras.
Exemplo 6
estoque >>> 100 150 100
Estoque possui 3 barras:
barra 0: 100 cm
barra 1: 150 cm
barra 2: 100 cm
pedidos >>> 80 35 70 70 35
Há 5 pedidos para serem atendidos:
pedido 0: 80 cm
pedido 1: 35 cm
pedido 2: 70 cm
pedido 3: 70 cm
pedido 4: 35 cm
Maneira para atender aos pedidos:
pedido 0: corte 80 cm da barra 2
pedido 1: corte 35 cm da barra 0
pedido 2: corte 70 cm da barra 1
pedido 3: corte 70 cm da barra 1
pedido 4: corte 35 cm da barra 0
Sobras no estoque:
barra 0: 30 cm
barra 1: 10 cm
barra 2: 20 cm
Exemplo 7
estoque >>> 100 vinte
ERRO: valores no estoque devem ser inteiros ('vinte')
Exemplo 8
estoque >>> 100 150 100
Estoque possui 3 barras:
barra 0: 100 cm
barra 1: 150 cm
barra 2: 100 cm
pedidos >>> 8 xyz ghi
ERRO: valor de cada pedido deve ser inteiro ('xyz')
Roteiro
-
Faça o download do arquivo
esqueleto_ep5.py
. -
Mude o nome do arquivo
esqueleto_ep5.py
paraNUSP_ep5.py
, onde oNUSP
é o seu número USP. -
Abra o esqueleto no Spyder ou em qualquer outro editor ou ambiente apropriado para desenvolver programas em Python.
-
Leia e preencha o cabeçalho com o seu nome, nusp, etc. Não modifique o resto do cabeçalho.
-
Execute o arquivo para ver se está tudo ok. O programa deve imprimir:
Vixe! Ainda não fiz a função main(). Vixe! Ainda não fiz a função processe_pedidos().
-
Antes de escrever cada função, leia atentamente a especificação da função e os exemplos.
-
Teste cada função separadamente das demais usando o console do Spyder (= Python Shell ou IPython). Você também pode usar para os testes um terminal.
-
Teste o EP5 completo, chamando agora a função
main()
, inclusive com outros exemplos além dos fornecidos. -
Após testar o seu programa com vários exemplos, entregue o arquivo
NUSP_ep5.py
. -
Não deixe de seguir as Instruções para entrega de EPs.
Entrega
A primeira entrega deve ser feita até o dia 22/09 (até 23h55m).
O EP receberá comentários no dia 23/09.
Uma nova versão poderá ser entregue até o dia 25/09 (até 23h55m).
- 13 setembro 2016, 21:30 PM