寻找最少的移动次数 [英] Finding least number of moves

问题描述

我有以下问题陈述：

给定一个数字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);

但我没有得到所需的输出。有谁能帮我一下吗？

推荐答案

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

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：N

moves：包含移动的ArrayList。(用于打印底稿)

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

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

如果我们调用 PUBLIC STATIC VOID Main(字符串[]参数){

    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(@特里斯坦的最佳解决方案)

如果我们使用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

足够快

这篇关于寻找最少的移动次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！