Exercício Programa 3: Câmbio Automático - Parte A

Descrição

O aeroporto internacional de UspIme, uma pequena nação no sudeste da América do Sul, contratou você para desenvolver o software da máquina de câmbio que será colocada em vários pontos do aeroporto. Essa máquina troca dólares americanos em virtuais imeanos (= moeda de UspIme).

Esse exercício é dividido em várias partes, a começar pela parte A. Na parte A, você deve escrever uma função recursiva que devolve todas as combinações de moedas (ou notas) que somam um determinado valor. A cada nova parte você vai escrever mais código para desenvolver o resto da máquina de câmbio.

Parte A: entrega até 27/08

Na parte A, você deve escrever apenas uma função recursiva que calcula todas as combinações de moedas (ou notas) que somam um determinado valor.

Objetivos

• Desenvolver um algoritmo recursivo

O que você deve fazer

Suponha que valores é uma lista de números inteiros positivos distintos representando valores de notas ou moedas e seja n um certo valor em dolares. Diremos em uma lista de números inteiros é um troco para n se todo elemento da lista está em valores e a soma de seus elementos é n. Por exemplo, se valores = [1,2,3] então [1,1,2] e [1,3] são trocos para n = 4.

Escreva uma função recursiva em Python que recebe um número inteiro n e uma lista valores de números inteiros e retorna uma lista com todos os trocos viáveis para n. Por exemplo, para n = 4 e valores = [1,2,3] a função deve retornar [[1,1,1,1], [1,1,2], [2,2], [1,3]].

A ordem dos elementos (conjuntos de moedas) em cada troco pode ser qualquer. A lista de trocos não deve conter repetições como [1,3] e [3,1] que representam o mesmo troco.

Você deve, como sempre, testar a sua função antes de entregá-la. Seguem abaixo os resultados para alguns testes possíveis.

Python 3.4.3 (default, Mar 26 2015, 22:07:01)
[GCC 4.9.2] on linux
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
>>> lista_trocos(4,[1,2,3])
[[1, 1, 1, 1], [2, 1, 1], [3, 1], [2, 2]]
>>>
>>> lista_trocos(0,[1,2,3])
[[]]
>>> lista_trocos(4,[5,6,7])
[]
>>> lista_trocos(50,[10,25])
[[10, 10, 10, 10, 10], [25, 25]]
>>> lista_trocos(10,[3,7,9])
[[7, 3]]
>>> lista_trocos(20,[3,7,9])
[[7, 7, 3, 3]]
>>> lista_trocos(30,[3,7,9])
[[3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [9, 3, 3, 3, 3, 3, 3, 3], [9, 9, 3, 3, 3, 3],
[7, 7, 7, 3, 3, 3], [9, 9, 9, 3], [9, 7, 7, 7]]
>>>