PHP: считаем числа Армстронга

Что такое числа Армстронга, легко прочитать в Вики.

Придумать дельный алгоритм, не сводящийся к перебору, видимо, сложнее. Идея такого алгоритма есть вот здесь.

Если таки перебирать, да ещё и на заведомо медленном PHP, то видимых оптимизаций немного. Можно основной алгоритм оформить как цикл по разрядности числа, в котором вызывается функция check(), проверяющая условия Армстронга для всех чисел заданной разрядности.

Все однозначные числа являются числами Армстронга, для них отдельная проверка не нужна. Число известной разрядности $n можно преобразовать в массив цифр посредством функции sscanf с шаблоном "%1d%1d...%1d", где %1d повторено $n раз. Операцию возведения цифры в степень можно затабулировать, а не вычислять трудоёмкими функциями над вещественными числами.

У меня получилось время выполнения скрипта не более, чем над 4-значными числами ~1 сек., над 5-значными около 4 сек., над 6-значными уже примерно 45 сек. Дальше, конечно, будет экспоненциальный рост времени работы скрипта.

Ниже приводится полный листинг, поменяйте значение D в начале и смотрите вывод сами :)

<?php
 set_time_limit (3600);
 define("D", 5); // максимальное количество цифр числа

 function array_prod (&$array_a, $array_b) {
  // Перемножение массивов поэлементно
  $array_a = array_map (function($a,$b) {return $a*$b;}, $array_a, $array_b);
 }

 // Вернёт массив из n-значных чисел Армстронга
 function check ($n, $deg10, $degree){
  $result = array();
  $format = str_repeat ("%1d", $n);
  for ($k = $deg10[$n-1]; $k < $deg10[$n]-1; $k++) {
   $digits = sscanf($k, $format); //массив цифр числа
   $sum = 0;
   array_walk ($digits, function($d) use(&$sum, $degree) {
    $sum += $degree[$d];
   });
   if($sum == $k) $result[] = $k; 
  }
  return $result;
 }

 $time_start = microtime(true);
 $mult = 1;
 $deg10 = array(); 
 $deg10[] = $mult;
 for ($i=1; $i <= D; $i++) $deg10[] = ($mult *= 10);
 $digits = range(0,9);
 $degree = $digits;
 $armstrong[1] = $digits;
 for ($n = 2; $n <= D; $n++) {
  array_prod ($degree, $digits);
  $armstrong[] = check ($n, $deg10, $degree);
 }
 $time = microtime(true) - $time_start;
 print ('<br>Числа Армстронга:<pre>');
 var_dump ($armstrong);
 printf ("</pre><br>Время счёта = %.2f c", $time);
?>

07.03.2017, 23:30 [4466 просмотров]