MO417 - Questão para a prova oral

Número: 072

Enunciado:
A empresa Coffee Machines ltda produz máquinas do tipo Vending para cafés e bebidas quentes, onde nenhuma bebida custa mais do que R$ 1.00, que é o valor maior de pagamento aceito por suas máquinas. Recentemente a empresa resolveu lançar um novo modelo, onde é possível devolver o troco ao cliente (e não somente aceitar o pagamento em valor exato). Para isso, o gerente da Coffee Machines ltda contratou um estagiário que ficaria encarregado de desenvolver um algoritmo para o programa que seleciona as moedas que devem ser devolvidas ao cliente como troco. O algoritmo deve escolher o menor número de moedas possível, para manter sempre uma quantia de moedas razoável no "caixa" da máquina. Caso não haja nenhuma combinação de moedas para o troco, o algoritmo deve retornar uma mensagem avisando ao cliente.
As moedas disponíveis no caixa da máquina estão em ordem decrescente (esta ordem é mantida por outro módulo da máquina). Nomeamos o conjunto de moedas no caixa como C, e seus valores pertercem ao conjunto { 0.01, 0.05, 0.10, 0.25, 0.50 }.
A idéia usada pelo estagiário foi escrever um algoritmo guloso que escolheria um conjunto de moedas M, onde cada moeda m escolhida seria a moeda de maior valor em C, ainda não escolhida, que acrescentada à soma dos valores das moedas já escolhidas até o momento, não ultrapassaria o valor desejado para o troco.
Baseado nesta idéia, o estagiário então escreveu o seguinte algoritmo: 

			MONTA-TROCO(C,t)
				M ← {∅}
				soma_M ← 0
				i ← 1
				n ← comprimento[C]
				while (soma_M < t) and (i < n)
					do m ← C[i]
					   if (soma_M + m) ≤ t
						then M ← M U {m}
						     soma_M ← soma_M + m
					   i ← i + 1
				if soma_M = t
					then return M
					else return "Troco não disponível!"
Onde C é o conjunto de moedas atualmente no caixa da máquina e t é o valor do troco que se deseja compor.

Pouco tempo após o lançamento deste modelo de máquina, a empresa decidiu fazer um Recall pois desconfiava que a máquina apresentava os seguintes problemas:

I - Poderia retornar um troco de valor diferente do correto;
II - Poderia retornar uma quantidade de moedas maior do que o mínimo possível (considerando as moedas disponíveis no "caixa" da máquina);
III - Poderia dizer ao cliente que não há troco quando na verdade haveria uma combinação de moedas possível para aquele troco.

Dentre os problemas que a Coffee Machines ltda acredita existir, o(s) que realmente existe(m) é(são):

  1. apenas I
  2. apenas I e II
  3. apenas II e III
  4. apenas III
  5. NDA

Autor(a): Fernando José Vieira da Silva (RA: 085324)