首頁 >後端開發 >php教程 >利用php 求水仙花數的優化

利用php 求水仙花數的優化

jacklove
jacklove原創
2018-06-09 11:47:443254瀏覽

水仙花數是指一個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(&#39; &#39;, microtime());
    return (float)$usec + (float)$sec;
}
// 设定超时时间为3600秒
set_time_limit(3600);
// 记录开始运行时间
$start = getMicrotime();
// 执行求出3~7位的水仙花数
for($i=3; $i<=7; $i++){
    $result[$i] = implode(&#39;,&#39;, narcissistic($i));
}
// 记录运行结束时间
$end = getMicrotime();
// 输出运行时间
echo &#39;run time:&#39;.(float)($end - $start);
// 打印结果
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
print_r($result);
echo &#39;
'; ?>

執行結果:

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(&#39; &#39;, 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(&#39;,&#39;, narcissistic($i));
}
// 记录运行结束时间
$end = getMicrotime();
// 输出运行时间
echo &#39;run time:&#39;.(float)($end - $start);
// 打印结果
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
print_r($result);
echo &#39;
'; ?>

執行結果:

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來驗證身分證號碼

如何透過php 來取得YouTube影片資訊

#關於php unserialize 回傳false的解決方法

############## ########

以上是利用php 求水仙花數的優化的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn