Преобразование числа в другое число с помощью рекурсии

Question

Я пытаюсь создать алгоритм для следующей задачи:

• У меня есть два целых числа a ≤ b
• Алгоритм должен преобразовать a в b путем сложения 1 и умножения на 2 операции.Например, если a = 5 и b = 23, программа должна вывести что-то вроде 23 = ((5 * 2 + 1) * 2 + 1)
• Я должен использовать рекурсию

Я уже гуглил много раз, но все, что я мог найти, это идеи о том, как преобразовать матрицу, как сделать геометрические преобразования, как преобразовать строку в другую строку и тому подобноепрочее.

У кого-нибудь есть идеи?

Answer 1

Это способ найти преобразование с минимальным числом операций:

(РЕДАКТИРОВАТЬ: добавлены круглые скобки)

public static void main (String [] args)
{
    int a = 5, b = 23;
    System.out.println (transform (a, b) + " = " + b);
}

public static String transform (int a, int b)
{
    if (a == b) return "" + a;
    if (b % 2 == 0 && 2 * a <= b)
    {
        b = b / 2;
        return transform (a, b) + " * 2";
    }
    else
    {
        b = b - 1;
        return "(" + transform (a, b) + " + 1)";
    }
}

Answer 2

Это на самом деле печатает, но это может быть не совсем то, что вы ищете, я не уверен.

private static String doDo(int a, int b, StringBuilder sb) {
    if (a == b) {
      String ret = sb.toString();
      int charCount = ret.replaceAll("[^)]", "").length();
      for (int i = 0; i < charCount; i++)
        ret = "(" + ret;
      return ret;
    }
    if (a < (b/2f)) {
      sb.append(")*2+1");
      return doDo(a*2 + 1, b, sb);
    } else {
      sb.append("+1");
      return doDo(a+1, b, sb);
    }
  }

System.out.println(doDo(5, 23, new StringBuilder().append("5")));

Это напечатано -> ((5)*2+1)*2+1

Answer 3

Следующий метод должен работать для вас, я думаю:

int transform(int a, int b) {
   if (a>= b)
      return a;
   else if (a*2 <= b)
      return transform(2*a, b);
   else
      return transform(a + 1, b);
}

Answer 4

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

И тестирование на примере 5-> 23 дает:

((((5)*2)+1)*2)+1=23

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

Шляпа для josh.trow, когда я использовал его идею о том, как сделать форматирование строки.

import java.util.ArrayList;
import java.util.List;

public class DoubleAndAddAlgorithm {
    public enum Op {
        DOUBLE, ADD_ONE
    }

    private static List<Op> getOptimalTransform(int a, int b) throws IllegalArgumentException {
        // Returns the list of operations that comprises the optimal way to get from a to b

        // If a is already bigger than b, we have a problem
        if (a > b) {
            throw new IllegalArgumentException("a cannot be greater than b");
        }

        List<Op> result = new ArrayList<Op>();

        // If we can get there in one operation, do so
        if (2*a == b) {
            result.add(Op.DOUBLE);
        } else if (a+1 == b) {
            result.add(Op.ADD_ONE);
        }

        // If doubling would cause us to overshoot, all we can do is add 1
        // and take it from there...
        else if (2*a > b) {
            result.add(Op.ADD_ONE);
            result.addAll(getOptimalTransform(a+1, b));
        }

        // Otherwise, let's try doubling, and let's try adding one, and use
        // recursion to see which gets us to the target quicker
        else {
            List<Op> trialResultDouble = getOptimalTransform(2*a, b);
            List<Op> trialResultAddOne = getOptimalTransform(a+1, b);

            // Let's say (arbitrarily), that if neither operation results in us
            // getting to the target any quicker than the other, we choose to add 1
            if (trialResultDouble.size() < trialResultAddOne.size()) {
                result.add(Op.DOUBLE);
                result.addAll(trialResultDouble);
            } else {
                result.add(Op.ADD_ONE);
                result.addAll(trialResultAddOne);
            }
        }
        return result;
    }

    public static String getFormattedResult(int a, int b) {
        try {
            List<Op> ops = getOptimalTransform(a, b);

            StringBuilder sb = new StringBuilder();
            sb.append(Integer.toString(a));

            for (Op op: ops) {
                if (op == Op.DOUBLE) {
                    sb.insert(0, "(");
                    sb.append(")*2");
                } else if (op == Op.ADD_ONE) {
                    sb.insert(0, "(");
                    sb.append(")+1");
                }
            }

            sb.append("=");
            sb.append(Integer.toString(b));

            return sb.toString();
        } catch (IllegalArgumentException e) {
            return "Illegal arguments supplied";
        }
    }

    public static void main(String[] args) {
        System.out.println( getFormattedResult(5, 23) );
    }
}

Answer 5

Если вы не хотите переигрывать, используйте это (модифицированная версия решения @ anubhava).

int transform(int a, int b) {
   if (a >= b){
      return a;
   } else {
      int c = a*2 + 1;
      if (c>b){
          return a;
      } else {
          return transform(c, b);
      }
  }
}

Answer 6

вот какой-то псевдокод, который вы можете использовать

transform(a, b)
start
   if a >= b
       return
   else
     print formatted progress 
     transform(a * 2 + 1, b)
end

Answer 7

Поиск алгоритма под названием double & add, это двойное от квадрата и умножение одного ... извините, но я не знаю деталей.