水仙花數是指一個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 class="brush:php;toolbar:false">'; print_r($result); echo ''; ?>
執行結果:
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 class="brush:php;toolbar:false">'; print_r($result); echo ''; ?>
執行結果:
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%的執行時間。
本文解釋了利用php 來求水仙花數的最佳化,更多相關內容請關注php中文網。
相關推薦:
#關於php unserialize 回傳false的解決方法
以上是利用php 求水仙花數的優化的詳細內容。更多資訊請關注PHP中文網其他相關文章!