Problema do troco

[Danilo Gonçalves Vicente]

Implementei o problema do troco em C++. Acho que ficou bom !

#include <iostream>

using namespace std;

int numeroMoedas(double troco,int n,double *moedas){

int solucao[n-1];

double soma = 0.0;

solucao[n-1] = 0;//caso base

for(int i = n - 2;i >= 0;i--){

if(soma + moedas >= troco)//se a soma total mais o valor da moeda for maior que o troco

solucao = solucao[i+1];//solução é a anterior do array

else {

bool repetiu = false;//vê se repetiu uma mesma moeda

while(soma + moedas < troco){ //enquanto a soma mais a moeda respectiva for menor que o troco

if(!repetiu)//se não repetiu

solucao = solucao[i+1] + 1;//soma a solução anterior + 1

else

solucao = solucao + 1; //soma a solucao atual + 1

soma = soma + moedas;//incrementa a soma

repetiu = true;//moeda repetiu

}

}

}

return solucao[0];//quantidade de moedas mínima

}

int main(){

int n = 12;

double troco = 3149.32;

double moedas[12] = {0.01,0.05,0.10,0.25,0.50,1.00,2.00,5.00,10.00,20.00,50.00,100.00};

int r = numeroMoedas(troco,n,moedas);

cout << r << endl;

system("pause");

return 0;

}