【水仙花数】Python求解水仙花数

renheshi

　　

　　一个N位的十进制正整数，如果它的每个位上的数字的N次方的和等于这个数本身，则称其为花朵数。
　　例如：
　　当N=3时，153就满足条件，因为 1^3 + 5^3 + 3^3 = 153，这样的数字也被称为水仙花数（其中，“^”表示乘方，5^3表示5的3次方，也就是立方）。
　　当N=4时，1634满足条件，因为 1^4 + 6^4 + 3^4 + 4^4 = 1634。
　　当N=5时，92727满足条件。
　　实际上，对N的每个取值，可能有多个数字满足条件。
　　程序的任务是：求N=21时，所有满足条件的花朵数。注意：这个整数有21位，它的各个位数字的21次方之和正好等于这个数本身。
　　如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。因为这个数字很大，请注意解法时间上的可行性。要求程序在3分钟内运行完毕。
　　在chinaunix上看到的，周末自己实现了一个非递归的算法，采用Python语言实现。计算时间为：
　　real1m32.599s
　　user1m32.290s
　　sys0m0.060s
　　看来Python还能在时间要求内解决问题，^_^
　　搜索方式类似于非递归全排列算法，这个也是枚举了所有可能出现的数字组合，并一一比较判断。（不知道有是否什么数学规律可以再简化）
　　代码如下：
　　


#!/usr/bin/python
def get_flower(n, ofile):
D_pow=[pow(i,n) for i in range(0,10)]
V_min=1*pow(10,n-1)
V_max=sum((9*pow(10,x) for x in range(0,n)))
T_count=0
print D_pow, V_max, V_min
nums=[1]+[0]*(n-1)
print 'Start:', nums
idx=n-1
tmp_l=[0]*10
while True:
nums[idx]+=1
if nums[idx]<10:
j=idx+1
while j<n:
nums[j]=nums[idx] # reset
j+=1
v=sum((D_pow[x] for x in nums))
if v<=V_max and v>=V_min:
T_count+=1
#test if is flower
#print 'do test:', ''.join(map(str,nums))
k=0
while k<10:
tmp_l[k]=0
k+=1
N=0
for k in nums:
tmp_l[k]+=1
N+=1
while N>0:
p=v%10
if tmp_l[p]>0:
tmp_l[p]-=1
N-=1
else:
break
v/=10
if N==0:
print >>ofile, 'hit', sum((D_pow[x] for x in nums))
idx=n-1
elif idx==0:
print 'done'
break
else:
idx-=1
print 't_count', T_count
if __name__ == '__main__':
with file('./f.txt', 'wb') as o:
get_flower(21, o)
#get_flower(3, o)
 　　结果为：
　　hit 449177399146038697307
　　hit 128468643043731391252
　　如果用c来实现的话，会需要处理递归问题，毕竟long long是64bit，最大能表示的正整数是18446744073709551615（十进制长度为20）。可能需要一个大整数运算库，或者使用gcc4.6新提供的__int128。改天有空的时候，再用c来尝试下。