Change-making algorithm - Less amount of possible coins

0

Given the Change-Making algorithm:

change(C1, C2, ...., Cr: valores de denominações de moedas, onde C1 > C2 > ... > Cr; n: inteiro positivo)


for i := 1 para r
     di := 0 {di conta a denominação das moedas Ci usadas}
     while n >= Ci
          di := di + 1 {adiciona uma moeda na denominação Ci}
          n := n - Ci
{di é o número de moedas na denominação Ci na troca for i = 1, 2, ...}

And the question:
Considering the algorithm to make the exchange and the American currency pattern ($ 0.25, $ 0.10, $ 0.05, and $ 0.01). Show that if we enter $ 0.12, then the algorithm will not produce an exchange using the smallest amount of possible currencies.

I would like to ask for help in understanding logic or where to start, as I am lost in this.

Sorry for the translation a little "rude" because I'm studying this in English and I do not know the correct terms in pt.

    
asked by anonymous 15.09.2015 / 22:48

0 answers