3

Найти числа Армстронга меньше 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 и т.д.)

2
  • Вопрос-то в чем? За вас код надо написать? 24 фев 2016 в 9:15
  • Нет, ни в коем случае. Меня интересует алгоритм или хотя бы подсказка без чего тут не обойтись, например без рекурсии.
    – abbath0767
    24 фев 2016 в 9:25

1 ответ 1

4

UPD

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

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

  1. Все однозначные числа являются числами Армстронга, и для них проверка не нужна.
  2. Число известной разрядности можно преобразовать в массив цифр посредством процедуры sscanf() с шаблоном вида "%1d%1d...%1d".
  3. Операцию возведения цифры в степень можно затабулировать.
  4. Вместо цикла 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 "<br>Числа Армстронга:";
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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.