水仙花数是指一个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; } // 获取当前microtime
function 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.230147838593
Array
(
[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; } // 获取当前microtime
function 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.354328155518
Array
(
[3] => 153,370,371,407
[4] => 1634,8208,9474
[5] => 54748,92727,93084
[6] => 548834
[7] => 1741725,4210818,9800817,9926315
)
结果比对,优化后的算法降低了42%的运行时间。