Moedas usadas
Montante formado
Mínimo possível

    Moedas (¢)

      Mais sobre o problema do troco

      Problema do troco

      Com alguns tipos de moedas, como se paga um montante exato com o menor número possível de moedas, e de quantas maneiras se pode fazê-lo? A resposta gulosa, a maior moeda primeiro, funciona com dinheiro real, mas falha com alguns conjuntos de moedas. Uma tabela que constrói cada montante a partir de montantes mais pequenos acerta sempre. Toque numa moeda da bandeja para a pôr no balcão, e toque numa moeda do balcão para a retirar. O medidor enche-se até ao montante: forme-o exatamente, com o menor número de moedas que conseguir. Mínimo de moedas mostra a melhor resposta, e Guloso mostra o que se obtém escolhendo sempre a maior moeda que cabe, o que nem sempre dá o mínimo. Altere as moedas (em cêntimos) e o montante no painel. A vista Tabela mostra como a programação dinâmica encontra o mínimo de moedas, ou conta o número de maneiras de formar o montante: prima Reproduzir para ver a tabela encher-se, ou Avançar e Recuar para ir um passo de cada vez, e arraste o controlo de passos para saltar para qualquer ponto. Cada moeda pode ser usada as vezes que quiser. Com a tabela selecionada, as setas avançam passo a passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e para o fim.

      Como funciona

      1. Toque nas moedas do tabuleiro para formar exatamente a quantia e veja o indicador encher-se em cêntimos.
      2. Tente usar o menor número de moedas e depois prima Mínimo de moedas ou Guloso para comparar.
      3. Abra a vista Tabela e prima Reproduzir para ver cada célula ler a quantia menor de que depende.

      Mínimo de moedas

      O montante 0 não precisa de moedas. Para cada montante maior, experimente cada moeda que não seja maior do que ele: o que sobra depois dessa moeda é um montante mais pequeno, já na tabela, por isso mais uma moeda dá um candidato. O candidato mais pequeno vai para a célula, e a moeda que o deu fica guardada na linha de baixo. Quando a tabela está cheia, as moedas são lidas de volta a partir do alvo: pegue na sua última moeda, vá para o montante que sobra e repita até 0.

      Número de maneiras

      Para contar combinações em vez de ordens, a tabela junta uma moeda por linha. Uma célula conta as maneiras de formar o seu montante com as moedas até à sua linha: as maneiras sem a moeda mais recente, que são a célula de cima, mais as maneiras que usam a moeda mais recente pelo menos uma vez, que são a célula esse número de colunas à esquerda na mesma linha. Como as moedas são juntadas numa ordem fixa, 1 + 2 e 2 + 1 são a mesma maneira e são contadas uma só vez.

      Perguntas frequentes

      Porque é que o método guloso falha?

      O algoritmo guloso escolhe sempre a maior moeda que cabe e nunca volta atrás. Com as moedas 1, 3 e 4 e um montante de 6, escolhe 4, depois 1 e 1: três moedas, quando bastariam duas de 3. Em sistemas de moedas como o euro ou o dólar americano, o guloso acaba por ser ótimo; esses sistemas chamam-se canónicos.

      Qual é a diferença entre contar maneiras e contar ordens?

      As maneiras tratam 1 + 2 e 2 + 1 como a mesma combinação; as ordens contam-nas separadamente. A aplicação conta maneiras, juntando as moedas uma linha de cada vez. Para contar ordens, percorrem-se os montantes e experimenta-se cada moeda para cada um.

      Qual é a rapidez do algoritmo do troco?

      As duas tabelas precisam de tantos passos como o número de tipos de moedas vezes o montante. Isso é rápido para montantes na ordem dos milhares, mas um montante pode ser um número enorme, por isso, medido pelo número de algarismos, o problema é NP-difícil em geral.

      E se um montante não se puder formar?

      A sua célula fica em ∞, por exemplo os montantes 1 e 3 com as moedas 2 e 5. No modo Número de maneiras, a sua contagem é simplesmente 0.

      Alguma coisa é enviada para algum lado?

      Não. Tudo é calculado no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.

      Pronto para experimentar?

      Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

      Ir para o editor