.. -- coding: utf-8 --

..  Copyright (C)  Coelho e Hitoshi
    Permission is granted to copy, distribute
    and/or modify this document under the terms of the GNU Free Documentation
    License, Version 1.3 or any later version published by the Free Software
    Foundation; with Invariant Sections being Forward, Prefaces, and
    Contributor List, no Front-Cover Texts, and no Back-Cover Texts.

..  shortname:: EP3
..  description:: exercício acha troco recursivo


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.

.. sourcecode:: python

    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]]
    >>>