Операции с большим количеством операций в Java Кратчайший путь к одному

Question

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

Вам предоставляется строковое представление числа длиной до 309 цифр. Вы можете преформ три операции:
1) Добавить 1 к числу
2) Вычесть 1
3) Разделить на 2

цель программы является, чтобы найти кратчайший путь, или наименьшее количество операций, могут быть выполнены на этот номер, так что результат равен 1.
например: дали "11"
1 -> 2 -> 3 -> 6 -> 12 -> 11
результат: 5 шагов
у меня было два подходы, которые не работают 100%:
1: начать с одного или самого номера и повторить шаг за шагом каждый возможный ответ до тех пор, пока число не будет достигнуто в пределах максимального количества шагов (например. 11, 20).
2: определить все возможные ответы с помощью двухмерного логического массива со всеми возможными перестановками, затем поочередно перебирать возможные движители. этот массив работает как карта концептуально.

Оба этих подхода имели ограниченный успех, так как я столкнулся с ошибкой stackoverflow или просто закончил работу с большими массивами. Это заставило меня ограничить количество шагов, чтобы код мог работать несколько успешно. Каким будет ваш подход?

EDIT 1:30 вечера
попытка 1 (извините, это было отредактировано серьезно, следовательно, почему это не было показано ранее ...):

import java.math.BigInteger; 
import java.util.Scanner; 

public class Answer { 

public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    String str; 
    Scanner sc = new Scanner(System.in); 
    while (true) { 
     str = sc.nextLine(); 
     System.out.println(answer(str)); 
    } 
    // System.out.println(answer("15")); 
} 

private static BigInteger minNumOfJumps; 
private static BigInteger big2 = BigInteger.valueOf(2); 
/** smallest Number of jumps reached so far */ 
private static BigInteger smallestAmountOfJumps; 

public static int answer(String string) { 
    // TODO Auto-generated method stub 
    BigInteger src = new BigInteger(string); 
    // BigInteger currentJump = BigInteger.ZERO; //used to initialize the 
    // nodes 
    // minNumOfJumps = src.divide(big2).add(BigInteger.ONE); //this must 
    // execute... 
    minNumOfJumps = new BigInteger("14"); // this must execute... 
    smallestAmountOfJumps = new BigInteger(minNumOfJumps.toString()); 
    // System.out.println(minNumOfJumps); 
    Node n = new Node(src); // ...before this 

    return Integer.parseInt(getSmallestAmountOfJumps().toString()); 
    // System.out.println(n.getSmallestAmountOfJumps().toString()); 
} 

public static BigInteger getBig2() { 
    return big2; 
} 

public static void setBig2(BigInteger big2) { 
    Answer.big2 = big2; 
} 

public static BigInteger getMinNumOfJumps() { 
    return minNumOfJumps; 
} 

public static BigInteger getSmallestAmountOfJumps() { 
    return smallestAmountOfJumps; 
} 

public static void setSmallestAmountOfJumps(String smallestAmountOfJumps) { 
    Answer.smallestAmountOfJumps = new BigInteger(smallestAmountOfJumps); 
} 
} 

/* 
* I have never made a shortest path algorithm before, so i hope this is toyour 
* satisfaction 
*/ 
class Node { 

/** number of nodes per creation */ 
private static final int NUMBER_OF_NODES_PER_NODE = 3; 
/** if this number is exceeded, no more jumps are necessary. */ // SAVE THAT 
                   // THINKING 
                   // JUICE! 
// private static BigInteger POSSIBLE_MINIMUM_NUMBER_OF_JUMPS; 

private static boolean lastTransformWasRemoveOne; 
private static boolean lastTransformWasAddOne; 

// if one is the given value(src) 
// private boolean isOneReached; 
/** if the current path isn't valid */ 
// private boolean threadIsBroken; 
// value passed during creation 
private BigInteger src; 
// current jump 
private BigInteger currentJump; 

// all possible transformations during next jump 
// private Node[] path; 

private Node(BigInteger src, BigInteger jump) { 
    currentJump = jump; 
    this.src = src; 
    // POSSIBLE_MINIMUM_NUMBER_OF_JUMPS = Answer.getMinNumOfJumps(); 
    // this.path = new Node[NUMBER_OF_NODES_PER_NODE]; 

    // 0 = remove | 1 = add | 2 = divide 
    for (int i = 0; i < NUMBER_OF_NODES_PER_NODE; i++) { 
     // System.out.println("i: " + i); 
     // System.out.println("src: " + src); 
     // System.out.println("compare: " + 
     // currentJump.compareTo(smallestAmountOfJumps)); 
     // System.out.println("currentJump: " + currentJump); 
     // System.out.println("smallestAmountOfJumps: " + 
     // smallestAmountOfJumps); 
     if (src.compareTo(BigInteger.ONE) == 0) { 
      if (currentJump.subtract(Answer.getSmallestAmountOfJumps()).compareTo(BigInteger.ZERO) == -1) { 
       Answer.setSmallestAmountOfJumps(currentJump.toString()); 
       // this below may break the code, but i think it fits with 
       // the logic 
       break; 
      } 
     } else if (i == 0) { // remove 1 
      // System.out.println(lastTransformWasAddOne); 
      // System.out.println("compare: " + 
      // currentJump.compareTo(smallestAmountOfJumps)); 
      // System.out.println("currentJump: " + currentJump); 
      // System.out.println("smallestAmountOfJumps: " + 
      // smallestAmountOfJumps); 
      if (!lastTransformWasAddOne && currentJump.compareTo(Answer.getSmallestAmountOfJumps()) < 0) { 
       lastTransformWasRemoveOne = true; 
       Node n = new Node(transform(i), currentJump.add(BigInteger.ONE)); 
      } 
     } else if (i == 1 && !lastTransformWasRemoveOne 
       && currentJump.compareTo(Answer.getSmallestAmountOfJumps()) < 0) { // add 
                        // 1 
      lastTransformWasAddOne = true; 
      Node n = new Node(transform(i), currentJump.add(BigInteger.ONE)); 
     } else if (src.mod(Answer.getBig2()) == BigInteger.ZERO 
       && currentJump.compareTo(Answer.getSmallestAmountOfJumps()) < 0) { // divide 
                        // by 
                        // 2 
      lastTransformWasRemoveOne = false; 
      lastTransformWasAddOne = false; 
      Node n = new Node(transform(i), currentJump.add(BigInteger.ONE)); 
     } else if (currentJump.compareTo(Answer.getSmallestAmountOfJumps()) == 0) 
      break; 
    } 
} 

private BigInteger transform(int i) { 
    // TODO Auto-generated method stub 
    return (i == 0) ? src.subtract(BigInteger.ONE) 
      : (i == 1) ? src.add(BigInteger.ONE) : (i == 2) ? src.divide(Answer.getBig2()) : BigInteger.ZERO; 
} 

/** 
* To be called once and only once. 
*/ 
public Node(BigInteger src) { 
    this(src, BigInteger.ZERO); 
} 

} `

и это еще одна попытка:

import java.math.BigInteger; 
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashSet; 
import java.util.Scanner; 
import java.util.Set; 

public class AnswerLessProficient { 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     String str; 
     Scanner sc = new Scanner(System.in); 
     while (true) { 
      str = sc.nextLine(); 
      System.out.println(answer(str)); 
     } 
     // System.out.println(answer("15")); 
    } 

    private static boolean notFirstCall; 
    private static boolean pathIsSet; 
    private static boolean[][] boolArray; 
    private static final String ZERO = "0"; 
    private static final BigInteger TWO = BigInteger.ONE.add(BigInteger.ONE); 
    private static int maximumSteps; 
    private static int maximumPermutations; 
    private static ArrayList<byte[]> listOfPaths; 
    private static Set<byte[]> setOfPaths; 
    // private static final int maximumPermutations = halfMaximumPermutations * 
    // 2; 
    // private static byte[][] path; 
    private static BigInteger src; 
    private static int steps; 
    private static BigInteger tempSrc; 
    private static byte[] tempPath; 
    // private static boolean followThePathsWithAlternateRoutesWasCalledOnce; 

    public static int answer(String s) { 
     // listOfPaths = new ArrayList<>(); 
     src = new BigInteger(s); 
     tempSrc = new BigInteger(s); 
     maximumSteps = 9; 
     steps = maximumSteps; 
     maximumPermutations = (int) Math.pow(2, maximumSteps); 
     if (!notFirstCall) { 
      tempPath = new byte[maximumSteps]; 
      setOfPaths = new HashSet<>(); 
      int mercyVar = (int) Math.pow(2, maximumSteps); 
      // path = new byte[maximumPermutations][maximumSteps]; 
      // boolArray = new boolean[maximumPermutations][maximumSteps]; 
      for (int i = 0; i < mercyVar; i++) { 
       listOfPaths = new ArrayList<>(); 
       String bin = (Integer.toBinaryString(i)); 
       while (bin.length() < maximumSteps) 
        bin = (ZERO + bin); 
       char[] chars = bin.toString().toCharArray(); 
       byte[] tempPath = new byte[maximumSteps]; 
       for (int j = 0; j < maximumSteps; j++) { 
        // if (!pathIsSet) 
        // path[j] = -1; 
        if (chars[j] == '0') { 
         tempPath[j] = 2; 
         // path[i][j] = 2; 
         // boolArray[i][j] = true; 
        } else { 
         tempPath[j] = -1; 
         // path[i][j] = -1; 
        } 
       } 
       //System.out.println(Arrays.toString(tempPath)); 
       listOfPaths.add(tempPath); 
       setOfPaths.add(tempPath); 
       findAltRoute(listOfPaths.size() - 1, maximumSteps - 1); 
      } 
      /* 
      * for (int i = mercyVar, j = 0; i < maximumPermutations; i++, j++) 
      * { for (int k = 0; k < maximumSteps; k++) { if (path[j][k] == -1) 
      * { path[i][k] = 1; } else { path[i][k] = 2; } } } 
      */ 

      // for (byte[] bs : setOfPaths) { 
      // System.out.println(Arrays.toString(bs)); 
      // } 
      /* 
      * for (int i = maximumSteps - 1, k = 0; i >= 0 && 
      * tempSrc.compareTo(BigInteger.ZERO) > 0; i--, k++) { if 
      * (tempSrc.compareTo(BigInteger.ONE) <= 0) if (k < steps) { steps = 
      * k; maximumSteps = steps; System.out.println(Arrays.toString(bs)); 
      * break; } else break; if (bs[i] == 2 && tempSrc.mod(TWO) != 
      * BigInteger.ZERO) break; tempSrc = transform(tempSrc, bs[i]); } 
      * tempSrc = src.add(BigInteger.ZERO); 
      */ 
      // } 

      // System.out.println(bin); 
      /* 
      * for (int j = 0; j < maximumSteps && i >= halfMaximumPermutations; 
      * j++) { // if (!pathIsSet) // path[j] = -1; if (chars[j + 1] == 
      * '0') { path[i][j] = 2; // boolArray[i][j] = true; } else { 
      * path[i][j] = 1; } } 
      */ 
      // System.out.println(bin); 
      // System.out.println(Arrays.toString(path[i])); 
      // pathIsSet = true; 
      notFirstCall = true; 
     } 
     justFollowThePath(); 
     // System.out.println(Arrays.toString(path[0])); 
     // System.out.println 
     // (Arrays.toString(path[(int) (maximumPermutations/2)-1])); 
     // System.out.println(Arrays.toString(path[maximumPermutations-1])); 

     /** 
     * 561-508-2204 george rubio debt forgiveness; 305-709-8255 
     */ 
     // for (int i = 0; i < maximumPermutations; i++) { 
     // followThePathsWithAlternateRoutes(path[i], maximumSteps - 1); 
     // } 

     // followThePathsWithAlternateRoutesWasCalledOnce = false; 

     /* 
     * for (int i = 0; i < maximumPermutations; i++) { for (int k = 0; k < 
     * maximumSteps; k++) { 
     * 
     * } 
     * 
     * for (int k = maximumSteps - 1; k > 0; k--) { 
     * 
     * } } 
     */ 

     // for (boolean[] bs : boolArray) { 
     // System.out.println(Arrays.toString(bs)); 
     // } 

     // System.out.println(Arrays.toString(boolArray[maximumPermutations - 
     // 1])); 
     // System.out.println(Arrays.toString(path)); 

     return steps; 
    } 

    private static void findAltRoute(int listIndex, int startingSearchIndex) { 
     if (listOfPaths.get(listIndex)[startingSearchIndex] == -1) { 
      // followThePathsWithAlternateRoutesWasCalledOnce = true; 
      // recurAlt(tempPath, maximumSteps - 1, maximumSteps - 1, (byte) 1, 
      // maximumSteps - 1); 
      for (int i = startingSearchIndex - 1; i >= 0; i--) { 
       if (listOfPaths.get(listIndex)[i] == 2) { 
        returnAltRoute(listIndex, i + 1, startingSearchIndex, (byte) 1, i); 
        findAltRoute(listIndex + 1, i); 
        return; 
       } 

       else if (i == 0) { 
        returnAltRoute(listIndex, i, startingSearchIndex, (byte) 1); 
        return; 
       } 
      } 
     } 
     for (int i = startingSearchIndex - 1; i >= 0; i--) { 
      if (listOfPaths.get(listIndex)[i] == -1 && listOfPaths.get(listIndex)[i + 1] == 2) { 
       if (i != 0) { 
        for (int k = i - 1; k >= 0; k--) { 
         if (listOfPaths.get(listIndex)[k] == 2 && listOfPaths.get(listIndex)[k + 1] == -1) { 
          // recurAlt(tempPath, i, k + 1, (byte) 1, k); 
          returnAltRoute(listIndex, k + 1, i, (byte) 1, k); 
          findAltRoute(listIndex, i); 
         } 
         // returnAltRoute(listIndex, 0, i, (byte)1); 
         // return; 
        } 
       } else { 
        returnAltRoute(listIndex, 0, i, (byte) 1); 
        return; 
       } 
      } 
     } 
    } 

    private static void returnAltRoute(int listIndex, int tempStart, int tempEnd, byte adjust, int returnSearchInt) { 
     byte[] tempPath = new byte[listOfPaths.get(listIndex).length]; 
     for (int i = maximumSteps - 1; i >= 0; i--) { 
      if (i >= tempStart && i <= tempEnd) { 
       tempPath[i] = adjust; 
      } else { 
       tempPath[i] = listOfPaths.get(listIndex)[i]; 
      } 
     } 
     System.out.println(Arrays.toString(tempPath)); 
     setOfPaths.add(tempPath); 
     listOfPaths.add(tempPath); 
     maximumPermutations = setOfPaths.size(); 
     findAltRoute(listIndex, returnSearchInt); 
    } 

    private static void returnAltRoute(int listIndex, int tempStart, int tempEnd, byte adjust) { 
     byte[] tempPath = new byte[listOfPaths.get(listIndex).length]; 
     for (int i = maximumSteps - 1; i >= 0; i--) { 
      if (i >= tempStart && i <= tempEnd) { 
       tempPath[i] = adjust; 
      } else { 
       tempPath[i] = listOfPaths.get(listIndex)[i]; 
      } 
     } 
     System.out.println(Arrays.toString(tempPath)); 
     setOfPaths.add(tempPath); 
     listOfPaths.add(tempPath); 
     maximumPermutations = setOfPaths.size(); 
    } 

    private static void justFollowThePath() { 
     for (byte[] bs : setOfPaths) { 
      //System.out.println(tempSrc.toString()); 
      for (int i = 0; i < maximumSteps && tempSrc.compareTo(BigInteger.ZERO) > 0; i++) { 
       if (tempSrc.compareTo(BigInteger.ONE) == 0) 
        if (i < steps) { 
         steps = i; 
         maximumSteps = steps; 
         //System.out.println(i); 
         // System.out.println(Arrays.toString(tempPath)); 
         break; 
        } else 
         break; 
       if (bs[i] == 2 && tempSrc.mod(TWO) != BigInteger.ZERO) 
        break; 
       tempSrc = transform(tempSrc, bs[i]); 
      } 
      tempSrc = src.add(BigInteger.ZERO); 

     } 
    } 

    private static void followThePathsWithAlternateRoutes(byte[] tempPath, int startingSearchIndex) { 
     if (tempPath[maximumSteps - 1] == -1) { 
      // followThePathsWithAlternateRoutesWasCalledOnce = true; 
      recurAlt(tempPath, maximumSteps - 1, maximumSteps - 1, (byte) 1, maximumSteps - 1); 
     } 
     for (int i = startingSearchIndex - 1; i >= 0; i--) { 
      if (tempPath[i] == -1 && tempPath[i + 1] == 2) { 
       for (int k = i - 1; k > 0; k--) { 
        if (tempPath[k] == 2) { 
         recurAlt(tempPath, i, k + 1, (byte) 1, k); 
        } 
       } 
      } 
     } 

     System.out.println(); 
     for (int i = maximumSteps - 1, k = 0; i >= 0 && tempSrc.compareTo(BigInteger.ZERO) > 0; i--, k++) { 
      if (tempSrc.compareTo(BigInteger.ONE) <= 0) 
       if (k < steps) { 
        steps = k; 
        maximumSteps = steps; 
        System.out.println(Arrays.toString(tempPath)); 
        break; 
       } else 
        break; 
      if (tempPath[i] == 2 && tempSrc.mod(TWO) != BigInteger.ZERO) 
       break; 
      tempSrc = transform(tempSrc, tempPath[i]); 
     } 
     tempSrc = src.add(BigInteger.ZERO); 
    } 

    private static BigInteger transform(BigInteger temp, byte i) { 
     // TODO Auto-generated method stub 
     return (i == -1) ? tempSrc.subtract(BigInteger.ONE) 
       : (i == 1) ? tempSrc.add(BigInteger.ONE) : (i == 2) ? tempSrc.divide(TWO) : null; 
    } 

    private static void recurAlt(byte[] tempPath, int tempStart, int tempEnd, byte adjust, int returnSearchInt) { 
     // TODO Auto-generated method stub 
     byte[] temp = new byte[tempPath.length]; 
     for (int i = 0; i < temp.length; i++) { 
      if (i >= tempStart && i <= tempEnd) 
       temp[i] = adjust; 
      else 
       temp[i] = tempPath[i]; 
     } 
     followThePathsWithAlternateRoutes(temp, returnSearchInt); 
    } 

} 

Есть другие вещи, которые я пробовал, но вы можете видеть, куда я иду. Любые указатели?

---

Answer 1

Если число четное, разделите его на 2. Если число равно 3 mod 4, добавьте его, если число фактически не равно 3. В противном случае вычтите его. Повторяйте, пока не дойдете до 1.

Вот доказательство.

Прежде всего обратите внимание, что если число четное, имеет смысл разделить на 2. Потому что, если вы выполняете некоторое число (скажем, 2k) +1 или -1, разделите его на 2, это то же самое, что и деление на два а затем добавление или вычитание k 1. Поэтому, делясь на две в первую очередь, вы сохраняете операции.

Итак, вопрос только в том, следует ли добавлять или вычитать 1, когда число нечетное. Вы можете доказать по индукции, что данная стратегия верна.

Нечетное число n равно либо 4x + 1, либо 4x + 3. Обратите внимание, что любая последовательность операций (когда мы делим на 2 по возможности) в какой-то момент достигнет либо x, либо x + 1.

Мы рассмотрим каждую из них по очереди и посчитаем кратчайшие пути к x и x + 1. (Проверка того, что я правильно определил кратчайшие пути, опущен).

В первом случае (4x + 1), вычитая первый, мы можем перейти к x в 3 этапа (4x + 1-> 4x-> 2x-> x) и x + 1 в 4 этапа (4x + 1-> 4x-> 2x-> х> х + 1). Добавив сначала, мы можем перейти к x в 4 этапа (4x + 1-> 4x + 2-> 2x + 1-> 2x-> x) и x + 1 в 4 этапа (4x + 1-> 4x + 2 -> 2x + 1> 2x + 2> х + 1). Таким образом, мы могли бы всегда вычесть первый.

Во втором случае (4x + 3), вычитая один первый, мы можем перейти к x в 4 этапа (4x + 3-> 4x + 2-> 2x + 1-> 2x-> x), а x +1 в 4 шага (4x + 3-> 4x + 2-> 2x + 1-> 2x + 2-> x + 1). Добавив сначала, мы можем перейти к x + 1 в 3 этапа (4x + 3-> 4x + 4-> 2x + 2-> x + 1), а x в 4 этапа (4x + 3-> 4x + 4 -> 2x + 2> х + 1-> х). Таким образом, мы могли бы всегда добавить 1 сначала в этом случае.

Во втором случае, если x = 0 (то есть n = 4 * 0 + 3 = 3), то наши рассуждения не совсем работают, поскольку мы фактически не достигнем x. В этом случае мы должны вычесть один и разделить на 2, чтобы достигнуть 1.

Вопрос помеченный Java, но вот некоторые псевдокод (на самом деле Python) для получения оптимальных цепочек:

def chain(n): 
    while n: 
     print n, 
     if n % 2 == 0: 
      n //= 2 
     elif n % 4 == 3 and n != 3: 
      n += 1 
     else: 
      n -= 1 

chain(11) 

Answer 2

Мой первый подход будет использовать BFS.

Есть только 2 или 3 переход состояния (я полагаю, мы не можем делить нечетное число). Но этот подход достаточно быстр для небольшого числа.

Второй подход будет использовать A* с наименьшим числом в качестве эвристической функции. Например, когда я начинаю с «12», я могу перейти к: «11», «13», «6». Я выберу «6» для следующего состояния, потому что он ближе к «1». Однако этот подход все еще не достаточно быстрый.

Мой третий подход будет генерировать ответ от «1» до «100», а затем ищет шаблон/формулу.

Редактировать: удалить неправильную формулу.