找到最少的移动次数

Question

我有以下问题陈述:

给定一个数n(1 <n <10 ^ 9),该集合中数学运算的最小数量(将n除以2,将n除以3,从n减去1)可以用来转换数n到1？

到目前为止,我已经编写了以下代码以尝试解决问题:

while(n!=1){

    if(n%3==0 || n%2==0){
        if(n%3==0){
            n=n/3;
            c=c+1;
        }
        if(n%2==0){
        n=n/2;
        c=c+1;
        }
    }
    else{
        n=n-1;
        c=c+1;
    }
}
System.out.println(c);

但我没有得到所需的输出.有人可以帮助我.

Answer 1

我认为特里斯坦是对的 - 你无法知道哪个操作最终会产生最短的路径,所以你必须尝试所有这些才能得到正确的答案.

通常,像这样的强力解决方案意味着计算将采用指数时间.从n开始,然后使用3个操作计算最多3个新数字.然后对于这3个数字中的每一个,你得到另外3个,总共9个.然后对于这9个中的每一个,你得到另外3个,共27个; 等等.您可以看到如何快速结束一系列荒谬的可能性.

但是,您的搜索空间有限.由于您的所有操作都会导致值减小,因此您只会遇到从1到n(包括1和n)的数字.这意味着最多需要n次操作才能达到1的目标.每个数字只有一条最短路径,所以一旦找到了这条路径,你就不需要考虑任何其他路径了那个号码.如果你保留一组以前看过的数字,你应该能够消除大部分的搜索空间,因为你可以抛弃重复的结果.(这是Memoization的一种形式.)

这是我将如何解决这个问题:

1. 创建一个Set<Integer>包含以前看到的值.
2. 创建一个Map<Integer, Integer>以保存您的活动值.每个键→值条目的键将是从n到的路径中的数字1,该值将是达到该数字所花费的操作数.
3. 将初始条目n → 0放在活动地图中.
4. 虽然您的活动地图不包含具有值的键1(您的目标):
   1. 创建一个空地图以保存新的活动值.
   2. 对于活动 x → i中的每个条目:
      1. 如果x可被3整除且x/3不在所见集中,则将x/3 添加到所看到的并将x/3→ i + 1放入新的活动地图中.
      2. 为x/2和x -1 做类似的事情.
   3. 替换当前积极与地图新的活动地图.
5. 返回值我为入门1→ 我在你的活动地图.

你可以采取一些措施来加快速度(例如,当你找到时立即突破循环1),或者减少内存占用(例如,如果它们比任何一个都大,你可以丢弃看到的哨兵您的活动条目,或使用列表而不是地图,因为迭代的所有i值都相同),但这应该足够高效,以满足您的需要.

我已将我的解决方案移植到Java并在此处发布:

http://ideone.com/qWt0LE

输出包含一些时间.请注意,此处链接的解决方案使用了一个可见的地图和一个活动的列表.我将链中的前一个数字存储为所看到的每个地图条目的值,这允许我在结束时重建链.在输出中,3表示除以3,2表示除以2,1表示减1.

Answer 2

我相信这里的问题只是计算最少的步骤数，而不是有关步骤的详细信息、如何处理它等。因此在这种情况下，下面的解决方案应该是有效且最简单的解决方案。动态规划中的自下而上方法。

int getMinOperations(int n) {
    // Use this array to store the previous solved result.
    int dp[] = new int[n + 1];
    // base case, if it is 1, we do not need to do any processing
    dp[1] = 0;
    
    for (int i = 2; i <= n; i++) {
        // for the time being, let's assume we are getting minimum number of step by subtracting 1
        dp[i] = 1 + dp[i - 1];
        // if number if divisible by 2 let's divide it and compare it with the number of steps 
        // calculated in previous step, choose the minimum one
        if (i % 2 == 0)
            dp[i] = Math.min(dp[i], 1 + dp[i / 2]);
        // if number if divisible by 3 let's divide it and compare it with the number of steps 
        // calculated in previous step, choose the minimum one
        if (i % 3 == 0)
            dp[i] = Math.min(dp[i], 1 + dp[i / 3]);
        // At this step we have stored the minimum step to reduce the i to 1. and we will continue till nth value
    }
    // Returning nth value of array, as value at each index is the minimum number of steps to reduce it to 1.
    int res = dp[n];
    delete[] dp;
    return res;
}

Answer 3

最简单的解决方案可能是探索所有可能性。

public static ArrayList<Integer> solve(int n, 
  ArrayList<Integer> moves, int bestMove,HashMap<Integer,Integer> memory) {

        if (moves.size() >= bestMove) return null;
        if (n == 1) return moves;
        Integer sizeOfPathN= memory.get(n);

        if (sizeOfPathN!=null && sizeOfPathN<=moves.size())return null;
        memory.put(n,moves.size());

        int size_1=Integer.MAX_VALUE, size_2 = Integer.MAX_VALUE, size_3 = Integer.MAX_VALUE;
        ArrayList<Integer> moves3 = null, moves2 = null, moves1;

        if (n % 3 == 0) {
            ArrayList<Integer> c = new ArrayList<Integer>(moves);
            c.add(3);
            moves3 = solve(n / 3, c,bestMove,memory);
            if (moves3!=null)
            size_3 = moves3.size();
        }

        bestMove = Math.min(bestMove, size_3);

        if (n % 2 == 0) {
            ArrayList<Integer> c = new ArrayList<Integer>(moves);
            c.add(2);
            moves2 = solve(n / 2, c,bestMove,memory);
            if (moves2!=null)
            size_2 = moves2.size();
        }

        bestMove = Math.min(bestMove, size_2);


        ArrayList<Integer> c = new ArrayList<Integer>(moves);
        c.add(1);
        moves1 = solve(n - 1, c,bestMove,memory);
        if (moves1!=null)
        size_1 = moves1.size();

        int r = Math.min(Math.min(size_1, size_2),size_3);
        if (r==size_1) return moves1;
        if (r==size_2) return moves2;

        return moves3;

    }

解释：

n： 否

moves：包含动作的ArrayList。（用于打印目的）

bestMove：包含找到的最小解决方案的大小的值。

memory：包含先前探索的“状态”和路径长度的 HashMap。

如果我们调用 public static void main(String[] args) {

    long a = System.currentTimeMillis();
    Object[] sol=solve(10, new ArrayList<Integer>(),Integer.MAX_VALUE,new HashMap<Integer,Integer>()).toArray();
    System.out.println(sol.length);
    System.out.println(Arrays.toString(sol));
    System.out.println((System.currentTimeMillis()-a));
}

输出将是：

3
[1, 3, 3]
1

相当于n-1, n/3,n/3（@Tristan的最佳解决方案）

如果我们用1000 000 000as n 来调用它：

30
[1, 3, 3, 3, 3, 1, 3, 3, 1, 3, 1, 1, 3, 3, 3, 3, 1, 2, 2, 1, 3, 2, 1, 3, 3, 2, 1, 3, 2, 2]
55

如果我们用以下方式调用它11：

4
[1, 1, 3, 3]
1

编辑： 如果只需要移动次数：

public static int solve(int n,int moves,int bestMove,HashMap<Integer,Integer> memory) {

        if (moves >= bestMove) return Integer.MAX_VALUE;
        if (n == 1) return moves;
        Integer sizeOfPathN= memory.get(n);

        if (sizeOfPathN!=null && sizeOfPathN<=moves)return Integer.MAX_VALUE;
        memory.put(n,moves);

        int size_1=Integer.MAX_VALUE;
        int size_2 = Integer.MAX_VALUE;
        int size_3 = Integer.MAX_VALUE;

        moves=moves+1;
        if (n % 3 == 0) size_3 = solve(n / 3, moves,bestMove,memory);
        bestMove = Math.min(bestMove, size_3);      
        if (n % 2 == 0) size_2=solve(n >> 1, moves,bestMove,memory);

        bestMove = Math.min(bestMove, size_2);

        size_1 = solve(n - 1, moves,bestMove,memory);


        return  Math.min(Math.min(size_1, size_2),size_3);


    }

调用此方法

long a = System.currentTimeMillis();
System.out.println(
     solve(1000 *1000*1000, 0,Integer.MAX_VALUE,new HashMap<Integer,Integer>()));

    System.out.println((System.currentTimeMillis()-a));

输出：

30
24

足够快