高手求解 [复制链接]

153=1^3+5^3+3^3 ,371=3^3+7^3+1^3, 370=3^3+7^3+0^3, 407=4^3+0^3+7^3他们都是三位数且等于各位数字的三次幂之和,这种巧合不能不令人感到惊讶.更为称奇的是,竞然构造出其值等于各位数字四(五,六)次幂之和的四(五,六)位数:1634=1^4+6^4+3^4+4^4 54748=5^5+4^5+7^5+4^5+8^5 548834=5^6+4^6+8^6+8^6+3^6+4^6像这种其值等于各位数字的 n 次幂之和的 n 位数,称为 n 位 n 次幂回归数.简称为回归数,请输出10(20)位以内的回归数.(运算时间<5S).

一位回归数:1,2,3,4,5,6,7,8,9
二位回归数:不存在
三位回归数:153,370,371,407
四位回归数:1634,8208,9474
五位回归数:54748,92727,93084

当N较小时,程序不难,当N<6时,这个运算量一般都能完成.当N增大时,程序运算量极巨增大,运算时间就会很长,如何设计一个有效算法提高运算速度,在5S内能运算出的几位的回归数??

随手写了一个，的确超时严重……

测试结果：
Test 1 OK [0.00 secs] (n=1)
Test 2 OK [0.00 secs] (n=5)
Test 3 OK [0.60 secs] (n=10)
Test 4 OK [1.26 secs] (n=11)
Test 5 OK [2.56 secs] (n=12)
Test 6 OK [4.98 secs] (n=13)
Test 7 OK [9.42 secs] (n=14)
Test 8 OK [17.19 secs] (n=15)
Test 9 OK [30.49 secs] (n=16)
Test 10 OK [52.06 secs] (n=17)
Test 11 OK [87.22 secs] (n=18)
Test 12 OK [143.36 secs] (n=19)

说明：由于没有用高精度，我的程序最高支持19位（n＝19）吧。

我的输出（空表示没有）：
1-digit numbers: 0 1 2 3 4 5 6 7 8 9 2-digit numbers: 3-digit numbers: 370 407 153 371 4-digit numbers: 8208 1634 9474 5-digit numbers: 93084 92727 54748 6-digit numbers: 548834 7-digit numbers: 9800817 4210818 1741725 9926315 8-digit numbers: 24678050 24678051 88593477 9-digit numbers: 146511208 912985153 472335975 534494836 10-digit numbers: 4679307774 11-digit numbers: 32164049650 40028394225 42678290603 49388550606 32164049651 94204591914 44708635679 82693916578 12-digit numbers: 13-digit numbers: 14-digit numbers: 28116440335967 15-digit numbers: 16-digit numbers: 4338281769391370 4338281769391371 17-digit numbers: 35875699062250035 21897142587612075 35641594208964132 18-digit numbers: 19-digit numbers: 1517841543307505039 3289582984443187032 4929273885928088826 4498128791164624869

我的程序：
program hgs; var zhl:array[1..20] of shortint; cfl:array[0..9] of int64; n:shortint; procedure cf; var i,j:shortint; begin for i:= 1 to 9 do cfl<i>:=i; if n= 1 then exit; for i:= 1 to n-1 do for j:= 1 to 9 do cfl[j]:=cfl[j]*j; end; procedure pdhsc; var i:shortint; s:string; zh:array[0..19] of shortint; temp,max:qword; procedure qsort(low,high:integer); procedure swap(var a1,a2:shortint); var a3:shortint; begin a3:=a1; a1:=a2; a2:=a3; end; var i,j:shortint; begin if low>=high then exit; j:=low-1; for i:=low to high-1 do if zh<i><zh[high] then begin inc(j); swap(zh<i>,zh[j]); end; swap(zh[high],zh[j+1]); qsort(low,j); qsort(j+2,high); end; begin temp:=0; max:=1; for i:= 1 to n do max:=max*10; for i:= 1 to n do begin inc(temp,cfl[zhl<i>]); if temp > max then exit; end; str(temp,s); if length(s) <> n then exit; for i:= 1 to n do val(s<i>,zh<i>,zh[0]); qsort(1,n); for i:= 1 to n do if (zh<i> <> zhl<i>) then exit; write(temp,' '); end; function incr : boolean; var i,j:shortint; begin inc(zhl[n]); for i:= n downto 2 do begin if zhl<i> =10 then begin inc(zhl[i-1]); for j:= i to n do zhl[j]:=zhl[i-1]; end else break; end; if ((zhl[1]=10) and (zhl[n]=10)) then exit(false); exit(true); end; procedure main; var i:shortint; begin cf; for i:=1 to n-1 do zhl<i>:=0; repeat pdhsc; until incr()=false; end; begin for n:= 1 to 19 do begin writeln(n,'-digit numbers:'); main; writeln; end; end.

程序中所有的<>请替换为[]，论坛的问题……

测试环境：
Intel Pentium 4 1400MHz
256MB DDR 333
Windows XP SP2
Freepascal 2.0.2

说明：我的程序需要Freepascal编译……

csdn上的讨论，楼主可以去看看，网址：
http://community.csdn.net/Expert/topic/4734/4734515.xml?temp=.8288233

好东西————

不错~~

今天用C语言重新写了个，快了很多。

测试结果：
Test 1 OK [0.00 secs] (n=1)
Test 2 OK [0.00 secs] (n=5)
Test 3 OK [0.17 secs] (n=10)
Test 4 OK [0.36 secs] (n=11)
Test 5 OK [0.75 secs] (n=12)
Test 6 OK [1.50 secs] (n=13)
Test 7 OK [2.64 secs] (n=14)
Test 8 OK [4.70 secs] (n=15)
Test 9 OK [8.23 secs] (n=16)
Test 10 OK [13.90 secs] (n=17)
Test 11 OK [23.30 secs] (n=18)
Test 12 OK [38.00 secs] (n=19)

5秒内的回文数达到了15位！

测试环境：
Intel Pentium 4 1400MHz
256MB DDR 333
Windows XP SP2
DEV C++ 4.9.9.2

源代码：

很不错！顶！

这个~好像叫水仙花数or 阿姆斯特朗数吧~~

LZ的代码解释一下，看不大懂~