Алгоритм поиска чисел Армстронга

#алгоритм

Найти числа Армстронга меньше N можно несколькими способами. Я выбрал следующий -
создать матрицу, содержащую i строк (числа от 1 до 9) и j столбцов (степени от 1 до
N.length(), то есть длины числа) в каждой ячейке которой находится число i в степени
j, то есть например degreeMatrix[2][3] = 2^3 = 8

Собственно встает вопрос по созданию алгоритма перебора чисел и поиск среди найденных
подходящих чисел. 
Есть смысл искать только среди чисел которые не повторялись ранее - например от 1
до 9 - проверяются все, от 11 до 99 проверяются лишь 45 раз и только те, что идут друг
за другом с условием что каждое число не меньше предыдущего и не больше следующего
- 11, 12 .. 19, далее 22, 23 .. 29, далее 33, 34 .. 39 и таким образом до 99. С трех
и более значными числами ситуация аналогична. Таким образом можно избежать огромного
числа лишних проверок (для 2-ух значных почти в два раза уменьшается, для 3-х значных
количество проверок менее 200 и т.д.)

Соответственно нужно реализовать алгоритм с использованием данных из матрицы (назовем
ее проще М)

Для однозначных чисел все просто - 

М(1,1), М(2,1) .. М(9,1) степень равна 1

Для двузначных как раз таки начинаются проблемы - 

от 11 до 19 - М(1,2) + М(1,2), М(1,2) + М(2,2) .. М(1,2) + М(9,2) 

от 22 до 29 - М(2,2) + М(2,2), М(2,2) + М(3,2) .. М(2,2) + М(9,2) 

Требуется создать алгоритм суммирующий значения из матрицы в зависимости от длины
числа (длин = количесвто чисел и их степень) с учетом правильной последовательности
(каждое число не меньше предыдущего и не больше последующего, например 11, 129, 371 и т.д.)
    

Ответы

Ответ 1

UPD

Алгоритм не должен быть расточительным, поэтому от идеи с матрицами лучше отказаться.

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


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


Программа на языке PHP:

set_time_limit(3000);
define("D", 7); // максимальное количество цифр числа

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

// Поиск n - значных чисел Армстронга
function check($n, $deg10, $degree){
    $result = [];
    $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);
// Формирование массива степеней 10
$mult = 1;
$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 "
Числа Армстронга:";
var_dump($armstrong);
printf("Время счёта = %.3f c", $time);


Результаты:




Числа Армстронга:
array (size=8)
  1 => 
    array (size=10)
      0 => int 0
      1 => int 1
      2 => int 2
      3 => int 3
      4 => int 4
      5 => int 5
      6 => int 6
      7 => int 7
      8 => int 8
      9 => int 9
  2 => 
    array (size=0)
      empty
  3 => 
    array (size=4)
      0 => int 153
      1 => int 370
      2 => int 371
      3 => int 407
  4 => 
    array (size=3)
      0 => int 1634
      1 => int 8208
      2 => int 9474
  5 => 
    array (size=3)
      0 => int 54748
      1 => int 92727
      2 => int 93084
  6 => 
    array (size=1)
      0 => int 548834
  7 => 
    array (size=4)
      0 => int 1741725
      1 => int 4210818
      2 => int 9800817
      3 => int 9926315
  8 => 
    array (size=3)
      0 => int 24678050
      1 => int 24678051
      2 => int 88593477
Время счёта = 13942.224 c