【水仙数】Python水仙数を解く
1つのNビットの10進数の正の整数で、その各ビットの数字の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次の和はちょうどこの数そのものに等しい.
条件を満たす数字が1つだけでない場合は、条件を満たすすべての数字を小さいから大きいまで出力し、各数字が1行を占めます.この数字が大きいので、解法の時間的な実行可能性に注意してください.要求プログラムは3分以内に実行済みです.
chinaunixで見たように、週末には自分で非再帰的なアルゴリズムを実現し、Python言語で実現した.計算時間:
real 1m32.599s
user 1m32.290s
sys 0m0.060s
Pythonは時間の要求内に問題を解決できるようですね^^;
探索方式は非再帰的全配列アルゴリズムに類似しており,これも可能なすべての数値の組合せを列挙し,一つ一つ比較して判断する.(どんな数学の法則がもっと簡略化できるか分からない)
コードは次のとおりです.
結果:
hit 449177399146038697307
hit 128468643043731391252
cで実現する場合、再帰的な問題を処理する必要があります.結局long longは64 bitで、最大で表すことができる正の整数は18446744073709551615(10進数長は20)です.大きな整数演算ライブラリが必要になるか、gcc 4.6で新しく提供された__int128を使用する必要があるかもしれません.後日空いているときは、cで試してみてください.
例:
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次の和はちょうどこの数そのものに等しい.
条件を満たす数字が1つだけでない場合は、条件を満たすすべての数字を小さいから大きいまで出力し、各数字が1行を占めます.この数字が大きいので、解法の時間的な実行可能性に注意してください.要求プログラムは3分以内に実行済みです.
chinaunixで見たように、週末には自分で非再帰的なアルゴリズムを実現し、Python言語で実現した.計算時間:
real 1m32.599s
user 1m32.290s
sys 0m0.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は64 bitで、最大で表すことができる正の整数は18446744073709551615(10進数長は20)です.大きな整数演算ライブラリが必要になるか、gcc 4.6で新しく提供された__int128を使用する必要があるかもしれません.後日空いているときは、cで試してみてください.