Troco

Troco

Médio

Introdução

Na aldeia mística de Coinholt, estás atrás do balcão da tua padaria, a arrumar uma fornada fresca de pastéis. A porta abre-se com um rangido e entra Denara, uma comerciante habilidosa com bom olho para produtos de qualidade. Depois de uma refeição rápida, desliza uma moeda cintilante pelo balcão, com um valor de 100 unidades.

Sorris, pegas na moeda e olhas para o custo total da refeição: 88 unidades. Isso significa que tens de devolver 12 unidades de troco.

Denara estende a mão, à espera. «Dá-me só o menor número de moedas», diz ela com um sorriso. «A minha bolsa já está cheia e não quero correr o risco de as perder pelo caminho.»

Sabes que tens algumas opções. «Temos Lumis (valem 10 unidades), Viras (valem 5 unidades) e Zenth (valem 2 unidades) disponíveis para troco.»

Calculas rapidamente as possibilidades de cabeça:

  • um Lumis (1 × 10 unidades) + um Zenth (1 × 2 unidades) = 2 moedas no total
  • dois Viras (2 × 5 unidades) + um Zenth (1 × 2 unidades) = 3 moedas no total
  • seis Zenth (6 × 2 unidades) = 6 moedas no total

«A melhor escolha são duas moedas: um Lumis e um Zenth», dizes, enquanto lhe entregas o troco.

Denara sorri, claramente impressionada. «Como sempre, acertaste.»

Instruções

Determina o menor número de moedas a dar a um cliente para que a soma dos seus valores seja igual à quantia correta de troco.

Exemplos

  • Uma quantia de 15 com os valores de moeda disponíveis [1, 5, 10, 25, 100] deve devolver uma moeda de valor 5 e uma moeda de valor 10, ou [5, 10].
  • Uma quantia de 40 com os valores de moeda disponíveis [1, 5, 10, 25, 100] deve devolver uma moeda de valor 5, uma moeda de valor 10 e uma moeda de valor 25, ou [5, 10, 25].

Palavras

find-fewest-coins ( coins target -- result ) devolve um array de denominações de moedas cuja soma é target. coins é um hash set (por exemplo, HS{ 1 5 10 25 }); usa as palavras do vocabulário sets (members, in?, …) para trabalhar com ele.

Quando nenhuma combinação de coins permite chegar a target, lança um erro cannot-make-change.

Editar via GitHub A ligação abre numa nova janela ou separador
Factor Exercism

Estás pronto para começar Troco?

Inscreve-te no Exercism para aprenderes e dominares Factor com 47 conceitos163 exercícios, e mentoria humana real, tudo grátis.