Baseado em uma resposta a uma questão que fiz no Yahoo! Respostas.

readme.md

Baseado em uma pergunta no Yahoo!Respostas. https://br.answers.yahoo.com/question/index?qid=20180319200053AAlky7Q

Já olhei várias respostas... https://br.answers.yahoo.com/question/index?qid=20070116122629AAfWmTw

Mas é uma duvida de Analise combinatória:

Imagina um sistema para gerar troco. Mas é diferente dos normais por ai.

Normalmente eles contam as cedulas e moedas que precisam entregar.

Ex: R$ 100,00 2x R$ 50 ou se tiver quantidade de notas (Ex caixa automático) 5x R$ 20,00 10x R$ 10,00

Mas vamos pensar menor:

Digamos que eu tenha que devolver 4,10.

Eu posso entregar:

02 R$ 2,00 + 01 R$ 0,10 02 R$ 2,00 + 02 R$ 0,05 02 R$ 2,00 + 10 R$ 0,01

04 R$ 1,00 + 01 R$ 0,10 04 R$ 1,00 + 02 R$ 0,05 04 R$ 1,00 + 10 R$ 0,01

...

16 R$ 0,25 + 01 R$ 0,10 16 R$ 0,25 + 02 R$ 0,05

...

41 R$ 0,10 410 R$ 0,01

Como posso calcular a soma de todas as possibilidades

Sendo que tenho R$ 100,00, R$ 50,00, R$ 20,00, R$ 10,00, R$ 5,00, R$ 2,00, R$ 1,00, R$ 0,50, R$ 0,25, R$ 0,10, R$ 0,05, R$ 0,01

--

Um usuário respondeu:

moedas[1..12] = {0.10, 0.05, 0.10, 0.25, 0.50, 1.00, 2.00, 5.00, 10.00, 20.00, 50.00, 100.00} valor = 4.10

FUNÇÃO modos(troco, maior_moeda) | SE(maior_moeda <= 1) | | RETORNE 1 | FIM | contador = 0 | ENQUANTO(troco >= 0) | | contador = contador + modos(troco, maior_moeda - 1) | | troco = troco -MOEDA(maior_moeda) | FIM | RETORNE contador

IMPRIMA modos(valor,12)

Programei em python e como resultado, tive: --------- modos = 46232 ---------

modos.js

var moedas = [0.01, 0.05, 0.10, 0.25, 0.50, 1.00, 2.00, 5.00, 10.00, 20.00, 50.00, 100.00];
var valor = 4.10 ;
function modos(troco,maior_moeda){
	if(maior_moeda < 0){
		return 1;
	}
	var contador = 0;
	while(troco >= 0 ){
		contador = contador + modos(troco, maior_moeda -1);
		troco = troco  - moedas[maior_moeda];
	}
	return contador;
}
console.log(modos(valor,12));