php中如何求水仙花数优化

php中如何求水仙花数优化2014-08-31水仙花数是指一个n位数（n>=3），它每个位上数字的n次幂之和等于它本身，n为它的位数。（例如：1^3+5^3+3^3 = 153）

水仙花数又称阿姆斯特朗数。

三位的水仙花数有4个：153，370，371，407

四位的水仙花数有3个：1634，8208，9474

五位的水仙花数有3个：54748，92727，93084

六位的水仙花数有1个：548834

七位的水仙花数有4个：1741725，4210818，9800817，9926315

八位的水仙花数有3个：24678050，24678051，88593477

.....

最大的水仙花数有39位（115132219018763992565095597973971522401），十进制自然数中的所有水仙花数共有88个。

php 求水仙花数

1.穷举法求水仙花数，求3~7位的水仙花数

<？php// 穷举求水仙花数function narcissistic（$n）{if（$n<3 || $n>39）{return false;}// 保存执行结果$result = array（）;$start = pow（10,$n-1）;$end = pow（10, $n）;for（$i=$start; $i<$end; $i++）{$total = 0;$nums = str_split（$i, 1）;foreach（$nums as $num）{$total += pow（$num, $n）;}if（$total==$i）{array_push（$result, $i）;}}return $result;}// 获取当前microtimefunction getMicrotime（）{list（$usec, $sec） = explode（" ", microtime（））;return （float）$usec + （float）$sec;}// 设定超时时间为3600秒set_time_limit（3600）;// 记录开始运行时间$start = getMicrotime（）;// 执行求出3~7位的水仙花数for（$i=3; $i<=7; $i++）{$result[$i] = implode（",", narcissistic（$i））;}// 记录运行结束时间$end = getMicrotime（）;// 输出运行时间echo "run time:".（float）（$end - $start）;// 打印结果echo "<pre>";print_r（$result）;echo "</pre>";？>

执行结果：

run time:82.230147838593Array（[3] => 153,370,371,407[4] => 1634,8208,9474[5] => 54748,92727,93084[6] => 548834[7] => 1741725,4210818,9800817,9926315）

2.优化算法求水仙花数，求3~7位的水仙花数

优化方法：为pow 创建0-9 N阶的对应表，减少计算次数

<？php// 优化求水仙花数function narcissistic（$n）{if（$n<3 || $n>39）{return false;}// 保存执行结果$result = array（）;// n阶pow对应表$powlist = getPow（$n）;$start = pow（10,$n-1）;$end = pow（10, $n）;for（$i=$start; $i<$end; $i++）{$total = 0;$nums = str_split（$i, 1）;foreach（$nums as $num）{$total += $powlist[$num];}if（$total==$i）{array_push（$result, $i）;}}return $result;}// 获取当前microtimefunction getMicrotime（）{list（$usec, $sec） = explode（" ", microtime（））;return （float）$usec + （float）$sec;}// 获取n阶pow对应表function getPow（$n）{$powlist = array（）;for（$i=0; $i<=9; $i++）{array_push（$powlist, pow（$i,$n））;}return $powlist;}// 设定超时时间为3600秒set_time_limit（3600）;// 记录开始运行时间$start = getMicrotime（）;// 执行求出3~7位的水仙花数for（$i=3; $i<=7; $i++）{$result[$i] = implode（",", narcissistic（$i））;}// 记录运行结束时间$end = getMicrotime（）;// 输出运行时间echo "run time:".（float）（$end - $start）;// 打印结果echo "<pre>";print_r（$result）;echo "</pre>";？>

执行结果：

run time:47.354328155518Array（[3] => 153,370,371,407[4] => 1634,8208,9474[5] => 54748,92727,93084[6] => 548834[7] => 1741725,4210818,9800817,9926315）

结果比对，优化后的算法减少了42%的执行时间。