sxslex/python — Issue #1: decompoe.py
Author: sxslex
Created: 2012-02-09 10:42:31+00:00
State: open

#Pessoal como ideia do Cássio estarei postando alguns desafios para que
#possamos resolvê-los em grupo assim iremos aperfeiçoando nossa
#linguagem python.
#
#1 - Faça um programa recursivo para gerar a decomposição de um número
#inteiro positivo na soma de todos os
#possíveis fatores como mostrado a seguir. Por exemplo, para n = 5,
#temos:
#Variavel para guardar resultados de chamadas da funcao para reaproveitalos
#by SleX

cache = {}
def decompoe(num):
def _decompoe(num,resp=[]):
global cache
#verifica se ja tenho a lista de decomposicao do numero*
if(cache.has_key(num)): return cache[num]
#adiciona o proprio numero na lista de resultado*
resp.append(num.__str__())
#loop todos os numero do 1 ate o numero a decompor*
for x in xrange(1,num):
nus = num-x
#adiciona a lista de resultado a lsita de resultado dadecomposicao
#do numero menos o valor do loop mas adicionando a este valor o
#numero passando anterior*
resp.extend([str(s)+' + '+str(num-nus) for s in _decompoe(nus,[])])
#salva e cache o resultado da decomposicao deste numero*
cache[num] = resp
return resp
resp =_decompoe(num)
#ordena o resultado*
resp.sort()
#inverte a ordenacao*
resp.reverse()
return resp

if(__name__ == '__main__'):
print decompoe(1)
print decompoe(2)
print decompoe(3)
print decompoe(4)
print decompoe(5)