Правильное направление - это динамическое программирование и алгоритм Дейкстры.
Надо просто завести массив на 105 элементов и по порядку, начиная с единицы, заполнить его минимально возможным количеством операций калькулятора (массив $steps). Наличие операции инкремента в калькуляторе даёт гарантию, что это возможно.
Кроме того, для каждого из чисел запоминаются также предыдущие числа (от одного до трёх), соответствующие одному шагу оптимального решения (массив $previous). Это позволяет полностью избавиться от перебора (с момента заполнения массивов сложность алгоритма равна количеству операций калькулятора).
В итоге удаётся:
- Определить минимальное количество операций калькулятора по пути к каждому числу.
- Найти число, требующее больше всего операций (77759 - 24 операции).
- Двигаясь по нулевым элементам массива previous, моментально получить один из оптимальных путей.
- Рекурсивным обходом массива previous максимально быстро определить все оптимальные способы, которыми можно получить данное число (на примере числа 96234).
Программа (на PHP):
function pre($i, $chain){
global $previous;
if($i==0){
print("<br>");
foreach($chain as $val) print(" $val");
return;
}
array_push($chain, $i);
$cnt = count($previous[$i]);
if(!$i) return;
for($c=0; $c < $cnt; $c++){
pre($previous[$i][$c], $chain);
}
}
$n = 96234;
$lim = 100000;
$steps = array();
$steps[1] = 0;
$previous[1]=array(0);
$max = 0;
for($i=2; $i<=$lim; $i++){
$i1=$i-1;
$steps[$i] = $steps[$i1]+1;
$previous[$i] = array($i1);
$i2 = $i>>1;
if(2*$i2 == $i){
if ($steps[$i2] < $steps[$i]-1){
$steps[$i] = $steps[$i2]+1;
$previous[$i] = array($i2);
}elseif($steps[$i2] == $steps[$i]-1){
array_push($previous[$i], $i2);
}
}
$i3 = (int)($i/3);
if(3*$i3 == $i) {
if ($steps[$i3] < $steps[$i]-1){
$steps[$i] = $steps[$i3]+1;
$previous[$i] = array($i3);
}elseif($steps[$i3] == $steps[$i]-1){
array_push($previous[$i], $i3);
}
}
if($steps[$i]>$max) $max = $steps[$i];
}
asort($steps);
var_dump(array_slice($steps, 99990, 99999, true));
printf("<br> steps[%d] = %d:   ", $pr=77759, $steps[$pr]);
while($pr>1) printf(" %d", $pr=$previous[$pr][0]);
print("<br>");
printf("<br> steps[%d] = %d:   ", $pr=99977, $steps[$pr]);
while($pr>1) printf(" %d", $pr=$previous[$pr][0]);
print("<br>");
printf("<br> steps[%d] = %d:   ", $pr=96234, $steps[$pr]);
while($pr>1) printf(" %d", $pr=$previous[$pr][0]);
print("<br>");
$chain = array();
pre($n, $chain);
Результаты:
array (size=10)
86399 => int 22
51407 => int 22
69119 => int 22
60911 => int 22
93311 => int 23
77758 => int 23
77757 => int 23
77755 => int 23
51839 => int 23
77759 => int 24
steps[77759] = 24: 77758 38879 38878 19439 19438 9719 9718 4859 4858 2429 2428 1214 607 606 303 101 100 99 33 11 10 9 3 1
steps[99977] = 19: 99976 49988 24994 24993 8331 2777 2776 1388 694 693 231 77 76 38 19 18 9 3 1
steps[96234] = 14: 48117 16039 16038 8019 2673 891 297 99 33 11 10 9 3 1
96234 48117 16039 16038 8019 2673 891 297 99 33 11 10 9 3 1
96234 48117 16039 16038 5346 2673 891 297 99 33 11 10 9 3 1
96234 48117 16039 16038 5346 1782 891 297 99 33 11 10 9 3 1
96234 48117 16039 16038 5346 1782 594 297 99 33 11 10 9 3 1
96234 48117 16039 16038 5346 1782 594 198 99 33 11 10 9 3 1
96234 48117 16039 16038 5346 1782 594 198 66 33 11 10 9 3 1
96234 48117 16039 16038 5346 1782 594 198 66 22 21 7 6 3 1
96234 48117 16039 16038 5346 1782 594 198 66 22 21 7 6 2 1
96234 48117 16039 16038 5346 1782 594 198 66 22 21 7 6 2 1
96234 48117 16039 16038 5346 1782 594 198 66 22 11 10 9 3 1
96234 32078 16039 16038 8019 2673 891 297 99 33 11 10 9 3 1
96234 32078 16039 16038 5346 2673 891 297 99 33 11 10 9 3 1
96234 32078 16039 16038 5346 1782 891 297 99 33 11 10 9 3 1
96234 32078 16039 16038 5346 1782 594 297 99 33 11 10 9 3 1
96234 32078 16039 16038 5346 1782 594 198 99 33 11 10 9 3 1
96234 32078 16039 16038 5346 1782 594 198 66 33 11 10 9 3 1
96234 32078 16039 16038 5346 1782 594 198 66 22 21 7 6 3 1
96234 32078 16039 16038 5346 1782 594 198 66 22 21 7 6 2 1
96234 32078 16039 16038 5346 1782 594 198 66 22 21 7 6 2 1
96234 32078 16039 16038 5346 1782 594 198 66 22 11 10 9 3 1
Суммарное время выполнения ~ 1 секунды.