Python算不定位数的水仙花数解决方法

Python算不定位数的水仙花数
算6位数的水仙花数，用了6个for循环，如果是7位或以上的呢，怎么减少for循环的使用啊，听说可以用递归？有没有大侠帮忙看看

t1=time()
def main():
    n=6
    for a in xrange(1,10):
        for b in xrange(10):
            for c in xrange(10):
                for d in xrange(10):
                    for e in xrange(10):
                        for f in xrange(10):                  
                            num=100000*a+10000*b+1000*c+100*d+10*e+f
                            if num==a**n+b**n+c**n+d**n+e**n+f**n:
                                    print num
main()
print time()-t1

python 递归 算法 水仙花数
[解决办法]
不要用循环,直接找到n位最大与最小的数,挨着判断一下就行

def cmp_nar(n):
    ''' n is the number of digits '''
    min_num = 10**(n-1)
    max_num = 10**n
    result = []
    for num in range(min_num,max_num):
        if num==sum([int(x)**n for x in str(num)]):
            result.append(num)
    return result

# test 3-digits
print cmp_nar(3)

[解决办法]
分为两步：1. 生成所有的组合（用递归）和 2. 检测这些组合。

walker4是一个第一步，test_walker是第二步。

In [422]: def walker4(n, power_table):
     ...:     if n == 1:
     ...:         for d in range(1, 10):
     ...:             yield d, power_table[d]
     ...:     else:
     ...:         for k, s in walker4(n-1, power_table):
     ...:             for d in range(1,10):
     ...:                 yield k*10 + d, s + power_table[d]

In [423]: def test_walker(n, walker):
     ...:     power_table = [pow(d, n) for d in range(10)]
     ...:     return [k for k, v in walker(n, power_table) if k == v]

In [424]: test_walker(6, walker4)
Out[424]: [548834]

In [425]: test_walker(7, walker4)
Out[425]: [1741725, 9926315]

[解决办法]
sum不用每次都计算，只需要加1就可以了。

n次方也可以在每层的循环中保持临时结果，也可以用hash 就可以不用计算n次方了。

我比较喜欢动态生成代码的方式。还是循环而不是递归。
[解决办法]
这种递归最适合装饰器内存优化了，速度快百倍
[解决办法]

引用:

谢啦。速度很快，不过这段代码会漏解，7位的水仙花数算出来只有两个，实际上一共四个
[1741725, 4210818, 9800817, 9926315]

抱歉没仔细看你的代码，只看了for a in range(1,10)就跳到循环体内了,以为不许0出现。

要找所有的7位数的话，walker4中改一个地方就行了：

In [422]: def walker4(n, power_table):
     ...:     if n == 1:
     ...:         for d in range(1, 10):
     ...:             yield d, power_table[d] 
 
     ...:     else:
     ...:         for k, s in walker4(n-1, power_table):
     ...:             for d in range(10):  # <== 改这儿
     ...:                 yield k*10 + d, s + power_table[d]

[解决办法]
https://bitbucket.org/GSmith/narcissistic-numbers/src/21a4ed879f078639a6323f07af310a04165e6a83/narcissisticnumbers.py?at=default

用这个，很快！
[解决办法]

引用:

https://bitbucket.org/GSmith/narcissistic-numbers/src/21a4ed879f078639a6323f07af310a04165e6a83/narcissisticnumbers.py?at=default

用这个，很快！

原理介绍 http://gsmith.co/narcissistic-numbers/

速度：
 2 -    0.000109593218562
 3 -    0.000959215561797
 4 -     0.00176118867957
 5 -     0.00393326029562
 6 -     0.00963137459585
 7 -       0.023165220757
 8 -      0.0463923855072
 9 -      0.0949920297507
10 -       0.189894992103
11 -       0.354495209603
12 -       0.638352641655
13 -        1.07140749581
14 -        1.82483265042
15 -        2.96213499319
16 -        4.75087225573
17 -         7.4580355104
18 -        11.5109950588
19 -         17.431152917
[解决办法]

引用:

分为两步：1. 生成所有的组合（用递归）和 2. 检测这些组合。

walker4是一个第一步，test_walker是第二步。

In [422]: def walker4(n, power_table):
     ...:     if n == 1:
     ...:         for d in range(1, 10):
     ...:             yield d, power_table[d]
     ...:     else:
     ...:         for k, s in walker4(n-1, power_table):
     ...:             for d in range(1,10):
     ...:                 yield k*10 + d, s + power_table[d]

In [423]: def test_walker(n, walker):
     ...:     power_table = [pow(d, n) for d in range(10)]
     ...:     return [k for k, v in walker(n, power_table) if k == v]

In [424]: test_walker(6, walker4)
Out[424]: [548834]

In [425]: test_walker(7, walker4)
Out[425]: [1741725, 9926315]

改写了一下，效率差不多

def walker4(n, power_table):
    if n == 1:
        for d in range(1, 10):
            yield  power_table[d]
    else:
        for s in walker4(n-1, power_table):
            for d in range(10):
                yield s + power_table[d]
def nar(n):
    walker=walker4(n, [d**n for d in range(10)]) 
    return [i+10**(n-1) for i,j in enumerate(walker) if i+10**(n-1)==j]

print nar(6)

[解决办法]

def nar(n):
    powLs=[i**n for i in range(0,9+1)]
    t=[i**n for i in range(1,9+1)]
    for i in range(n-1):
        t=[s+powLs[d] for s in t for d in range(0,9+1)]
    c=10**(n-1) 
    return [i+c for i,j in enumerate(t) if i+c==j] 
 
print nar(6)

非递归版本，enumerate 比 zip(xrange(10**(n-1), 10**n-1)稍快
不知道这个能否用yield加速
[解决办法]

引用:

改写了一下，效率差不多

def walker4(n, power_table):
    if n == 1:
        for d in range(1, 10):
            yield  power_table[d]
    else:
        for s in walker4(n-1, power_table):
            for d in range(10):
                yield s + power_table[d]
def nar(n):
    walker=walker4(n, [d**n for d in range(10)]) 
    return [i+10**(n-1) for i,j in enumerate(walker) if i+10**(n-1)==j]

print nar(6)

你这样改引入了一个隐含的假设：walker产生的幂数和是按照其对应的数的从小到大的次序排列的。
[解决办法]

引用:

def nar(n):
    powLs=[i**n for i in range(0,9+1)]
    t=[i**n for i in range(1,9+1)]
    for i in range(n-1):
        t=[s+powLs[d] for s in t for d in range(0,9+1)]
    c=10**(n-1) 
    return [i+c for i,j in enumerate(t) if i+c==j]
print nar(6)

非递归版本，enumerate 比 zip(xrange(10**(n-1), 10**n-1)稍快
不知道这个能否用yield加速

可以用yield减速:) 把t从方括号(list)改成圆括号(generater)，速度稍微差一点，但占用的内存大大减少。在我的电脑上，用list的话，n=8就算不了了。
[解决办法]
神奇的yield...
[解决办法]

引用:

sum不用每次都计算，只需要加1就可以了。

n次方也可以在每层的循环中保持临时结果，也可以用hash 就可以不用计算n次方了。

我比较喜欢动态生成代码的方式。还是循环而不是递归。

同问，用Python如何动态生成代码，是“元编程”吗？

查看更多 下一篇