Минимум шагов к одному

Question

Заявление о проблемах:

На положительное целое число вы можете выполнить любой из следующих трех шагов.

1. Вычесть 1 из него. (n = n - 1)
2. Если его делящийся на 2, разделите на 2. (если n% 2 == 0, то n = n/2)
3. Если его делится на 3, разделите на 3. (если n% 3 == 0, то n = n/3).

Теперь вопрос, учитывая положительное целое число п, найти минимальное количество шагов, которые принимает п 1

например:

1. При п = 1, выход: 0
2. При п = 4, выход: 2 (4/2 = 2/2 = 1)
3. При п = 7, выход: 3 (7 -1 = 6/3 = 2/2 = 1)

Я знаю решение, использующее динамическое программирование и имеющее целочисленный массив. вот код.

public int bottomup(int n) { 
      //here i am defining an integer array 
      //Exception is thrown here, if the n values is high. 
      public int[] bu = new int[n+1]; 
      bu[0] = 0; 
      bu[1] = 0; 
      for(int i=2;i<=n;i++) { 
        int r = 1+bu[i-1]; 
        if(i%2 == 0) r = Math.min(r,1+bu[i/2]); 
        if(i%3 == 0) r = Math.min(r,1+bu[i/3]); 
        bu[i] = r; 
      } 
      return bu[n]; 
    } 

Но я хочу, чтобы решить эту проблему с помощью менее space.This решение бросает OutOfMemoryError в Java, если п = 100000000.I не хочет, чтобы увеличить мой ворох space.Does кто имеет решение, используя меньше места?

Обратите внимание, что эта проблема не может быть решена с использованием жадного алгоритма. Использование одного цикла while и проверка на делимое на 3 и делимое на 2 не работает. Вам нужно использовать динамическое программирование.please, если у любого есть решение, использующее меньшее пространство.

например:

при п = 10 жадным алгоритмом 10/2 = 5 -1 = 4/2 = 2/2 = 1, который занимает 4 steps.where как решение должно быть 10-1 = 9/3 = 3/3 = 1, 3 шага.

Я даже попробовал решение по опрокидыванию.

public int[] td = null; 
    public int topdown(int n) { 
      if(n <= 1) return 0; 
      int r = 1+topdown(n-1); 
      if(td[n] == 0) { 
        if(n%2 == 0) r = Math.min(r,1+topdown(n/2)); 
        if(n%3 == 0) r = Math.min(r,1+topdown(n/3)); 
        td[n] = r; 
      } 
      return td[n]; 
    } 

Ошибка при n = 10000.

Answer 1

Идея состоит в том, что на любой итерации вам нужны значения только для r/3 по номеру r. Таким образом, вы можете отказаться от 1/3rd массива.

Я не знаком с Java, но с C++ вы можете использовать double ended queue (deque):

Вы продолжаете добавлять к деку со спины.
Когда i = 6, вам не нужны bu[0] и bu[1]. Таким образом, вы выталкиваете два элемента из передней части очереди.

Случайный доступ [ ] поддерживается контейнером deque.

EDIT: Кроме того, как предложено в комментариях, вы должны изменить тип данных для меньшего размера одного, так как максимальное число шагов должно быть порядка ((log N) to base 2)

EDIT2: Как Dukeling отметил, что, кажется, что в Java нет готовой хорошо подходящей реализации для deque, которая не будет компрометировать по сложности времени. Вы можете подумать о том, чтобы реализовать его по-своему, как это делает C++ (я слышал, что он реализован как вектор векторов с малым размером внутренних векторов по сравнению с общим количеством элементов).

Answer 2

ОБНОВЛЕНИЕ: здесь обновленный код, который я фактически протестировал несколько, и я верю, что приходит к тем же ответам для n от 1 до 100000. Я оставляю исходный ответ ниже для справки. Недостатком было «умное» использование MAX_INT. Я забыл, что будут случаи, когда я пропустил возможность -1, но число также не будет делиться на 2 или 3. Это решает, возвращая значение null, чтобы означать «этот путь бессмыслен для дальнейшего изучения».

public static int steps(int n) { 
    return steps(n, 0); 
} 
private static Integer steps(int n, int consecutiveMinusOnes) { 
    if (n <= 1) { 
     return 0; 
    } 
    Integer minSteps = null; 
    if (consecutiveMinusOnes < 2) { 
     Integer subOne = steps(n - 1, consecutiveMinusOnes + 1); 
     if (subOne != null) { 
      minSteps = 1 + subOne; 
     } 
    } 
    if (n % 2 == 0) { 
     Integer div2 = steps(n/2, 0); 
     if (div2 != null) { 
      if (minSteps == null) { 
       minSteps = div2 + 1; 
      } else { 
       minSteps = Math.min(minSteps, 1 + div2); 
      } 
     } 
    } 
    if (n % 3 == 0) { 
     Integer div3 = steps(n/3, 0); 
     if (div3 != null) { 
      if (minSteps == null) { 
       minSteps = div3 + 1; 
      } else { 
       minSteps = Math.min(minSteps, 1 + div3); 
      } 
     } 
    } 
    return minSteps; 
} 

Я считаю, что это может сработать, но я этого не доказал. Этот алгоритм основан на идее, что единственная причина для вычитания одной из них заключается в том, чтобы приблизить вас к числу, делящемуся на 2 или 3. По этой причине вам действительно не нужно применять шаг вычитания на один более двух раз последовательно, потому что если k% 3 == 2, то k - 2% 3 == 0, и вы можете разделить на три. Вычитание еще раз потребует усилий (вы также пройдете хотя бы на один четный номер, так что лучшая разница с двухступенчатой ​​возможностью появится). Это означает, что сверху вниз, рекурсивный подход, и вы можете смешать в некотором запоминании, если вы хотите:

public static int steps(n) { 
    return steps(n, 0); 
} 
private static int steps(int n, int consecutiveMinusOnes) { 
    if (n <= 1) { 
     return 0; 
    } 
    int minSteps = Integer.MAX_VALUE; 
    if (consecutiveMinusOnes < 2) { 
     minSteps = 1 + steps(n - 1, consecutiveMinusOnes + 1); 
    } 
    if (n % 2 == 0) { 
     minSteps = Math.min(minSteps, 1 + steps(n/2, 0)); 
    } 
    if (n % 3 == 0) { 
     minSteps = Math.min(minSteps, 1 + steps(n/3, 0)); 
    } 
    return minSteps; 
} 

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

Answer 3

Это работает :)

import java.util.Scanner; 
public class MinimumStepToOne { 

public static void main(String[] args){ 
    Scanner sscan = new Scanner(System.in); 
    System.out.print("Give a no:" + " "); 

    int n = sscan.nextInt(); 
    int count = 0; 
    for(int i = 0; n > 1; i++){ 

     if(n%2 == 0){n /= 2; count++;} 
     else if(n%3 == 0){ n /= 3; count++;} 
     else { n -= 1; count++;} 

    } 
    System.out.println("your no is minimized to: " + n); 
    System.out.println("The min no of steps: " + count);  
} 
}