Не получается решить задачу на программирование: калькулятор

Пытаюсь решить задачу условие, которой приведено ниже.
Проблема в том что на больших числах моя программа выдает какой-то совершенно адски
результат. К примеру для числа 96234 программа выдает такую простыню чисел http://pastebin.com/8H5SvPK
(сравните с тем результатом, который приведен в условии). В принципе я понимаю почему так происходит, но другой идеи для решения данной задачи у меня нет. Подскажите как тут грамотно решить эту задачу.

Условие задачи:

У вас есть примитивный калькулятор, 
который умеет выполнять всего три операции с текущим числом x: 
заменить x на 2x, 3x или x+1. 
По данному целому числу 1≤n≤10^5 определите минимальное число операций k, 
необходимое, чтобы получить n из 1. 
Выведите k и последовательность промежуточных чисел.

Sample Input 1:
1
Sample Output 1:
0
1 

Sample Input 2:
5
Sample Output 2:
3
1 2 4 5 

Sample Input 3:
96234
Sample Output 3:
14
1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234 


Мое решение:

#include 
#include 

using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;

    int i = 1;
    vector m;
    m.push_back(i);
    while (i != n) {
        if (i * 3 <= n) {
            i *= 3;
        } else if (i * 2 <= n) {
            i *= 2;
        } else {
            i++;
        }
        m.push_back(i);
    }

    cout << m.size() - 1 << endl;
    for (int i = 0; i < m.size(); i++) cout << m[i] << " ";

    return 0;
}

    

Ответы

Ответ 1

Напишу свое решение, которое, по-моему, намного проще понять, чем уже опубликованные (я, например, не понимаю, почему они правильные).

Алгоритм такой: заводим список, в котором в i-ой позиции будем хранить минимально
число шагов, известное на данный момент, за которое можно попасть в N. В начале на
будет известно только то, что в N-ой позиции стоит 0. Затем начинаем бежать по списк
из конца в начало. На каждом шаге проверяем, из каких позиций мы можем попасть в текущую, и для этих позиций обновляем расстояние, если оно лучше, чем уже посчитанное ранее. К моменту когда мы прийдем в i-ый элемент, там будет записано минимальное расстояние, т.к. мы перебрали все варианты. Код такой:

#include 
#include 
#include 

int main() {
  int N;
  std::cin >> N;
  std::vector steps(N + 1, INT_MAX);
  steps[N] = 0;
  std::vector next_num(N + 1, -1);

  for (int i = N; i > 1; --i) {
    int s = steps[i] + 1;
    // 3 * x
    if (!(i % 3) && steps[i / 3] > s) {
      steps[i / 3] = s;
      next_num[i / 3] = i;
    }
    // 2 * x
    if (!(i % 2) && steps[i / 2] > s) {
      steps[i / 2] = s;
      next_num[i / 2] = i;
    }
    // x + 1
    if (steps[i - 1] > s) {
      steps[i - 1] = s;
      next_num[i - 1] = i;
    }
  }

  std::cout << steps[1] << std::endl;
  for (int i = 1; i != -1; i = next_num[i])
    std::cout << i << ' ';
  std::cout << std::endl;
}


Сложность алгоритма -- линейная. 

Результаты на тестах:

http://ideone.com/cuHyDP

 stdin
1
 stdout
0
1 


http://ideone.com/Ttku2H

 stdin
5
 stdout
3
1 3 4 5 


http://ideone.com/G5yg1I

 stdin
96234
 stdout
14
1 3 9 10 11 33 99 297 891 2673 8019 16038 16039 48117 96234


Ответ 2

У меня получилась другая последовательность чисел, но количество операций 14:

    long num = 96234;
    long x = num;
    int k = 0;

    while(x > 1)
    {
        if (x % 3 == 0)
        {
            x = x / 3;
            k++;
        }
        else if (x % 2 == 0)
        {
            if ((x - 1) % 3 == 0 && x % 4 != 0)
            {
                x--;
                k++;
                continue;
            }
            x = x / 2;
            k++;
        }
        else
        {
            x--;
            k++;
        }
    }


Последовательность чисел:
1 2 6 7 21 22 66 198 594 1782 5346 16038 16039 32078 96234


Ответ 3

Итерационный алгоритм. Название говорит само за себя, алгоритм пытается перебрать все возможные варианты. По этой причине может работать долго.
Для ускорения работы глубина рекурсии ограничена числом, выдаваемым алгоритмом Елены Обломовой

#include 
#include 
#include 


using namespace std;

int *VAR[100];
int LENS[100];
int IM[100];
int MAX_ITER;

int probe(int i,int iter)
{
 iter++; if(iter>MAX_ITER) return 10000;
 int j[3];
 int ret[3]; int m;
 if(i<=1) return 0;
 ret[0]=ret[1]=ret[2]=10000;
 j[2]=i-1; ret[2]=probe(j[2],iter);
 if(i%2==0) {j[1]=i/2; ret[1]=probe(j[1],iter);}
 if(i%3==0) {j[0]=i/3; ret[0]=probe(j[0],iter);}
 if(ret[0]=10000) return ret[m]+1;
 if(m) ret[m]=probe(j[m],iter);
 IM[iter-1]=j[m];
 ret[m]++;
 return ret[m];
}

int ElenaOblomovaAlg(int num)
{
 int x=num;
 int k=0;
 while(x > 1)
  {
   if (x % 3 == 0)  { x=x/3; k++; }
   else if (x % 2 == 0)
    {
     if((x-1)%3==0 && x%4 != 0) { x--; k++; continue; }
     x=x/2; k++;
    }
   else { x--; k++; }
  }
 return k;
}

int main(int argc, const char * argv[]) {
    int n,i;
    int o,j=0;
    memset(VAR,0,sizeof(int *)*100);
    memset(LENS,0,sizeof(int)*100);
    cin >> n;
    MAX_ITER=ElenaOblomovaAlg(n)+1;
    cout << "ElenaOblomova algorithm return " << MAX_ITER-1 << "\n";
    i=probe(n,0);
    if(i>1000) { i=MAX_ITER; cout << "Error recursion alg !!!\n"; }
    cout << "\ncount=" << i << "\n";
    i--;
    for (; i>=0; i--) cout << IM[i] << " ";
    cout << n;
    return 0;
}


Дает всегда оптимальное разложение, но его самого есть куда оптимизировать. Например разложение числа 99997 полным перебором требует порядка 1.6 миллиарда тестов.


Ответ 4

По вашему алгоритму так и будет.. все правильно получается...Большая портянка чисел. Но на самом деле алгоритм другой должен быть:

В обратную сторону - берем исходное число. Делим на 3. Если есть остаток - не учитываем
а вместо этого делим на 2, если остаток опять будет от деления, значит вычитаем 1..... повторяем. пока не дойдем до 1.


Ответ 5

Правильное направление - это динамическое программирование и алгоритм Дейкстры.
Надо просто завести массив на 105 элементов и по порядку, начиная с единицы, заполнит
его минимально возможным количеством операций калькулятора (массив $steps). Наличие операции инкремента в калькуляторе даёт гарантию, что это возможно.

Кроме того, для каждого из чисел запоминаются также предыдущие числа (от одного д
трёх), соответствующие одному шагу оптимального решения (массив $previous). Это позволяет полностью избавиться от перебора (с момента заполнения массивов сложность алгоритма равна количеству операций калькулятора).
В итоге удаётся:


Определить минимальное количество операций калькулятора по пути к каждому числу.
Найти число, требующее больше всего операций (77759 - 24 операции).
Двигаясь по нулевым элементам массива previous, моментально получить один из оптимальных путей.
Рекурсивным обходом массива previous максимально быстро определить все оптимальные способы, которыми можно получить данное число (на примере числа 96234).


Программа (на PHP):

function pre($i, $chain){
    global $previous;
    if($i==0){
        print("
");
        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("
 steps[%d] = %d:   ", $pr=77759, $steps[$pr]);
while($pr>1) printf(" %d", $pr=$previous[$pr][0]);
print("
");

printf("
 steps[%d] = %d:   ", $pr=99977, $steps[$pr]);
while($pr>1) printf(" %d", $pr=$previous[$pr][0]);
print("
");

printf("
 steps[%d] = %d:   ", $pr=96234, $steps[$pr]);
while($pr>1) printf(" %d", $pr=$previous[$pr][0]);
print("
");

$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 242
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 секунды.