MAC 324: Exercício de programação da terceira prova

A sistemática seguida referente a estas questões encontra-se na página: Especificações para a entrega do exercício de programação. Daqui em diante supomos que Você leu aquela página na íntegra.

Questão fácil (máximo de um ponto adicional na nota)

A silhueta de um conjunto de prédios

Considere um conjunto de prédios de forma retangular. A sua silhueta é a projeção dos prédios num plano imaginário atrás de todos eles.

Escreva um programa em Java que calcula eficientemente a silhueta de um conjunto de n prédios dados.

Uma silhueta pode ser representada por uma sequência de inteiros positivos (c[0],h[1],c[1],h[2],c[2],...,h[n],c[n]) onde os c[i] são comprimentos de segmentos horizontais de altura h[i]. A origem da silhueta é o ponto de coordenadas (0,0) e o seu término é o ponto de coordenadas (soma(c[i]),0).

Note que a silhueta de um prédio retangular é uma sequência da forma (c[0],h[1],c[1]).

O procedimento básico do seu programa deve ser um algoritmo para calcular a união de duas silhuetas dadas.

Por exemplo, dadas as silhuetas

 
(3,  6,4,  2,1,  9,4,  4,4, 17,3, 14,3,  9,5) e

(5,  4,4, 13,5,  6,4, 16,2, 11,3,  5,2) 

(3, 6,4, 4,1, 9,1, 13,5, 6,2, 17,3, 16,1, 14,2, 11,1, 9,4),

Uma estratégia muito eficiente consiste em dividir os prédios dados em duas "metades", calcular recursivamente a silhueta de cada "metade" e calcular a união das duas silhuetas obtidas.

Outra alternativa mais simples mas menos eficiente consiste em construir as silhuetas dos m primeiros prédios, para cada valor de m, tomando a união dos m-1 primeiros prédios com o m-ésimo.

Além das solicitações nas Especificações para a entrega do exercício de programação entregue também os resultados que o seu programa fornece para o exemplo dado, considerando separadamente os treze prédios do exemplo. Ou seja, não use o agrupamento de prédios do exemplo, use apenas os prédios propriamente ditos, conforme na sequência abaixo de dados:

(3,6,4)   (5,4,4)   (7,2,1)   (8,9,4)   (9,13,5) (12,4,4) (14,6,4)

(16,17,3) (18,16,2) (19,14,3) (20,11,3) (22,9,5) (23,5,2)

Questão difícil (máximo de dois pontos adicionais na nota da prova)

Acomodação ótima de arquivos em disquetes

Uma companhia que vende software precisa acomodar n arquivos, de tamanhos t=(t[1],t[2],...,t[n]), em disquetes de capacidade C, sendo que t[i]<=C, para cada i.

Faça um programa em Java que aloca os arquivos no menor número possível de disquetes.

Exemplo:    C=360

arquivo     1   2   3   4    5    6    7    8    9
tamanho    40  80  80  80  100  100  100  240  240
disquete    1   1   2   2    2    2    3    1    3 

No caso, são necessários 3 disquetes para acomodar os 9 arquivos, já que eles nao cabem em dois disquetes cuja capacidade é de 720. Note que se os arquivos fossem alocados na ordem que surgem, da esquerda para a direita, haveria necessidade de quatro disquetes.

Uma forma de testar o seu programa, é variar a ordem de apresentação dos arquivos e verificar se o número de disquetes se mantem ou não.

Outra forma de testes é repartir a capacidade de um certo número de disquetes em arquivos de tamanhos bem diferentes e apresentar os dados bem embaralhados para o programa. Ou seja, obter os dados a partir de uma solução pré-estabelecida. Por exemplo:

  360=20+40+60+80+100+10+50
  
  360=70+110+180
  
  360=15+25+35+45+55+65+75+22+23

Tente resolver agora a sequência:

  10 15 20 22 23 25 35 40 45 50 55 60 65 70 75 80 100 110 180

em diversas ordens.

Outro teste ainda: duplique cada arquivo (tome dois de 10, dois de 15, etc) e veja se o programa aloca os arquivos em 6 disquetes.

No relatório explique a função de cada variável no programa. Explique sucintamente o método que Você usou para gerar a solução. Divida o seu programa em blocos convenientes e explique também sucintamente a função de cada bloco.

A grosso modo, o seu programa vai ter que enumerar todas as possibilidades de alocação dos arquivos em um certo número de disquetes e escolher uma configuração que usa o mínimo de disquetes.

Obviamente, a melhor estrategia é Você estar absolutamente convencido de que o seu programa funciona corretamente através do entendimento completo do algoritmo utilizado. Neste caso Você não precisará se preocupar com tantos testes. É sempre bom lembrar porém que João Seguro morreu de velho.

Além das solicitações nas Especificações para a entrega do exercício de programação entregue também os resultados que o seu programa fornece para os exemplos dados.

Boa Sorte!

Dúvidas, pergunte ao Professor (mas não suponha que Você receberá uma resposta): Imre Simon <is@ime.usp.br>

Home page da disciplina MAC 324

Mapa do sítio da disciplina