Use php to optimize the number of daffodils

The narcissus number refers to an n-digit number (n>=3). The sum of the n-th power of the numbers in each digit is equal to itself, and n is its number of digits. (For example: 1^3 5^3 3^3 = 153)

The Narcissus number is also called Armstrong’s number.

There are 4 narcissus numbers with three digits: 153, 370, 371, 407

There are 3 narcissus numbers with four digits : 1634, 8208, 9474

There are three five-digit narcissus numbers: 54748, 92727, 93084

Six-digit narcissus numbers There is one number: 548834

The seven-digit daffodil number has four: 1741725, 4210818, 9800817, 9926315

The eight-digit number There are three daffodil numbers: 24678050, 24678051, 88593477

....

The largest daffodil number has 39 digits ( 115132219018763992565095597973971522401), there are 88 daffodil numbers in the decimal natural numbers.

php Find the number of daffodils

1. Find the number of daffodils by exhaustive method, find 3 ~7-digit narcissus number

<?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;

'; ?>

Execution result:

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. Optimization algorithm Narcissus number, find the narcissus number between 3 and 7 digits

Optimization method: Create a 0-9 N-order correspondence table for pow to reduce the number of calculations

<?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;

'; ?>

Execution results:

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
)

Comparing the results, the optimized algorithm reduced the execution time by 42%.

This article explains the use of PHP to optimize the number of daffodils. For more related content, please pay attention to the PHP Chinese website.

Related recommendations:

How to verify ID number through php

How to get YouTube video information through php

##About the solution to php unserialize returning false

The above is the detailed content of Use php to optimize the number of daffodils. For more information, please follow other related articles on the PHP Chinese website!