Convert a number to another number using recursion

Question

I am trying to make an algorithm for the following task:

• I have two integers a ≤ b
• The algorithm should convert a to b by adding 1 and multiply by 2 operations. For example, if a = 5 and b = 23, the program should output something like 23 = ((5 * 2 + 1) * 2 + 1)
• I need to use recursion

I've searched Googled many times, but all I could find were ideas on how to transform a matrix, how to do geometric transformations, how to convert a row to another row, etc.

Does anyone have any ideas?

Answer 1

This is the way to find the transformation with the minimum number of operations:

(EDIT: ​​)

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

, :

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 3

, , . .

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 4

,

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

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

, . , , , ; , 1, , , .

And testing on an example 5> 23 gives:

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

You can be syntax with syntax, but hopefully a little verbosity helps show the intent of the code.

The josh.trow hat tip when I used his idea on how to make string formatting.

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 try doubling, and let 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 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 7

Look for the double & add algorithm, it is a double square & multiply one ... sorry, but I do not know the details.