当前位置:Gxlcms > PHP教程 > 利用php来求水仙花数的优化

利用php来求水仙花数的优化

时间:2021-07-01 10:21:17 帮助过:18人阅读

水仙花数是指一个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%的执行时间。

本文讲解了利用php 来求水仙花数的优化,更多相关内容请关注Gxl网。

相关推荐:

如何通过php来验证身份证号码

如何通过php 来获取YouTube视频信息

关于php unserialize 返回false的解决方法

以上就是利用php 来求水仙花数的优化的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行