MO417 - Questão para a prova oral

Número: 2009-072

Enunciado: Considere o algoritmo abaixo, concebido para selecionar as moedas que devem ser devolvidas a um cliente como troco numa máquina do tipo Vending para cafés e bebidas quentes. 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 pertencem ao conjunto { 0.01, 0.05, 0.10, 0.25, 0.50 }.  A idéia foi escrever um algoritmo guloso onde cada moeda m escolhida seria a de maior valor em C, ainda não escolhida, que acrescentada à soma dos valores das moedas já escolhidas não ultrapassasse o valor desejado para o troco:

   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.

Dentre as características abaixo, quais são as que se aplicam ao algoritmo proposto:

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

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

Ideia original de: Fernando José Vieira da Silva