使用指定的操作将一个数字转换为另一个数字。在这方面我需要一些帮助

Question

这是我最近遇到的问题-

null

假设我有三个整数k，m，n。我必须以最少的操作次数从k到达m，可能的操作是-

你可以把k乘以n。

你可以把k降低2。

你可以把k减1。

此外，这3个操作可以按任何顺序执行。

有很多方法可以尝试--无论是递归还是动态方法。但是我找到了一个有趣的解决方案，它没有实现这两个，而且我很难理解它。这里有代码供参考-

int k = sc.nextInt();
int m = sc.nextInt();
int n = sc.nextInt();
int count=0;
int x=0;
while(k<m)
{
if(m%n==0){
m=m/n;
count++;
}
else{
x=(n-(m%n));
m+=(x)/2*2+(x)%2;
count+=x/2+x%2;
}
}
if(k>m)
{
count+=(k-m)/2+(k-m)%2;
}
System.out.println(count);
}

好吧，我真的很抱歉不能包含注释，因为我不能得到这段代码的诀窍。谁能请您把代码读一遍，并解释一下这段代码实际上是如何工作的吗？那会有很大的帮助！（顺便说一下，代码运行良好！）

Answer 1

我想我已经简化了代码：

int k = 2;
int m = 5;
int n = 6;
int count = 0;
while (k < m) {
    k *=n;
    count++;
}
if (k > m) {
    count += (k - m) / 2 + (k - m) % 2;
}
System.out.println(count);

请让我知道它失败的用例。输出：

5

Answer 2

下面是一个注释版本（重新格式化也有很大帮助）：

    Scanner sc = new Scanner(System.in);

    int k = sc.nextInt();
    int m = sc.nextInt();
    int n = sc.nextInt();
    
    sc.close();

    int count = 0, x;
    while (k < m) { // Loop while k is smaller then m (meaning our end goal for m is to be smaller or equal to k) (since k will not change inside of the while loop we know that m must change)
        if (m % n == 0) { // Check if m divided by n has NO remainder, if so do the division and increase count by one
            m = m / n;
            count++;
        } else { // If not then...
            // ...subtract the remainder from n and store it in x. X now contains the number which you would need to add to m to make 'm % n == 0' (the if statement) result in true
            x = (n - (m % n));

            // In here we do 'x / 2 * 2' first which will result in even value (rounding x to its lower even value. eg. x = 5 would become 4. Since we are using integers) which we then add to m.
            // Then we also add the missing '1' to m to make the if statement in the next loop result in true
            // I tested this algorithm btw. it does not change the value of x:
            /*
                for (int x = 0; x < 5000; x++) {
                    boolean same = x == (x / 2 * 2 + x % 2);
                    System.out.println(x + " -> " + same);
                }
                Result: same is always true
            */
            m += x / 2 * 2 + x % 2; // This line can be simplified to 'm += x;'
            
            // Then we add half of the x and a 0 or a 1 to count
            count += x / 2 + x % 2;
        }
    }
    if (k > m) { // This will run always if k is not eual to m
        
        // This line is almost equal to this one: 'count += x / 2 + x % 2;'
        // except, that every x was replaced by '(k - m)'
        
        count += (k - m) / 2 + (k - m) % 2;
    }
    
    // Then we print out count
    System.out.println(count);